หน้าแรกของวิดีโอของเราแสดงรายการแนะนำใหม่ 24 รายการในทุกครั้งที่มีการรีเฟรช ต้องขอบคุณการเปลี่ยนมาใช้ weighted reservoir sampling (A-Res) การเปลี่ยนแปลงนี้ช่วยแก้ปัญหา "ตารางเดิมตลอดกาล" (same-grid-forever) ที่เคยเกิดขึ้นกับฟีดที่เรียงตามคะแนนแบบเดิมของเรา

ทำไมวิธีการแบบเดิมถึงทำให้ประสบการณ์การใช้งานแย่ลง

ทุกๆ สองชั่วโมง เราจะดึงวิดีโอที่กำลังเป็นกระแสล่าสุดจากแปดภูมิภาคและนำผลลัพธ์ไปเก็บไว้ในตาราง SQLite วิธีการแบบพื้นฐาน (naïve solution) คือการเรียงลำดับข้อมูลทั้งหมดตามคะแนนความเกี่ยวข้อง (relevance score) แล้วเลือก 24 อันดับแรก วิธีนั้นรับประกันว่ารายการที่มีคะแนนสูงสุดจะปรากฏขึ้น แต่ก็รับประกันด้วยว่ารายการเหล่านั้นจะค้างอยู่ตรงนั้นตลอดไป คลิปที่เป็นไวรัลเพียงคลิปเดียวอาจครองอันดับ 1 ได้นานหลายวัน และผู้ใช้จะเห็นตารางเดิมซ้ำๆ ทุกครั้งที่โหลดหน้าใหม่

นอกเหนือจากประสบการณ์ที่น่าเบื่อแล้ว การเรียงลำดับทั้งตารางในทุกๆ คำขอ (request) ยังบังคับให้ SQLite ต้องโหลดโครงสร้างข้อมูลชั่วคราวขนาดใหญ่ลงในหน่วยความจำ ซึ่งเป็นการสิ้นเปลืองทรัพยากร

สิ่งที่ weighted reservoir sampling มอบให้เรา

Weighted reservoir sampling ช่วยแก้ปัญหาสองอย่างได้พร้อมกัน:

  1. ความสดใหม่พร้อมความลำเอียง (Freshness with bias) – โอกาสที่วิดีโอแต่ละรายการจะถูกเลือกจะเป็นสัดส่วนตามน้ำหนัก (weight) ของมัน (เช่น คะแนนความเกี่ยวข้อง) วิดีโอที่มีน้ำหนักเป็นสองเท่าจะมีโอกาสปรากฏขึ้นเป็นสองเท่า แต่ไม่มีรายการใดที่ได้รับการรับประกันว่าจะได้พื้นที่แสดงผล
  2. ประสิทธิภาพการใช้หน่วยความจำ – อัลกอริทึมนี้จะเก็บเฉพาะ "reservoir" (อ่างเก็บข้อมูล) ขนาดคงที่จำนวน k รายการ (k = 24 สำหรับฟีดของเรา) โดยจะประมวลผลข้อมูลแบบสตรีมในการผ่านเพียงรอบเดียว (single pass) ดังนั้นการใช้หน่วยความจำจึงคงที่อยู่ที่ O(k) ไม่ว่าจะมีรายการที่เข้าข่าย (candidates) เข้ามามากเพียงใดก็ตาม

แนวคิดหลักนั้นเรียบง่าย ในขณะที่เราสแกนแถวข้อมูลที่เข้ามา เราจะกำหนดคีย์สุ่ม (random key) ให้กับแต่ละรายการโดยคำนวณรวมกับน้ำหนักของมัน จากนั้นจึงเก็บ k รายการที่มีคีย์สูงสุดไว้

การนำอัลกอริทึมไปใช้งานจริง

สำหรับวิดีโอแต่ละรายการ เราจะ:

  1. สุ่มตัวเลขแบบสม่ำเสมอ (uniform random number) u ∈ (0, 1)
  2. คำนวณคีย์ k = u^(1/weight)
    (ยิ่งน้ำหนักสูง คีย์ที่คาดหวังก็จะยิ่งใหญ่ขึ้น)
  3. ใส่รายการลงใน min-heap ที่เก็บคีย์สูงสุด k อันดับแรกในปัจจุบัน
    หาก heap มีขนาดเกิน k เราจะทิ้งคีย์ที่น้อยที่สุดไป

เมื่อสิ้นสุดการสตรีม ข้อมูลใน heap จะประกอบด้วยวิดีโอ 24 รายการที่เราจะนำไปแสดงผล

การจัดการกับข้อจำกัดของเลขทศนิยม (floating-point limits)

เมื่อน้ำหนักของวิดีโอมีค่ามากเกินไป u^(1/weight) จะมีค่าลดลงจนไม่สามารถแยกความแตกต่างจาก 1.0 ได้ในการคำนวณแบบ double-precision ซึ่งส่งผลให้รายการที่มีน้ำหนักมากหลายรายการมีคีย์เดียวกันและสูญเสียความสุ่ม วิธีแก้ไขคือการทำงานใน log space:

  • คำนวณ log_key = log(u) / weight แทนการใช้การยกกำลัง

เนื่องจากลอการิทึมเปลี่ยนการยกกำลังให้เป็นการคูณ ลำดับของคีย์จึงยังคงเดิมในขณะที่หลีกเลี่ยงปัญหาความแม่นยำที่ลดลง (precision cliff) โดยที่การคำนวณนี้แทบไม่มีต้นทุนเพิ่มเติมเลย

รายการตรวจสอบการติดตั้งใช้งาน (Implementation checklist)

  • โครงสร้างข้อมูล: ใช้ min-heap (priority queue) ขนาด k เพื่อเก็บคีย์ที่ใหญ่ที่สุดอย่างมีประสิทธิภาพ (O(log k) ต่อการแทรกหนึ่งครั้ง)
  • ประเภทข้อมูลตัวเลข: ใช้เลขทศนิยมแบบ 64-bit สำหรับ u และคีย์ที่ใช้ log ซึ่งให้ความแม่นยำที่เพียงพอสำหรับช่วงน้ำหนักทั่วไป
  • การตรวจสอบความถูกต้องทางสถิติ: ทำการทดสอบ Monte-Carlo อย่างรวดเร็วกับชุดตัวอย่างขนาดเล็ก หากรายการที่มีน้ำหนัก 10 ปรากฏขึ้นบ่อยกว่ารายการที่มีน้ำหนัก 1 ประมาณสิบเท่า แสดงว่าการติดตั้งใช้งานนั้นถูกต้อง
  • การสตรีมแบบรอบเดียว (Single-pass streaming): อัลกอริทึมไม่จำเป็นต้องทราบจำนวนรายการที่เข้าข่ายทั้งหมดล่วงหน้า ซึ่งสอดคล้องกับการทำงานของ SQLite cursor ของเราที่ส่งข้อมูลออกมาทีละแถว

บทสรุป

Weighted reservoir sampling ช่วยให้บริการแนะนำวิดีโอสามารถรักษาความสดใหม่ของหน้าแรก ให้ความสำคัญกับคะแนนความเกี่ยวข้อง และใช้หน่วยความจำน้อย ทั้งหมดนี้ทำได้ด้วยการประมวลผลรายการที่เข้าข่ายหลายหมื่นรายการเพียงรอบเดียว การเปลี่ยนการคำนวณคีย์ไปอยู่ใน log space และการใช้ min-heap ช่วยให้วิธีการนี้มีความแม่นยำและมีประสิทธิภาพสูง