[2009 WSDM] ความท้าทายในการสร้างระบบค้นคืนข้อมูลขนาดใหญ่

มิติสำคัญและจุดแลกเปลี่ยนของระบบค้นคืนข้อมูล

• ในการออกแบบระบบ จำเป็นต้องพิจารณาจุดแลกเปลี่ยนทางวิศวกรรมระหว่างปัจจัยต่อไปนี้อย่างสมดุล
  • จำนวนเอกสารที่ถูกทำดัชนี
  • จำนวนคิวรีที่ประมวลผลได้ต่อวินาที (QPS)
  • ความสดใหม่ของดัชนี/ความเร็วในการอัปเดต
  • เวลาแฝงของคิวรี (Latency)
  • ปริมาณข้อมูลที่เก็บต่อเอกสารแต่ละฉบับ
  • ความซับซ้อน/ต้นทุนของการคำนวณคะแนนและอัลกอริทึมการค้นหา
• ความยากทางวิศวกรรมมีแนวโน้มแปรผันตามผลคูณของพารามิเตอร์เหล่านี้
• ปัจจัยทั้งหมดนี้ส่งผลต่อทั้งประสิทธิภาพโดยรวมและประสิทธิภาพต่อค่าใช้จ่าย (performance per dollar)

การเปลี่ยนแปลงของขนาดระบบ (1999 vs 2009)

• ในช่วง 10 ปีที่ผ่านมา ขนาดของระบบและข้อกำหนดด้านประสิทธิภาพเปลี่ยนแปลงไปอย่างมาก
  • # เอกสาร: ~70 ล้าน → หลายพันล้าน (~เพิ่มขึ้น 100 เท่า)
  • จำนวนคิวรีที่ประมวลผลต่อวัน: (~เพิ่มขึ้น 1000 เท่า)
  • ข้อมูลดัชนีต่อเอกสาร: (~เพิ่มขึ้น 3 เท่า)
  • เวลาแฝงของการอัปเดต: หลายเดือน → หลายนาที (~ลดลง 10000 เท่า)
  • เวลาแฝงเฉลี่ยของคิวรี: <1 วินาที → <0.2 วินาที (~ลดลง 5 เท่า)
  • ทรัพยากรระบบ: เครื่องมากขึ้น * เครื่องเร็วขึ้น (~เพิ่มขึ้น 1000 เท่า)
• พารามิเตอร์เหล่านี้เปลี่ยนแปลงอย่างต่อเนื่อง และบางครั้งก็เปลี่ยนทีละหลายหลัก ทำให้การออกแบบระบบต้องพัฒนาอยู่ตลอดเวลา
  • ดีไซน์ที่เหมาะกับช่วงเวลาใดเวลาหนึ่ง (X) อาจกลายเป็นดีไซน์ที่ผิดอย่างมากเมื่อขนาดโตขึ้น 10 เท่า หรือ 100 เท่า (ดังนั้นควรออกแบบโดยเผื่อการเติบโตประมาณ 10 เท่า แต่ควรวางแผนเขียนใหม่ก่อนจะโตถึง 100 เท่า)
  • ในช่วง 10 ปีที่ผ่านมา มีการยกเครื่องครั้งใหญ่ 7 ครั้ง

สถาปัตยกรรมระบบระยะแรก (1997-1999)

• ช่วงโครงการวิจัย (1997):
  • เว็บเซิร์ฟเวอร์ฝั่ง frontend รับคิวรี แล้วกระจายคำขอประมวลผลไปยัง index server และ document server
  • Index server: shard ตาม document ID (docid)
  • Document server: shard ตาม document ID (docid)
• หลักการพื้นฐาน:
  • เอกสารถูกกำหนด integer ID (docids) โดยให้เอกสารสำคัญ/คุณภาพสูงมี ID ที่เล็กกว่า
  • Index server: (คิวรี) → คืนรายการ (score, docid, ...) ที่เรียงลำดับแล้ว, shard ตาม docid และทำ replication เพื่อรองรับความจุ ค่าใช้จ่าย O(#คิวรี * #เอกสารในดัชนี)
  • Document server: (docid, คิวรี) → สร้าง (title, snippet), แมป docid → ตัวเอกสารเต็มบนดิสก์, shard ตาม docid ค่าใช้จ่าย O(#คิวรี)
• ระบบให้บริการ (1999):
  • เพิ่ม cache server และการเชื่อมต่อกับระบบโฆษณาเข้ากับโครงสร้างจากโครงการวิจัย
  • ใช้งาน replica ของ shard ทั้งฝั่ง index/document server
  • การแคช: แคชทั้งผลลัพธ์ของ index และ snippet ของเอกสาร อัตรา cache hit 30-60% ช่วยเพิ่มประสิทธิภาพและลดเวลาแฝงของคิวรีได้มาก (แต่ต้องระวัง latency spike ขนาดใหญ่เมื่อมีการอัปเดตดัชนี/ล้างแคช)

กลยุทธ์การแบ่งพาร์ทิชันดัชนี

• ตามเอกสาร (By doc): แต่ละ shard ถือดัชนีของเอกสารเพียงบางส่วน (Google เลือกวิธีนี้)
  • ข้อดี: แต่ละ shard ประมวลผลคิวรีได้อย่างอิสระ, เก็บข้อมูลต่อเอกสารเพิ่มเติมได้ง่าย, ใช้ทราฟฟิกเครือข่าย (request/response) น้อย
  • ข้อเสีย: ทุก shard ต้องประมวลผลทุกคิวรี, สำหรับคิวรีที่มี K คำ จะต้องมีการ seek ดิสก์ O(K*N) บน N shard
• ตามคำ (By word): แต่ละ shard ถือดัชนีของคำบางส่วนสำหรับเอกสารทั้งหมด
  • ข้อดี: คิวรี K คำใช้เพียงสูงสุด K shard, ต้อง seek ดิสก์ O(K)
  • ข้อเสีย: ต้องใช้แบนด์วิดท์เครือข่ายสูงกว่ามาก (ต้องรวบรวมข้อมูลรายคำของเอกสารที่ match มาไว้ที่เดียว), เก็บข้อมูลต่อเอกสารได้ยาก

การ crawl และทำดัชนีในช่วงแรก (1998-1999)

• การ crawl:
  • ระบบ batch crawl แบบง่าย: รายการ URL ตั้งต้น → crawl หน้าเว็บ → ดึงลิงก์และเพิ่มเข้าคิว → หยุดเมื่อเก็บหน้าได้มากพอ
  • สิ่งที่ต้องพิจารณา: ป้องกันไม่ให้เว็บใดเว็บหนึ่งรับโหลดมากเกินไป, ตัดสินลำดับความสำคัญของหน้าที่ยังไม่ crawl (เช่น PageRank), จัดการคิว URL ที่ยังไม่ crawl อย่างมีประสิทธิภาพ, รองรับความล้มเหลวของเครื่อง
• การทำดัชนี:
  • ระบบ batch indexing แบบง่าย สร้างบนเครื่องมือ Unix พื้นฐาน
  • ปัญหา: ไม่มี checkpoint จึงเจ็บปวดมากเมื่อเครื่องล้ม, ไม่มี checksum ของข้อมูลต้นฉบับจึงเกิดปัญหา hardware bit error (ยิ่งแย่เพราะเครื่องรุ่นแรกไม่มี ECC/parity, เกิดปัญหา "เกือบจะเรียงแล้ว"), ได้เรียนรู้เรื่อง "หน่วยความจำและการเขียนโปรแกรมที่เป็นปฏิปักษ์"
  • วิธีแก้: พัฒนานามธรรมของไฟล์ที่เก็บ checksum ของเรกคอร์ดขนาดเล็ก และสามารถข้ามเรกคอร์ดที่เสียหาย/ซิงก์ใหม่ได้

วิธีการอัปเดตดัชนี (1998-1999)

• รอบเวลา: ประมาณเดือนละครั้ง
• กระบวนการ:
  1. รอจนถึงช่วงเวลาที่ทราฟฟิกต่ำ
  2. นำ replica บางส่วน offline
  3. คัดลอกดัชนีใหม่ไปยัง replica ที่ offline
  4. เปิด frontend ชุดใหม่ที่ชี้ไปยังดัชนีที่อัปเดตแล้ว และให้รับทราฟฟิกบางส่วน
• กลยุทธ์การใช้ดิสก์ของ index server:
  • พื้นที่รอบนอกของดิสก์ (outer part) ให้แบนด์วิดท์สูงกว่า
  1. (ขณะยังให้บริการดัชนีเดิม) คัดลอกดัชนีใหม่ไปยังครึ่งในของดิสก์ (inner half)
  2. รีสตาร์ตให้ใช้ดัชนีใหม่
  3. ลบดัชนีเดิม
  4. คัดลอกดัชนีใหม่อีกครั้งไปยังครึ่งนอกที่เร็วกว่า (faster half)
  5. ลบดัชนีใหม่ชุดแรกที่คัดลอกไว้ในครึ่งใน
  6. ใช้พื้นที่ว่างในครึ่งในเพื่อสร้างโครงสร้างข้อมูลที่ช่วยเพิ่มประสิทธิภาพ (เช่น Pair cache - คำนวณผลตัดกันของ posting list ล่วงหน้าสำหรับคู่คำค้นที่มักปรากฏร่วมกัน)

การรองรับการเติบโตและการขยายระบบ (1999-2001)

• ในปี '99, '00, '01 ขนาดดัชนีและทราฟฟิกเพิ่มขึ้นอย่างรวดเร็ว (~50 ล้าน → มากกว่า 1 พันล้านหน้า, ทราฟฟิกโต 20% ต่อเดือน + ความร่วมมือกับ Yahoo ทำให้ทราฟฟิกเพิ่มเป็น 2 เท่าในชั่วข้ามคืน เป็นต้น)
• ประสิทธิภาพของ index server กลายเป็นเรื่องสำคัญมาก: ต้องเพิ่มเครื่องอย่างต่อเนื่อง + ต้องปรับปรุงประสิทธิภาพด้วยซอฟต์แวร์ 10-30% ทุกเดือน
• วิธีขยายระบบ: เพิ่ม shard และ replica ให้มากขึ้น
• ข้อสังเกต:
  • เวลาตอบสนองของ shard ได้รับผลจากจำนวนครั้งที่ seek ดิสก์และปริมาณข้อมูลที่ต้องอ่าน
  • จุดที่ยังปรับปรุงประสิทธิภาพได้: การจัดตารางดิสก์ที่ดีขึ้น, การเข้ารหัสดัชนีที่ดีขึ้น

พัฒนาการของเทคนิคการเข้ารหัสดัชนี

• การเข้ารหัสยุคแรก ('97): ฟอร์แมต byte-aligned ที่เรียบง่ายมาก (WORD → [docid+nhits:32b, hit:16b, hit:16b...]) โดย hit คือ ตำแหน่ง + แอตทริบิวต์ (ขนาดฟอนต์, ชื่อเรื่อง ฯลฯ) เพิ่ม skip table สำหรับ posting list ขนาดใหญ่ ถอดรหัสได้ถูก แต่บีบอัดได้ไม่ดี จึงต้องใช้แบนด์วิดท์ดิสก์สูง
• เทคนิคการเข้ารหัสหลากหลายแบบ:
  • ระดับบิต: Unary, Gamma, Rice_k (กรณีพิเศษของ Golomb code), Huffman-Int
  • แบบ byte-aligned: varint (7 บิตต่อไบต์ + continuation bit)
• ฟอร์แมตดัชนีแบบบล็อก: ลดทั้งพื้นที่และการใช้ CPU (~ขนาดลดลง 30%) และเพิ่มความเร็วในการถอดรหัส ใช้บล็อกความยาวแปรผัน Header (delta, length ฯลฯ) + document ID delta (Rice_k) + จำนวน hit (Gamma) + คุณสมบัติของ hit (run-length Huffman) + ตำแหน่ง hit (Huffman-Int)
• ฟอร์แมตดัชนีใหม่ (หลังปี 2004): ใช้ single flat position space และมีโครงสร้างข้อมูลเสริมเพื่อติดตามขอบเขตของเอกสาร posting list เป็นรายการตำแหน่งที่เข้ารหัสแบบ delta ทั้ง ความกะทัดรัด และ ความเร็วในการถอดรหัสที่สูงมาก สำคัญพอ ๆ กัน

ระบบดัชนีในหน่วยความจำ (ต้นปี 2001)

• ที่มา: การขยายแบบ sharding + การเพิ่ม replica ทำให้มีหน่วยความจำรวมมากพอที่จะเก็บสำเนาดัชนีทั้งหมดไว้ในหน่วยความจำได้
• สถาปัตยกรรม: frontend → load balancer (bal) → shard (แต่ละ shard มี replica ของ in-memory index server หลายตัว)
• ข้อดี: throughput เพิ่มขึ้นมาก, latency ลดลงมาก (โดยเฉพาะคิวรีซับซ้อนที่ก่อนหน้านี้ต้องใช้ดิสก์ I/O ระดับ GB เช่น "circle of life")
• ปัญหา:
  • ความแปรปรวน (Variance): จากการใช้เครื่องหลักสิบไปเป็นหลักพัน ทำให้คาดการณ์พฤติกรรมได้ยากขึ้น (เช่น งาน cron แบบสุ่มก่อปัญหา)
  • ความพร้อมใช้งาน (Availability): ข้อมูลดัชนีของเอกสารแต่ละชุดมี replica แค่ 1 ชุดหรือมีน้อย → เกิด "คิวรีแห่งความตาย" (backend ล่มพร้อมกันทั้งหมด), และเมื่อเครื่องล้มจะมีปัญหาความพร้อมใช้งานของข้อมูลดัชนี (โดยเฉพาะเอกสารสำคัญควรมี replication)

การออกแบบระบบและเทคโนโลยีในช่วงหลัง (หลังปี 2004)

• ฮาร์ดแวร์: ดาต้าเซ็นเตอร์ขนาดใหญ่ขึ้น, แร็กที่ออกแบบเอง, เมนบอร์ดระดับ PC, ฮาร์ดแวร์สตอเรจ/เครือข่ายต้นทุนต่ำ, Linux + ซอฟต์แวร์พัฒนาขึ้นเอง
• ดีไซน์การให้บริการ (ฉบับปี 2004): โครงสร้างแบบลำดับชั้น
  • Root server → Parent server หลายตัว → Leaf server หลายตัว (โหลด Repository Shard จาก GFS ผ่าน File Loader)
  • เชื่อมต่อกับ cache server

การเข้ารหัสแบบ Group Varint

• แนวคิด: แก้ปัญหาความไม่มีประสิทธิภาพของการถอดรหัส varint (มี branch/shift/mask จำนวนมาก) โดยจัดจำนวนเต็ม 4 ค่าเป็นหนึ่งกลุ่ม และเข้ารหัสเป็น 5~17 ไบต์
• วิธีการ:
  • รวมแท็ก 2 บิต 4 ตัวที่บอกความยาวไบต์ของแต่ละค่า (1~4 ไบต์) ให้เป็น prefix byte ขนาด 1 ไบต์
  • จากนั้นเก็บ data byte จริงไว้ต่อจาก prefix byte
• การถอดรหัส: อ่าน prefix byte แล้วใช้เป็นดัชนีเพื่อ lookup ตารางที่คำนวณไว้ล่วงหน้า 256 รายการ → ได้ข้อมูล offset และ mask แล้วถอดรหัส 4 ค่าได้พร้อมกัน
• ประสิทธิภาพ: เร็วกว่าวิธีเดิมมาก (Group Varint: ~400M/วินาที, 7-bit Varint: ~180M/วินาที, 30-bit Varint w/ 2-bit len: ~240M/วินาที)

Universal Search (2007)

• ระบบที่แสดงผลแบบผสานรวม ไม่ใช่แค่ผลค้นหาเว็บ แต่รวมข้อมูลหลายประเภท เช่น รูปภาพ ข้อมูลท้องถิ่น ข่าว วิดีโอ บล็อก หนังสือ เป็นต้น
• โหนด super root ส่งคิวรีไปยังระบบค้นหาเฉพาะทางหลายระบบ (vertical search engine) แล้วรวบรวมผลลัพธ์กลับมา

ความท้าทายของการ crawl และทำดัชนีแบบเวลาแฝงต่ำ

• การทำให้อัปเดตสะท้อนผลได้ภายในไม่กี่นาทีเป็นโจทย์ที่ยากมาก
• heuristic สำหรับการ crawl: จะ crawl หน้าไหน
• ระบบ crawl: ต้อง crawl หน้าเว็บได้อย่างรวดเร็ว
• ระบบ indexing: พึ่งพาข้อมูล global เช่น PageRank, anchor text → จึงต้องมี online approximation แบบเรียลไทม์
• ระบบ serving: ต้องพร้อมรับการอัปเดตระหว่างประมวลผลคิวรี (จึงต้องใช้โครงสร้างข้อมูลที่ต่างจากระบบอัปเดตแบบ batch มาก)

ความสำคัญของการทดลองและอินฟราสตรักเจอร์

• ความง่ายในการทดลอง: สำคัญมาก (รอบการทดลองที่เร็ว → ทดลองได้มากขึ้น → ปรับปรุงได้มากขึ้น)
• ประเภทของการทดลอง:
  • การทดลองง่าย: เช่น ปรับน้ำหนักข้อมูลที่มีอยู่
  • การทดลองยาก: ต้องใช้ข้อมูลใหม่ที่ไม่มีในดัชนี production (จึงต้องทำให้การสร้าง/รวมข้อมูลใหม่และการนำไปทดลองทำได้ง่าย)
• อินฟราสตรักเจอร์หลัก:
  • GFS: ระบบไฟล์แบบกระจายขนาดใหญ่
  • MapReduce: ช่วยให้เขียน/รันงานประมวลผลข้อมูลขนาดใหญ่ได้ง่าย (เร่งการสร้างข้อมูลสำหรับดัชนี production และทำการทดลองเฉพาะกิจได้รวดเร็ว)
  • BigTable: ระบบสตอเรจแบบกึ่งโครงสร้าง (semi-structured) (เข้าถึงข้อมูลรายเอกสารแบบออนไลน์และมีประสิทธิภาพ, ให้หลายโปรเซสอัปเดตข้อมูลเอกสารแบบอะซิงโครนัสได้ — สำคัญต่อการลดรอบอัปเดตจากระดับชั่วโมงลงสู่ระดับนาที)

วงจรการทดลองและการปล่อยใช้งาน

1. คิดไอเดียและทดลองแบบออฟไลน์:
   • สร้างข้อมูลด้วย MapReduce, BigTable เป็นต้น
   • รันการทดลองออฟไลน์และตรวจสอบผลลัพธ์ (ชุดคิวรีสำหรับการประเมินโดยมนุษย์, ชุดคิวรีแบบสุ่ม เป็นต้น)
   • ในขั้นนี้ latency/throughput ของ prototype ยังไม่สำคัญ
   • ปรับปรุงซ้ำจากผลการทดลอง
2. ทดลองกับระบบจริง:
   • หากผลออฟไลน์ดี ให้นำไปทดลองกับทราฟฟิกจริงเพียงบางส่วนเล็กมาก (tiny sliver) ของผู้ใช้จริง (ส่วนใหญ่เป็นตัวอย่างแบบสุ่ม บางครั้งเป็นคิวรีบางคลาส)
   • ในขั้นนี้ latency สำคัญกว่า throughput! framework สำหรับการทดลองควรทำงานใกล้เคียงกับ latency ของ production
3. ปรับจูนประสิทธิภาพและปล่อยใช้งาน:
   • หากผลจาก live experiment ดี ให้ปรับจูนหรือ re-implement เพื่อให้รันได้ภายใต้โหลดเต็ม (เช่น precompute ข้อมูลแทนการคำนวณตอน runtime, หรือใช้ค่าประมาณที่ถูกกว่าเมื่อ "ดีพอแล้ว")
   • กระบวนการ rollout สำคัญมาก: ต้องชั่งน้ำหนัก quality vs cost อย่างต่อเนื่อง และสร้างสมดุลระหว่างการปล่อยใช้งานเร็วกับ latency ต่ำ/เสถียรภาพของเว็บไซต์ (จึงต้องอาศัยความร่วมมือที่ดีระหว่างทีมคุณภาพการค้นหาและทีมที่ดูแลประสิทธิภาพ/เสถียรภาพ)

ทิศทางและโจทย์ในอนาคต

• การค้นคืนข้อมูลข้ามภาษา (Cross-Language IR): แปลเอกสารทั้งหมดทั่วโลกให้ค้นได้ในทุกภาษา → ขนาดดัชนีพุ่งสูงและต้นทุนการคำนวณสูง (ต้องปรับปรุงคุณภาพการแปลอย่างต่อเนื่อง และต้องมีระบบขนาดใหญ่เพื่อรองรับ language model ที่ใหญ่และซับซ้อนขึ้น)
• Access Control Lists (ACLs) ภายในระบบค้นคืนข้อมูล: สภาพแวดล้อมที่มีทั้งเอกสารส่วนตัว กึ่งส่วนตัว แชร์วงกว้าง และสาธารณะปะปนกัน (ต้องสร้างระบบที่จัดการ ACL ขนาดต่างกันมากได้อย่างมีประสิทธิภาพ — เอกสารที่แชร์กับ 10 คนและเอกสารที่แชร์กับทั้งโลกย่อมต้องการวิธีที่เหมาะที่สุดต่างกัน และรูปแบบการแชร์อาจเปลี่ยนไปตามเวลา)
• การสร้างระบบ IR ที่มีประสิทธิภาพแบบอัตโนมัติ: ปัจจุบันใช้หลายระบบสำหรับหลายวัตถุประสงค์ (เช่น สำหรับอัปเดตเร็วมาก, สำหรับเอกสารขนาดมหาศาล ฯลฯ) (เป็นไปได้หรือไม่ที่จะพัฒนาระบบเดียวที่เมื่อป้อนพารามิเตอร์แล้วจะสร้างระบบค้นหาที่มีประสิทธิภาพให้ตรงตามข้อกำหนดโดยอัตโนมัติ?)
• การสกัดข้อมูลจากข้อมูลกึ่งโครงสร้าง: ข้อมูลที่มี semantic label ชัดเจนมีน้อยมาก แต่ข้อมูลกึ่งโครงสร้างอย่างตารางและฟอร์มมีอยู่มาก (จึงต้องมีอัลกอริทึม/เทคนิคที่ดีขึ้นสำหรับสกัดข้อมูลมีโครงสร้างจากแหล่งข้อมูลไม่มีโครงสร้าง/กึ่งโครงสร้าง — แม้จะมี noise มาก แต่ใช้ประโยชน์จากความซ้ำซ้อน และสามารถเชื่อมโยง/รวม/สรุปข้อมูลจากหลายแหล่งได้)

บทสรุป

• การออกแบบและสร้างระบบค้นคืนข้อมูลขนาดใหญ่เป็นงานที่ท้าทายและน่าสนุก
• เทคโนโลยีการค้นหาแบบใหม่มักต้องการการออกแบบระบบแบบใหม่เช่นกัน