Cloudflare ประหยัด RAM 100 TB ด้วยคณิตศาสตร์และ Rust: ลดจุดแฮชใน consistent hashing ลง 90% โดยการกระจายโหลดแทบไม่เปลี่ยน

Cloudflare ลดหน่วยความจำของบริการกระจายโหลดภายในลงรวม 100 TB ทั่วโลก จากการตั้งคำถามกับค่าตั้งต้นที่ทุกคนใช้กันมาหลายปี คือจำนวนจุดแฮชต่อเซิร์ฟเวอร์ใน consistent hashing การคำนวณพบว่าจุดแฮช 90,000 จุดสุดท้ายต่อเซิร์ฟเวอร์ช่วยให้โหลดกระจายสม่ำเสมอขึ้นเพียง 0.7% และเมื่อเกินราว 10,000 จุด การชนกันของค่าแฮชกลับทำให้แย่ลง ทีมจึงลดจุดแฮชลง 90% และบีบขนาดโครงสร้างข้อมูลใน Rust อีก 25% บทความนี้อธิบายคณิตศาสตร์เบื้องหลัง วิธีบีบข้อมูลโดยไม่ใช้ unsafe และวิธีปล่อยการเปลี่ยนแปลงที่เสี่ยงโดยไม่ทำให้แคชทั้งโลกหาย

consistent hashing คืออะไร และทำไมต้องมีจุดแฮชหลายพันจุด

เมื่อมีเซิร์ฟเวอร์ปลายทางหลายตัว ระบบกระจายโหลดต้องตัดสินใจว่าคำขอแต่ละรายการควรไปที่ไหน วิธีง่ายที่สุดคือเอาค่าแฮชของคำขอหารเอาเศษด้วยจำนวนเซิร์ฟเวอร์ แต่ทุกครั้งที่เพิ่มหรือถอดเซิร์ฟเวอร์ คำขอเกือบทั้งหมดจะย้ายที่ ทำให้แคชหายทั้งหมด consistent hashing แก้ปัญหานี้ด้วยการวางเซิร์ฟเวอร์เป็นจุดบนวงแหวนค่าแฮช คำขอจะไปที่เซิร์ฟเวอร์ที่อยู่ถัดไปบนวงแหวน เมื่อเซิร์ฟเวอร์เปลี่ยน คำขอที่ต้องย้ายมีเพียงส่วนน้อย แต่ถ้าแต่ละเซิร์ฟเวอร์มีจุดเดียว ช่วงบนวงแหวนจะยาวไม่เท่ากันจนโหลดเอียง ทางแก้มาตรฐานคือให้แต่ละเซิร์ฟเวอร์มีหลายจุด ค่าที่ใช้กันทั่วไปใน NGINX และ Pingora คือ 160 จุดต่อเซิร์ฟเวอร์

ปัญหาที่ Cloudflare เจอ: จุดแฮชทวีคูณจนกิน RAM หลาย GB

บริการที่เป็นต้นเรื่องคือ Pingora Backend Router หรือ PBR ระบบกระจายโหลดภายในที่ใช้ไลบรารีโอเพนซอร์ส pingora-ketama สองอย่างทำให้จำนวนจุดพองขึ้น อย่างแรกคือการถ่วงน้ำหนักตามความจุของเซิร์ฟเวอร์ ทำให้จำนวนจุดต่อเซิร์ฟเวอร์ขึ้นไปถึงราว 100,000 จุด อย่างที่สองคือระบบสร้างวงแหวนแยกหนึ่งวงต่อการผสมกันของฟีเจอร์แต่ละแบบ มีวงแหวนหลายสิบวงที่เก็บข้อมูลซ้ำกัน บางโปรเซสจึงใช้ RAM ถึงราว 6 GB

คณิตศาสตร์ที่ตอบว่าจุดแฮชกี่จุดถึงพอ

ทีมใช้ค่าสัมประสิทธิ์การแปรผัน (coefficient of variation หรือ CV) วัดว่าส่วนแบ่งโหลดของแต่ละเซิร์ฟเวอร์ต่างจากค่าเฉลี่ยเท่าไร สำหรับเซิร์ฟเวอร์ N ตัวที่มีจุดแฮช k จุดต่อตัว ค่า CV ประมาณได้จากรากที่สองของ (N−1) หารด้วย (N·k + 1) ข้อสังเกตสำคัญคือ CV ลดลงตามรากที่สองของ k ไม่ใช่ตาม k ตรง ๆ การเพิ่มจุดสิบเท่าจึงลดความเอียงได้เพียงราว 3 เท่า ที่ 160 จุด CV อยู่ราว 8% และเมื่อคำนวณช่วงที่ระบบใช้จริง พบว่าจุดแฮช 90,000 จุดสุดท้ายต่อเซิร์ฟเวอร์ช่วยลดความคลาดเคลื่อนได้เพียง 0.7%

ยิ่งกว่านั้น ค่าแฮชที่ใช้เป็นจำนวนเต็ม 32 บิต ตามหลัก birthday paradox เมื่อจำนวนจุดรวมบนวงแหวนมากขึ้น โอกาสที่จุดสองจุดจะได้ค่าแฮชเดียวกันจะสูงขึ้นเร็วกว่าที่คนส่วนใหญ่คาด การจำลองของทีมพบว่าเมื่อเกินราว 10,000 จุดต่อเซิร์ฟเวอร์ การชนกันทำให้ความคลาดเคลื่อนเพิ่มขึ้นแทนที่จะลดลง ข้อสรุปคือจุดส่วนใหญ่ไม่ได้ช่วยอะไรเลย และบางส่วนทำให้แย่ลงด้วยซ้ำ ทีมจึงลดจากราว 100,000 เหลือราว 10,000 จุดต่อเซิร์ฟเวอร์

บีบโครงสร้างข้อมูลใน Rust โดยไม่ใช้ unsafe

แต่ละจุดบนวงแหวนเดิมเก็บค่าแฮชแบบ u32 (4 ไบต์) กับดัชนีเซิร์ฟเวอร์แบบ u32 (4 ไบต์) รวม 8 ไบต์ เมื่อพบว่าดัชนีแบบ u16 ซึ่งรองรับได้ถึง 65,536 เซิร์ฟเวอร์เพียงพอแล้ว ขนาดข้อมูลจริงควรเหลือ 6 ไบต์ แต่กฎการจัดเรียงหน่วยความจำ (alignment) ของ Rust ทำให้ struct ที่มีฟิลด์ u32 ถูกเติมช่องว่างจนยังเป็น 8 ไบต์ ทางแก้ปกติคือใส่ #[repr(packed)] ซึ่งเกี่ยวพันกับโค้ด unsafe ทีมเลือกเก็บจุดเป็นอาร์เรย์ไบต์ขนาด 6 ไบต์ แล้วเขียนเมธอดอ่านค่าแฮชจากไบต์ 0-3 และดัชนีจากไบต์ 4-5 ซึ่งคอมไพล์ออกมาเหมือน packed struct ทุกประการแต่ไม่ต้องมีโค้ด unsafe เลย ได้ส่วนลดอีก 25%

ปล่อยการเปลี่ยนแปลงที่เสี่ยงอย่างไรไม่ให้แคชทั้งโลกหาย

การเปลี่ยนจำนวนจุดแฮชทำให้คำขอบางส่วนย้ายเซิร์ฟเวอร์ ถ้าเปลี่ยนพร้อมกันทั่วโลก แคชที่อุ่นอยู่จะหายเป็นวงกว้างและโหลดจะพุ่งไปที่ต้นทาง ทีมจึงให้ระบบถือวงแหวนเก่าและใหม่ไว้คู่กัน แล้วใช้ค่าแฮชของคำขอเป็นตัวเลือกว่าคำขอนั้นจะใช้วงแหวนไหน คำขอเดิมจึงได้ผลเดิมทุกครั้ง จากนั้นค่อย ๆ ขยายจากศูนย์ข้อมูลทดสอบไปยังกลุ่มที่ใหญ่ขึ้น โดยคุมสองมิติแยกกัน คือสัดส่วนทราฟฟิกและขอบเขตพื้นที่ ระหว่างทางเฝ้าดูการเลือกเซิร์ฟเวอร์ ตัวนับเวอร์ชันวงแหวน ข้อผิดพลาดการเชื่อมต่อ หน่วยความจำ เวลาเริ่มโปรเซส พฤติกรรมแคช และทราฟฟิกไปต้นทาง และย้อนกลับได้ทันทีโดยไม่ต้อง deploy ใหม่ หน่วยความจำลดลงอย่างเห็นได้ชัดเมื่อถอดโค้ดวงแหวนเก่าออกหลังย้ายครบ 100%

บทเรียนสำหรับทีมพัฒนาไทย

ค่าตั้งต้นที่ "ทุกคนใช้" อาจถูกต้องในบริบทเดิม แต่เมื่อถูกคูณด้วยตัวแปรอื่นในระบบของเรา เช่นการถ่วงน้ำหนักหรือจำนวนวงแหวน มันอาจเลยจุดที่ได้ประโยชน์ไปไกลแล้ว ก่อนซื้อเครื่องใหญ่ขึ้นหรือเพิ่ม RAM ลองคำนวณว่าข้อมูลที่เก็บอยู่ให้ประโยชน์ส่วนเพิ่มเท่าไร และตรวจขนาดจริงของโครงสร้างข้อมูลที่มีสำเนาหลายล้านชุด เพราะ padding ไม่กี่ไบต์คูณจำนวนมหาศาลก็คือค่าใช้จ่ายจริง และทุกการเปลี่ยนแปลงที่กระทบการกระจายโหลดหรือแคช ควรปล่อยแบบเก่าคู่ใหม่ เลือกเส้นทางแบบคงที่ต่อคำขอ และย้อนกลับได้โดยไม่ต้อง deploy

ทีมงาน Smart Cyber Tech ให้บริการออกแบบและปรับแต่งระบบคลาวด์ ตั้งแต่วิเคราะห์ต้นทุนหน่วยความจำและเครื่อง ไปจนถึงวางแผนปล่อยการเปลี่ยนแปลงแบบค่อยเป็นค่อยไปที่ย้อนกลับได้ ปรึกษาได้ที่ แบบฟอร์มติดต่อ