การคิวรีเวกเตอร์ 3 พันล้านรายการ

• บันทึกการทดลองเชิงเทคนิคที่เล่ากระบวนการลองลงมือสร้าง โซลูชัน map-reduce ที่เหมาะสมที่สุด ด้วยตัวเอง จาก ปัญหาการคิวรีเวกเตอร์ 3 พันล้านรายการของ Jeff Dean
• เริ่มจากการทำแบบ naive เพื่อคำนวณ dot product ระหว่างเวกเตอร์ float32 ขนาด 768 มิติ จำนวน 3 พันล้านรายการ กับเวกเตอร์คิวรี 1,000 รายการ แล้วค่อย ๆ ปรับปรุงประสิทธิภาพด้วย การทำเวกเตอร์ไรซ์ด้วย numpy และการแปลงเป็น float32
• ที่สเกล 3,000 เวกเตอร์ วิธี naive ใช้เวลาประมาณ 2 วินาที แต่หลังทำเวกเตอร์ไรซ์ลดเหลือ 0.01 วินาที และเมื่อใช้ float32 ลดได้ถึง 0.0045 วินาที
• เมื่อขยายไปถึงระดับ 3 พันล้านเวกเตอร์ เมทริกซ์ผลลัพธ์ต้องใช้หน่วยความจำราว 8.6TB ทำให้เกิดปัญหา OOM และจำเป็นต้องมีการปรับแต่งเพิ่มเติม เช่น การประมวลผลแบบแบตช์, memory mapping, การเขียนใหม่ด้วย Rust/C, และ SimSIMD
• ย้ำว่าความท้าทายหลักที่ยากกว่าการหาคำตอบเชิงเทคนิคคือ การนิยามความต้องการ ให้ชัดเจน (เช่น รูปแบบผลลัพธ์, สเปกเครื่อง, การยอมรับการบีบอัดได้หรือไม่)

---

จุดเริ่มต้นของปัญหา

• เริ่มจากการได้เห็นบทสนทนาเกี่ยวกับ Jeff Dean และปัญหาการคิวรีเวกเตอร์ 3 พันล้านรายการ แล้วลองลงมือสร้าง โซลูชัน map-reduce ที่เหมาะสมที่สุดด้วยตัวเอง
• เวกเตอร์คืออาร์เรย์ของตัวเลขทศนิยมจำนวน n มิติ และ การค้นหาเวกเตอร์ ใช้สำหรับค้นหาคำหรือรายการที่มีความหมายใกล้เคียงกัน
• เป็นรูปแบบการใช้งานทั่วไปของ embedding ในงานค้นหา, ระบบแนะนำ, และ แอปพลิเคชันค้นหาเชิงกำเนิด อย่าง Cursor

การทำแบบ Naive

• สมมติฐานเริ่มต้น: มีเวกเตอร์เอกสารสำหรับค้นหา 3 พันล้านรายการ และเวกเตอร์คิวรีประมาณ 1,000 รายการ โดยทั้งหมดเก็บไว้บนดิสก์ในรูปแบบ .npy
• มิติเวอร์กเตอร์คือ 768 ซึ่งเป็นขนาดที่พบได้ทั่วไปในโมเดล embedding สำหรับงานคิวรีตามความคล้ายคลึง
• ใช้วิธีลูปซ้อนเพื่อคำนวณ dot product โดยนำเวกเตอร์คิวรีแต่ละรายการไปเปรียบเทียบกับเวกเตอร์เอกสารทั้งหมดแล้วคืนผลลัพธ์
• เมื่อลองทดสอบก่อนด้วยเวกเตอร์ 3,000 รายการ บน M2 MacBook ใช้เวลา ประมาณ 2 วินาที (ซึ่งเล็กกว่าระดับ 3 พันล้านอยู่ 1 ล้านเท่า)

การปรับแต่งแบบเวกเตอร์ไรซ์ (Vectorized)

• ใช้วิธี เวกเตอร์ไรซ์ โดยแทนลูปซ้อนด้วยการคูณเมทริกซ์ของ numpy (vectors_file @ query_vectors.T)
• ที่ 3,000 เวกเตอร์ ใช้เวลาเพียง 0.0107 วินาที ซึ่งดีขึ้นอย่างมาก
• เมื่อขยายเป็น 3 ล้านเวกเตอร์ ใช้เวลา 12.85 วินาที

การแปลงเป็น float32

• ปรับแต่งเพิ่มเติมโดยแปลงข้อมูลเป็น np.float32
• ที่ 3,000 เวกเตอร์ ลดเวลาได้ถึง 0.0045 วินาที
• เมื่อ 3 ล้านเวกเตอร์ใช้เวลาประมาณ 13 วินาที จึงคาดว่าในกรณี 3 พันล้านเวกเตอร์จะใช้เวลามากขึ้น 1,000 เท่า หรือราว 3,216 นาที

สรุปการเปรียบเทียบประสิทธิภาพ

• วิธี Naive (3,000 เวกเตอร์): 1.9877 วินาที
• วิธีเวกเตอร์ไรซ์ (3,000 เวกเตอร์): 0.0107 วินาที
• วิธีเวกเตอร์ไรซ์ (3 ล้านเวกเตอร์): 12.8491 วินาที
• วิธี float32 (3,000 เวกเตอร์): 0.0045 วินาที

ปัญหา OOM และแนวทางการปรับแต่งเพิ่มเติม

• หากประมวลผลอ็อบเจ็กต์ 3 พันล้านรายการด้วย float32 (4 ไบต์) จะต้องใช้หน่วยความจำประมาณ 8.6TB และเกิด OOM ระหว่างรัน
• จำเป็นต้องมีการปรับแต่งเพิ่มเติมตามแนวทางที่ Jeff Dean เสนอไว้:
  • เปลี่ยนโค้ดไปใช้ generator และการเปรียบเทียบแบบแบตช์
  • เขียนผลลงดิสก์เป็นระยะระหว่างคำนวณ หรือใช้ memory mapping
  • เขียนใหม่เป็นโค้ดระดับระบบด้วย Rust หรือ C
  • ใช้ไลบรารีเฉพาะทางสำหรับการเปรียบเทียบความคล้ายคลึงของเวกเตอร์จำนวนมาก เช่น SimSIMD

ความสำคัญของการนิยามความต้องการ

• ก่อนจะไปถึงการปรับแต่งเพิ่มเติม พบว่าตัวโจทย์เองยังมีหลายส่วนที่ไม่ชัดเจน:
  • ต้องการใช้เวกเตอร์คิวรีเดี่ยวค้นหากับทั้ง 3 พันล้านรายการครั้งเดียวแล้วคืนผลทั้งหมด หรือเป็นการค้นหาแบบ top-k ANN
  • ต้องคืนเวกเตอร์ต้นฉบับกลับมาด้วยหรือไม่ และต้องมี re-ranking ตามคะแนนความคล้ายคลึงหรือไม่
  • ต้องการรันการค้นหาทั้งหมดครั้งเดียวด้วยเวกเตอร์คิวรี 1,000 รายการหรือไม่
  • เวกเตอร์อยู่ในหน่วยความจำอยู่แล้ว, ต้องอ่านจากดิสก์ทีละรายการ, หรือเป็นแบบ streaming
  • รันบนเครื่องโลคัลหรือไม่, สเปกเครื่องเป็นอย่างไร, และ ใช้ GPU ได้หรือไม่
  • ขนาดของ embedding ส่งผลอย่างไรต่อการแทนผลลัพธ์และขนาดของเวกเตอร์อินพุต/เอาต์พุต
  • การ บีบอัด จาก float64 เป็น float32 ยอมรับได้ในแง่ความแม่นยำหรือไม่
  • เป็นโปรเจกต์ที่ทำครั้งเดียวหรือไม่ และมีเวลาให้สร้างมากแค่ไหน
• สิ่งที่ยากที่สุดไม่ใช่ตัวโซลูชันเชิงเทคนิค แต่คือ การนิยามความต้องการให้แม่นยำ