ออกแบบ Search Autocomplete

Autocomplete หรือ Typeahead ให้ข้อเสนอแนะแบบ Real-time ขณะผู้ใช้พิมพ์ใน Search Box ระบบต้องส่งมอบ Top-k ข้อเสนอที่เกี่ยวข้องและนิยมตามข้อมูล Historical Query

บทนำ

Autocomplete หรือ Typeahead ให้ข้อเสนอแนะแบบ Real-time ขณะผู้ใช้พิมพ์ใน Search Box

Key Features

• แสดงสูงสุด 5 ผลลัพธ์ Autocomplete
• อิงตาม Query Popularity (ความถี่)
• รองรับเฉพาะ ตัวอักษรพิมพ์เล็กภาษาอังกฤษ
• Response Time < 100 ms

ข้อกำหนด

• 10 ล้าน DAU
• Peak QPS: 48,000
• การเติบโตของข้อมูล: 0.4 GB/วัน

High-Level Design

Services หลัก

1. Data Gathering Service: รวบรวม User Queries และ Aggregate สำหรับ Frequency Analysis
2. Query Service: ให้ Top-k ข้อเสนอแนะตาม Input ของผู้ใช้

Trie Data Structure

Trie เป็นโครงสร้างข้อมูลแบบ Tree ใช้จัดเก็บและดึง Query Strings อย่างมีประสิทธิภาพ

Key Features

• Compact Storage: แทน Prefixes แบบ Hierarchical เพื่อลดความซ้ำซ้อน
• Frequency Information: เก็บ Popularity ของ Queries ที่แต่ละ Node

ขั้นตอนการได้ Top-k Queries

1. หา Prefix
2. Traverse Subtree จาก Prefix Node เพื่อดึง Valid Children ทั้งหมด
3. เรียง Children และดึง Top-k

Optimizations

• Cache Top-k Queries: ที่แต่ละ Node เพื่อเพิ่มความเร็วในการดึง
• Limit Prefix Length: จำกัดความยาว Prefix เพื่อลด Search Space
• AJAX Requests: ใช้ Asynchronous Requests สำหรับ Responses แบบ Real-time
• Browser Caching: เก็บ Autocomplete Results ใน Browser Cache

เนื้อหานี้อ้างอิงจาก ByteByteGo - System Design Interview - An Insider's Guide