איך מעצבים השלמה אוטומטית בחיפוש - מקרה בוחן

מתחילים להקליד במנוע חיפוש, ולפני שסיימתם מילה שלמה כבר מופיעות הצעות. תכונה כזאת נראית קטנה, אבל היא דורשת תשובה תוך עשרות מילישניות בכל הקשה, ובקנה מידה של מיליוני משתמשים בו זמנית זה אילוץ עיצוב אמיתי. בואו נראה איך בונים אותה.

שלב 1 - הדרישה הבסיסית והאילוץ הקשה

הדרישה נשמעת פשוטה - בהינתן קידומת שהמשתמש הקליד, להחזיר את ההשלמות הכי סבירות. האילוץ הקשה הוא הזמן - כל הקשה במקלדת שולחת בקשה חדשה, ואם התשובה לא חוזרת כמעט מיד, החוויה מרגישה איטית וטרחנית. זה אומר שכל פתרון שדורש סריקה של כמות גדולה של נתונים בזמן אמת פשוט לא יעבוד - צריך משהו שכבר "יודע" את התשובה כמעט מראש.

שלב 2 - מבנה הנתונים - Trie

מבנה הנתונים הקלאסי לבעיה הזו הוא Trie, עץ קידומות. כל צומת בעץ מייצג תו בודד, והמסלול משורש העץ ועד לצומת מסוים מייצג מילה או קידומת. כדי למצוא את כל המילים שמתחילות בקידומת מסוימת, פשוט יורדים בעץ לפי התווים של הקידומת, ואז אוספים את כל המילים שנמצאות מתחת לצומת הזה. זה יעיל בהרבה מסריקת רשימה שטוחה של מילים, כי הזמן שלוקח תלוי באורך הקידומת, לא בכמות המילים הכוללת במערכת.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.top_suggestions = []  # מוכן מראש

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def search_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return node.top_suggestions

שלב 3 - חישוב מראש, לא בזמן חיפוש

הטריק המרכזי בעיצוב המערכת הוא שהדירוג של ההצעות לא מחושב ברגע החיפוש - הוא מחושב מראש, ברקע. לכל צומת ב-Trie שומרים לא רק את המילים האפשריות, אלא רשימה קצרה וממוינת מראש של ההצעות הכי פופולריות תחת הקידומת הזאת, על סמך היסטוריית חיפושים של כלל המשתמשים. כשמשתמש מקליד, השרת פשוט יורד ל-Trie ומחזיר את הרשימה המוכנה, בלי לחשב שום דירוג בזמן אמת. זה בדיוק אותו עיקרון שראינו במקרה הבוחן על פיד חברתי - להעביר את העבודה הכבדה משלב הקריאה לשלב שקורה מראש.

שלב 4 - עדכון הפופולריות לאורך זמן

חיפושים משתנים - מגמות עולות ויורדות, אירועים חדשים הופכים פופולריים בפתאומיות. המערכת צריכה לעדכן את הדירוג ברקע, בדרך כלל בעיבוד אצווה שרץ כל כמה שעות או כל יום, שסופר מחדש חיפושים אחרונים ובונה גרסה מעודכנת של ה-Trie. לרוב בונים את הגרסה החדשה בנפרד, ומחליפים אותה בבת אחת רק כשהיא מוכנה במלואה - כדי לא להציג משתמשים תוצאות חלקיות באמצע עדכון.

שלב 5 - התאמה אישית והקשר

חיפוש טוב לא מציע רק את הפופולרי ביותר בכלל, אלא לוקח בחשבון גם הקשר - מיקום גיאוגרפי של המשתמש, היסטוריית החיפושים האישית שלו, ולפעמים גם שעה ביום. זה מוסיף שכבה נוספת - במקום Trie גלובלי אחד, יכולים להיות כמה שכבות שמשלבות תוצאה כללית פופולרית עם התאמה אישית קלה, שמחושבת ברגע הבקשה על בסיס מידע קטן ומהיר לגישה, כמו מיקום המשתמש הנוכחי.

שלב 6 - קנה מידה - חלוקה בין שרתים

כשה-Trie גדול מדי מכדי להיכנס לזיכרון של שרת יחיד, מחלקים אותו - למשל, לפי האות הראשונה של הקידומת, כל שרת אחראי על טווח אותיות מסוים. בקשה עם קידומת ש-ל מנותבת לשרת שאחראי על האות ש, וכל שרת מחזיק בזיכרון רק את החלק שלו. זו טכניקת sharding בסיסית שמאפשרת להמשיך לגדול גם כשמבנה הנתונים כולו כבר לא נכנס למחשב יחיד.

מקרה הבוחן הזה מראה יפה איך מבנה נתונים קלאסי מתחום מדעי המחשב - Trie - הופך לרכיב מרכזי בעיצוב מערכות אמיתי בקנה מידה גדול. בקורס ארכיטקטורת תוכנה שלנו עוברים על מקרי בוחן דומים שמחברים תיאוריה לעיצוב מעשי.

התלבטתם איך לבנות חיפוש מהיר בפרויקט שלכם? הצטרפו לקהילה בדיסקורד ותשתפו את הגישה שבחרתם.

לסיכום

השלמה אוטומטית בחיפוש נשענת על מבנה נתונים ייעודי - Trie - שמאפשר איתור מהיר של כל המילים תחת קידומת נתונה, ועל עיקרון מרכזי של חישוב הדירוג מראש ברקע, לא בזמן החיפוש עצמו. מדרגיות מגיעה מחלוקת ה-Trie בין שרתים, וחוויית משתמש טובה יותר מגיעה מהוספת שכבת התאמה אישית קלה מעל הבסיס הפופולרי המשותף.