เกิดขึ้นเมื่อไม่กี่วันที่ผ่านมา การประชุมไฮดรา. ทีมงานจาก JUG.ru Group ได้เชิญนักพูดในฝัน (Leslie Lamport! Cliff Click! Martin Kleppmann!) และอุทิศเวลาสองวันให้กับระบบกระจายและการประมวลผล Kontur เป็นหนึ่งในสามหุ้นส่วนของการประชุม เราพูดคุยกันที่บูธ พูดคุยเกี่ยวกับพื้นที่เก็บข้อมูลแบบกระจาย เล่นบิงโก และไขปริศนา

นี่คือโพสต์ที่มีการวิเคราะห์งานที่ยืน Kontur จากผู้เขียนข้อความของพวกเขา ใครอยู่บนไฮดรา - นี่คือเหตุผลของคุณที่จะจดจำประสบการณ์ที่น่ารื่นรมย์ ใครไม่ใช่ - โอกาสที่จะยืดสมองของคุณ ใหญ่ O- สัญกรณ์

มีแม้กระทั่งผู้เข้าร่วมที่ถอดฟลิปชาร์ทออกเป็นสไลด์เพื่อเขียนการตัดสินใจของพวกเขา ฉันไม่ได้ล้อเล่น - พวกเขาส่งกระดาษปึกนี้ให้ตรวจสอบ:

มีทั้งหมดสามงาน:

• เกี่ยวกับการเลือกแบบจำลองตามน้ำหนักสำหรับโหลดบาลานซ์
• เกี่ยวกับการเรียงลำดับผลการสืบค้นกับฐานข้อมูลในหน่วยความจำ
• ในการถ่ายโอนสถานะในระบบแบบกระจายที่มีโทโพโลยีแบบวงแหวน

งาน 1. ClusterClient

จำเป็นต้องเสนออัลกอริทึมสำหรับการเลือก K อย่างมีประสิทธิภาพจากแบบจำลองถ่วงน้ำหนัก N ของระบบแบบกระจาย:

ทีมของคุณได้รับมอบหมายให้พัฒนาไลบรารีไคลเอ็นต์สำหรับคลัสเตอร์ N โหนดที่มีการกระจายจำนวนมาก ไลบรารีจะติดตามข้อมูลเมตาต่างๆ ที่เกี่ยวข้องกับโหนด (เช่น เวลาแฝง อัตราการตอบกลับ 4xx/5xx เป็นต้น) และกำหนดน้ำหนักของจุดลอยตัว W1..WN ให้กับโหนดเหล่านั้น เพื่อสนับสนุนกลยุทธ์การดำเนินการพร้อมกัน ไลบรารีควรสามารถเลือกโหนด K จาก N โหนดแบบสุ่มได้ โอกาสที่จะถูกเลือกควรเป็นสัดส่วนกับน้ำหนักของโหนด

เสนออัลกอริทึมในการเลือกโหนดอย่างมีประสิทธิภาพ ประเมินความซับซ้อนในการคำนวณโดยใช้สัญกรณ์ O ขนาดใหญ่

ทำไมทุกอย่างเป็นภาษาอังกฤษ?

เนื่องจากในรูปแบบนี้ผู้เข้าร่วมการประชุมต่อสู้กับพวกเขาและเนื่องจากภาษาอังกฤษเป็นภาษาราชการของไฮดรา งานมีลักษณะดังนี้:

ใช้กระดาษและดินสอ คิด อย่ารีบเปิดสปอยล์ทันที 🙂

การวิเคราะห์โซลูชัน (วิดีโอ)

เริ่มเวลา 5:53 เพียง 4 นาที:

และนี่คือวิธีที่คนที่มีฟลิปชาร์ตเสนอวิธีแก้ปัญหา:

การวิเคราะห์โซลูชัน (ข้อความ)

วิธีแก้ปัญหาต่อไปนี้อยู่บนพื้นผิว: รวมน้ำหนักของแบบจำลองทั้งหมด สร้างตัวเลขสุ่มจาก 0 ถึงผลรวมของน้ำหนักทั้งหมด จากนั้นเลือก i-replica เพื่อให้ผลรวมของน้ำหนักแบบจำลองตั้งแต่ 0 ถึง (i-1)th น้อยกว่าตัวเลขสุ่ม และผลรวมของน้ำหนักจำลองตั้งแต่ 0 ถึง i-th - มากกว่านั้น ดังนั้นจึงเป็นไปได้ที่จะเลือกแบบจำลองหนึ่งรายการ และหากต้องการเลือกแบบจำลองถัดไป คุณต้องทำซ้ำขั้นตอนทั้งหมดโดยไม่พิจารณาแบบจำลองที่เลือก ด้วยอัลกอริทึมดังกล่าว ความซับซ้อนของการเลือกแบบจำลองหนึ่งรายการคือ O(N) ความซับซ้อนของการเลือกแบบจำลอง K คือ O(NK) ~ O(N2)

ความซับซ้อนของสมการกำลังสองนั้นไม่ดี แต่สามารถปรับปรุงได้ ในการทำเช่นนี้เราจะสร้าง ต้นไม้ส่วน สำหรับผลรวมของน้ำหนัก จะได้รับต้นไม้ที่มีความลึก lg N ในใบซึ่งจะมีน้ำหนักจำลองและในโหนดที่เหลือ - ผลรวมบางส่วนจนถึงผลรวมของน้ำหนักทั้งหมดที่รากของต้นไม้ ต่อไป เราจะสร้างตัวเลขสุ่มจาก 0 ถึงผลรวมของน้ำหนักทั้งหมด ค้นหาแบบจำลอง i-th ลบออกจากแผนภูมิ และทำซ้ำขั้นตอนเพื่อค้นหาแบบจำลองที่เหลือ ด้วยอัลกอริทึมนี้ ความซับซ้อนของการสร้างแผนผังคือ O(N) ความซับซ้อนของการค้นหาแบบจำลอง i-th และการลบออกจากแผนผังคือ O(lg N) ความซับซ้อนของการเลือกแบบจำลอง K คือ O(N + K lg N) ~ O(N lg N) .

ความซับซ้อนของบันทึกเชิงเส้นนั้นดีกว่าความซับซ้อนกำลังสองโดยเฉพาะอย่างยิ่งสำหรับ K ขนาดใหญ่

อัลกอริทึมนี้ นำไปใช้ในรหัส ไลบรารี ClusterClient จากโครงการ "ตะวันออก". (ที่นั่น ต้นไม้ถูกสร้างขึ้นใน O(N lg N) แต่สิ่งนี้ไม่ส่งผลต่อความซับซ้อนขั้นสุดท้ายของอัลกอริทึม)

ภารกิจที่ 2 ม้าลาย

จำเป็นต้องเสนออัลกอริทึมสำหรับการจัดเรียงเอกสารในหน่วยความจำอย่างมีประสิทธิภาพตามฟิลด์ที่ไม่ได้จัดทำดัชนีโดยพลการ:

ทีมของคุณได้รับมอบหมายให้พัฒนาฐานข้อมูลเอกสารที่ชาร์ดในหน่วยความจำ ปริมาณงานทั่วไปคือการเลือกเอกสาร N อันดับสูงสุดที่จัดเรียงตามฟิลด์ตัวเลขตามอำเภอใจ (ไม่ได้จัดทำดัชนี) จากคอลเล็กชันขนาด M (โดยปกติคือ N < 100 << M) ปริมาณงานทั่วไปที่น้อยลงเล็กน้อยคือการเลือก N อันดับบนสุดหลังจากข้ามเอกสาร S อันดับต้น ๆ (S ~ N)

เสนออัลกอริทึมเพื่อดำเนินการค้นหาดังกล่าวอย่างมีประสิทธิภาพ ประเมินความซับซ้อนในการคำนวณโดยใช้สัญกรณ์ O ขนาดใหญ่ในกรณีเฉลี่ยและสถานการณ์กรณีที่เลวร้ายที่สุด

การวิเคราะห์โซลูชัน (วิดีโอ)

เริ่มเวลา 34:50 น. เพียง 6 นาที:

การวิเคราะห์โซลูชัน (ข้อความ)

โซลูชัน Surface: จัดเรียงเอกสารทั้งหมด (เช่น กับ Quicksort) จากนั้นนำเอกสาร N+S ในกรณีนี้ ความซับซ้อนของการคัดแยกอยู่ที่ค่าเฉลี่ย O(M lg M) ที่แย่ที่สุด O(M2)

เห็นได้ชัดว่าการจัดเรียงเอกสาร M ทั้งหมดแล้วคัดมาเพียงส่วนเล็กๆ นั้นไม่มีประสิทธิภาพ เพื่อไม่ให้จัดเรียงเอกสารทั้งหมดอัลกอริทึมจึงเหมาะสม เลือกอย่างรวดเร็วซึ่งจะเลือก N + S ของเอกสารที่ต้องการ (สามารถจัดเรียงตามอัลกอริทึมใดก็ได้) ในกรณีนี้ ความซับซ้อนจะลดลงเหลือ O(M) โดยเฉลี่ย ในขณะที่กรณีที่เลวร้ายที่สุดจะยังคงเหมือนเดิม

อย่างไรก็ตาม คุณสามารถทำได้อย่างมีประสิทธิภาพยิ่งขึ้น - ใช้อัลกอริทึม การสตรีมไบนารีฮีป. ในกรณีนี้ เอกสาร N+S แรกจะถูกเพิ่มไปยัง min- หรือ max-heap (ขึ้นอยู่กับทิศทางการจัดเรียง) จากนั้นเอกสารถัดไปแต่ละรายการจะถูกเปรียบเทียบกับรูทของทรี ซึ่งมีเอกสารขั้นต่ำหรือสูงสุดในปัจจุบัน และเพิ่มเข้าไปในต้นไม้หากจำเป็น . ในกรณีนี้ ความซับซ้อนในกรณีที่เลวร้ายที่สุด เมื่อคุณต้องสร้างแผนผังใหม่อย่างต่อเนื่องคือ O (M lg M) ความซับซ้อนโดยเฉลี่ยคือ O (M) เช่นเดียวกับการเลือกด่วน

อย่างไรก็ตาม การสตรีมแบบฮีปมีประสิทธิภาพมากกว่าเนื่องจากในทางปฏิบัติ เอกสารส่วนใหญ่สามารถทิ้งได้โดยไม่ต้องสร้างฮีปใหม่หลังจากเปรียบเทียบกับองค์ประกอบรูทเพียงครั้งเดียว การเรียงลำดับดังกล่าวถูกนำมาใช้ในฐานข้อมูลเอกสารในหน่วยความจำ Zebra ที่พัฒนาและใช้งานใน Kontur

ภารกิจที่ 3 การแลกเปลี่ยนสถานะ

จำเป็นต้องเสนออัลกอริทึมที่มีประสิทธิภาพสูงสุดสำหรับการเปลี่ยนสถานะ:

ทีมของคุณได้รับมอบหมายให้พัฒนากลไกการแลกเปลี่ยนสถานะแฟนซีสำหรับคลัสเตอร์แบบกระจายของโหนด N ควรโอนสถานะของโหนด i-th ไปยังโหนด (i+1)-th สถานะของโหนด N-th ควรโอนย้ายไปยังโหนดแรก การดำเนินการที่รองรับเพียงอย่างเดียวคือการแลกเปลี่ยนสถานะเมื่อสองโหนดแลกเปลี่ยนสถานะของอะตอม เป็นที่ทราบกันว่า state swap ใช้เวลา M มิลลิวินาที ทุกโหนดสามารถเข้าร่วมในการแลกเปลี่ยนสถานะเดียวในช่วงเวลาใดก็ได้

ใช้เวลานานเท่าใดในการถ่ายโอนสถานะของโหนดทั้งหมดในคลัสเตอร์

การวิเคราะห์โซลูชัน (ข้อความ)

วิธีแก้ปัญหาพื้นผิว: แลกเปลี่ยนสถานะขององค์ประกอบที่หนึ่งและสอง จากนั้นจึงเปลี่ยนสถานะขององค์ประกอบที่หนึ่งและสาม จากนั้นจึงเปลี่ยนสถานะขององค์ประกอบที่หนึ่งและสี่ และอื่นๆ หลังจากการแลกเปลี่ยนแต่ละครั้ง สถานะขององค์ประกอบหนึ่งจะอยู่ในตำแหน่งที่ต้องการ คุณต้องทำการเรียงสับเปลี่ยน O(N) และใช้เวลา O(N M)

เวลาเชิงเส้นนั้นยาวนาน คุณจึงสามารถแลกเปลี่ยนสถานะขององค์ประกอบเป็นคู่: ครั้งแรกกับครั้งที่สอง ที่สามกับสี่ และอื่น ๆ หลังจากการแลกเปลี่ยนสถานะแต่ละครั้ง องค์ประกอบทุกวินาทีจะอยู่ในตำแหน่งที่ถูกต้อง คุณต้องทำการเรียงสับเปลี่ยน O(lg N) และใช้เวลา O(M lg N)

อย่างไรก็ตาม เป็นไปได้ที่จะทำให้การเปลี่ยนแปลงมีประสิทธิภาพมากขึ้น - ไม่ใช่แบบเชิงเส้น แต่เป็นแบบคงที่ ในการทำเช่นนี้ ในขั้นตอนแรก คุณต้องแลกเปลี่ยนสถานะขององค์ประกอบแรกกับองค์ประกอบสุดท้าย สถานะที่สองกับองค์ประกอบสุดท้าย และอื่นๆ สถานะขององค์ประกอบสุดท้ายจะอยู่ในตำแหน่งที่ถูกต้อง และตอนนี้เราต้องแลกเปลี่ยนสถานะขององค์ประกอบที่สองกับองค์ประกอบสุดท้าย องค์ประกอบที่สามกับองค์ประกอบสุดท้าย และอื่น ๆ หลังจากการแลกเปลี่ยนรอบนี้ สถานะขององค์ประกอบทั้งหมดจะอยู่ในตำแหน่งที่ถูกต้อง จะมีการเรียงสับเปลี่ยนทั้งหมด O(2M) ~ O(1)

วิธีแก้ปัญหาดังกล่าวจะไม่ทำให้นักคณิตศาสตร์ประหลาดใจเลยที่ยังจำได้ว่าการหมุนเป็นองค์ประกอบของสมมาตรตามแนวแกนสองเส้น อย่างไรก็ตาม การเปลี่ยนแปลงโดยทั่วไปไม่ใช่เรื่องเล็กน้อยสำหรับการเปลี่ยนแปลงทีละตำแหน่ง แต่โดยตำแหน่ง K < N (เขียนในความคิดเห็นว่าเป็นอย่างไร)

คุณชอบปริศนาไหม? คุณรู้วิธีแก้ปัญหาอื่น ๆ หรือไม่? แบ่งปันในความคิดเห็น

และนี่คือลิงค์ที่มีประโยชน์ในตอนท้าย:

• เรียนรู้เพิ่มเติมเกี่ยวกับ การพัฒนาโครงสร้างพื้นฐาน ในรูปร่าง
• ดูบันทึกภายใน ใบปลิวพร้อมรายงาน เกี่ยวกับระบบกระจาย
• ดูวิดีโอบรรยายชุดต่างๆอัลกอริทึมที่ผิดปกติสำหรับคนทั่วไป»
• สมัครสมาชิกกับเรา ช่องในโทรเลข

ที่มา: will.com