কেস স্টাডি: সার্চ অটোকমপ্লিট সিস্টেম ডিজাইন করা

১ · রিকোয়ারমেন্ট

একটি ৪-অক্ষরের সার্চ টার্মে গড়ে ৪টি কিস্ট্রোক-রিকোয়েস্ট হয় — তাই এই সিস্টেমের প্রকৃত QPS আসলে ব্যবহারকারী সংখ্যার চেয়ে বহুগুণ বেশি (L02-এর মতো QPS হিসাব করার সময় "প্রতি সার্চে একাধিক রিকোয়েস্ট" এই ফ্যাক্টরটা মাথায় রাখা জরুরি)। আর প্রতিটি রিকোয়েস্টের জবাব একটি মানুষ সরাসরি টাইপ করতে করতে দেখছে — তাই লেটেন্সি বাজেট এই কোর্সের অন্য যেকোনো সিস্টেমের চেয়ে কড়া।

২ · মূল স্ট্রাকচার — প্রি-কম্পিউটেড টপ-K সহ Trie

DSA কোর্স থেকে পরিচিত TrieTrie (Prefix Tree)একটি ট্রি ডেটা স্ট্রাকচার যেখানে প্রতিটি পাথ (রুট থেকে একটি নোড পর্যন্ত) একটি স্ট্রিং প্রিফিক্স প্রতিনিধিত্ব করে — একই প্রিফিক্সের সব শব্দ একই পাথ শেয়ার করে। — একটি ট্রি যেখানে রুট থেকে যেকোনো নোড পর্যন্ত পথ একটি প্রিফিক্স বোঝায়। সাধারণ Trie শুধু "এই প্রিফিক্স দিয়ে কোন কোন শব্দ শুরু হয়" জানে, কিন্তু অটোকমপ্লিটের জন্য প্রতিটি অনুসন্ধানে সেই সব শব্দ জনপ্রিয়তা অনুযায়ী র‍্যাঙ্ক করা লাগবে — যা প্রতি-কিস্ট্রোকে করলে বেশি ধীর।

সমাধান: প্রতিটি Trie নোডে আগে থেকেই সেই প্রিফিক্সের টপ-K সবচেয়ে জনপ্রিয় সম্পূর্ণ শব্দের একটি ছোট তালিকা সংরক্ষণ করা হয় — বিল্ড টাইমে (বা পর্যায়ক্রমিক ব্যাচ রিফ্রেশে)। একটি লুকআপ তখন শুধু টাইপ করা প্রিফিক্স অনুসরণ করে নিচে নামা এবং সেই নোডের প্রি-কম্পিউটেড লিস্ট ফেরত দেওয়া — কোনো লাইভ স্ক্যান বা সর্টিং নেই।

৩ · ডিপ ডাইভ — বাস্তবায়ন

নিচের কোড একটি ছোট Trie বানায় যেখানে প্রতিটি নোডে সর্বোচ্চ ৩টি (টপ-৩) কমপ্লিশন প্রি-কম্পিউটেড থাকে। শব্দ যোগ করার সময় (insert) সেই শব্দের পাথের প্রতিটি নোডে টপ-৩ তালিকা আপডেট হয়; খোঁজার সময় (search) শুধু সেই প্রি-কম্পিউটেড তালিকা ফেরত দেওয়া হয়।

TOP_K = 3

class TrieNode:
    def __init__(self):
        self.children = {}
        self.top_completions = []   # [(word, popularity), ...] — সাজানো, সর্বোচ্চ TOP_K

def _update_top_k(node, word, popularity):
    # আগের এন্ট্রি (যদি থাকে) সরিয়ে নতুন করে যোগ করে জনপ্রিয়তা অনুযায়ী সাজানো
    node.top_completions = [(w, p) for w, p in node.top_completions if w != word]
    node.top_completions.append((word, popularity))
    node.top_completions.sort(key=lambda pair: -pair[1])
    node.top_completions = node.top_completions[:TOP_K]

def insert(root, word, popularity):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, TrieNode())
        _update_top_k(node, word, popularity)   # পাথের প্রতিটি প্রিফিক্স নোডে আপডেট

def search(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children:
            return []
        node = node.children[ch]
    return node.top_completions

# নমুনা শব্দ ও জনপ্রিয়তা স্কোর (কল্পিত সার্চ-লগ থেকে আসতে পারত)
sample_words = [
    ("cat", 50), ("car", 80), ("card", 65), ("care", 40), ("cart", 30),
    ("dog", 90), ("door", 20), ("dorm", 10),
]

root = TrieNode()
for word, popularity in sample_words:
    insert(root, word, popularity)

for prefix in ["ca", "car", "do"]:
    results = search(root, prefix)
    print(f"prefix '{prefix}' -> {results}")

৪ · ট্রেড-অফ

প্রি-কম্পিউটেশন লুকআপকে অতি-দ্রুত করে, কিন্তু ফলাফল সবসময় সাম্প্রতিকতম নাও হতে পারে — একটি নতুন ট্রেন্ডিং সার্চ টার্ম টপ-K লিস্টে ঢুকতে পরবর্তী ব্যাচ রিফ্রেশ (L24) পর্যন্ত অপেক্ষা করতে হয়। আরও বেশি TOP_K রাখলে ফলাফল বৈচিত্র্যময় হয় কিন্তু প্রতিটি নোডের মেমরি খরচ বাড়ে — লক্ষ লক্ষ নোডের একটি Trie-তে এটি গুরুত্বপূর্ণ। যেহেতু পুরো Trie সাধারণত প্রতিটি স্টেটলেস সার্ভারে (L12) ইন-মেমরি রেপ্লিকেটেড থাকে (এই ডেটাসেট তুলনামূলক ছোট এবং রিড-হেভি, ঠিক L19-এর ক্যাশিং নীতির মতো), নতুন কোনো সার্ভার যোগ করা সহজ — কিন্তু প্রতিটি সার্ভারকে Trie-এর একটি সম্পূর্ণ কপি রাখতে হয়, যা ছোট থাকা অবস্থাতেই সম্ভব।