การกระจายโหลดยังคงเป็นหนึ่งในความท้าทายที่สำคัญที่สุดในระบบกระจาย ซึ่งการเลือกแนวทางที่ผิดอาจนำไปสู่ประสิทธิภาพที่แย่และการใช้ทรัพยากรอย่างสิ้นเปลือง การอภิปรายในชุมชนเมื่อเร็วๆ นี้ได้เน้นย้ำถึงโซลูชันที่หรูหราซึ่งใช้ข้อมูลน้อยกว่าแต่ตัดสินใจได้ดีกว่า นั่นคืออัลกอริทึม Power of Two Random Choices
อัลกอริทึมง่ายๆ เอาชนะโซลูชันที่ซับซ้อน
แนวทาง Power of Two Random Choices ทำงานโดยการเลือกเซิร์ฟเวอร์สองตัวแบบสุ่มและส่งทราฟฟิกไปยังเซิร์ฟเวอร์ที่มีโหลดเบากว่า วิธีการที่ดูเรียบง่ายนี้มีประสิทธิภาพสม่ำเสมอเหนือกว่าแนวทางที่ซับซ้อนมากกว่า โดยเฉพาะเมื่อทำงานกับข้อมูลโหลดที่ล่าช้าหรือถูกแคช สมาชิกในชุมชนได้แบ่งปันทรัพยากรเพิ่มเติมและการแสดงภาพที่แสดงให้เห็นประสิทธิภาพของอัลกอริทึมในสถานการณ์ต่างๆ
อัลกอริทึมนี้โดดเด่นเป็นพิเศษในสภาพแวดล้อมที่ไม่มีข้อมูลโหลดแบบเรียลไทม์ที่สมบูรณ์แบบ ไม่เหมือนกับแนวทางแบบเลือกเซิร์ฟเวอร์ที่ดีที่สุดแบบดั้งเดิมที่ประสบปัญหาพฤติกรรมการแห่กันด้วยข้อมูลที่ล้าสมัย วิธีการสองตัวเลือกนี้รักษาประสิทธิภาพที่เสถียรแม้ในขณะที่ช่วงเวลาการรีเฟรชแคชเพิ่มขึ้น
การเปรียบเทียบประสิทธิภาพของอัลกอริทึม:
- การเลือกแบบสุ่ม: ประสิทธิภาพแย่ที่สุดกับข้อมูลใหม่ แต่ดีขึ้นกับข้อมูลเก่า
- การเลือกเซิร์ฟเวอร์ที่ดีที่สุด: ดีที่สุดกับข้อมูลใหม่ แต่แย่ที่สุดกับข้อมูลเก่าเนื่องจากปรากฏการณ์การแห่กัน
- การเลือกที่ดีที่สุดจาก 2 แบบสุ่ม: เป็นผู้นำอย่างสม่ำเสมอในช่วงการรีเฟรชข้อมูล 10-70 วินาที
- การเลือกที่ดีที่สุดจาก 3 แบบสุ่ม: ประสิทธิภาพดี แต่แพ้ "การเลือกที่ดีที่สุดจาก 2" เมื่อความล่าช้าเพิ่มขึ้น
การเปรียบเทียบประสิทธิภาพในโลกแห่งความจริง
ผู้ปฏิบัติงานในอุตสาหกรรมได้ให้ข้อมูลเชิงลึกที่มีค่าในการเปรียบเทียบอัลกอริทึมนี้กับวิธีการกระจายโหลดที่มีอยู่แล้ว การทดสอบของ HAProxy แสดงให้เห็นว่าแม้อัลกอริทึม least-connections จะเหนือกว่า Power of Two Random Choices ในบางครั้งในสภาวะที่เหมาะสม แต่วิธีการสองตัวเลือกพิสูจน์ให้เห็นว่ามีความยืดหยุ่นมากกว่าและไม่เคยมีประสิทธิภาพแย่ที่สุดในบรรดาแนวทางที่ทดสอบ
P2C ไม่เคยเป็นตัวเลือกที่แย่ที่สุดและถือได้ว่าเป็นค่าเริ่มต้นที่สมเหตุสมผลกว่าเมื่อ least-connections ไม่พร้อมใช้งาน
อย่างไรก็ตาม สมาชิกในชุมชนบางคนได้สังเกตข้อจำกัดในสถานการณ์เฉพาะ การจำลองที่เกี่ยวข้องกับความแตกต่างที่ยาวนานระหว่างเซิร์ฟเวอร์เผยให้เห็นว่าอัลกอริทึมยังคงสามารถส่งทราฟฟิกไม่สมส่วนไปยังเซิร์ฟเวอร์ที่มีโหลดหนัก แม้ว่าจะรักษาขีดจำกัดสัมบูรณ์ในการเพิ่มโหลดเป็นสองเท่าบนเซิร์ฟเวอร์ใดเซิร์ฟเวอร์หนึ่ง
ผลการปรับปรุงประสิทธิภาพทางคณิตศาสตร์:
- การกระจายแบบสุ่ม: โหลดสูงสุดของเซิร์ฟเวอร์เป็นสัดส่วนกับ log(n)
- Power of Two Choices: โหลดสูงสุดของเซิร์ฟเวอร์เป็นสัดส่วนกับ log(log(n))
- การจำกัดโหลด: อัลกอริทึมจำกัดการเพิ่มขึ้นของโหลดสูงสุดไว้ที่ 2 เท่าในเซิร์ฟเวอร์ตัวเดียว
- ช่วงที่เหมาะสม: มีประสิทธิภาพสูงสุดเมื่อใช้ช่วงเวลาการรีเฟรช cache ระหว่าง 10-70 วินาที
รากฐานทางคณิตศาสตร์และการผสานรวมกับคลาวด์
คณิตศาสตร์พื้นฐานที่อยู่เบื้องหลังแนวทางนี้มีความน่าสนใจ งานวิจัยแสดงให้เห็นว่าการกระจายคำขอข้ามเซิร์ฟเวอร์โดยใช้วิธีการนี้ส่งผลให้โหลดเซิร์ฟเวอร์สูงสุดเป็นสัดส่วนกับ log(log(n)) ด้วยความน่าจะเป็นสูง เมื่อเปรียบเทียบกับ log(n) สำหรับการกระจายแบบสุ่ม ซึ่งแสดงถึงการปรับปรุงแบบเอ็กซ์โพเนนเชียลในการกระจายโหลด
สภาพแวดล้อมคลาวด์สมัยใหม่ได้แยกความซับซ้อนเหล่านี้ออกจากนักพัฒนาเป็นส่วนใหญ่ ทำให้การกระจายโหลดรู้สึกเหมือนเป็นปัญหาที่ได้รับการแก้ไขแล้วสำหรับกรณีการใช้งานหลายๆ กรณี แต่การเข้าใจพื้นฐานเหล่านี้ยังคงมีค่าสำหรับระบบที่ต้องการตรรกะการกระจายโหลดแบบกำหนดเองหรือการทำงานในระดับที่โซลูชันมาตรฐานไม่เพียงพอ
อัลกอริทึม Power of Two Random Choices แสดงให้เห็นว่าบางครั้งโซลูชันที่หรูหราที่สุดมาจากการยอมรับความสุ่มแทนที่จะต่อสู้กับมัน พิสูจน์ให้เห็นว่าในระบบกระจาย ข้อมูลที่น้อยกว่าสามารถนำไปสู่การตัดสินใจที่ดีกว่าได้จริง
อ้างอิง: Marc's Blog