איך מעצבים אפליקציית שיתוף נסיעות כמו אובר - מקרה בוחן

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

שלב 1 - למה חיפוש מרחק פשוט לא עובד

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

שלב 2 - אינדקס גיאוגרפי - geohashing

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

שלב 3 - עדכון מיקום מתמיד

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

שלב 4 - תהליך ההתאמה בין נוסע לנהג

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

שלב 5 - מעקב אחרי נסיעה פעילה

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

שלב 6 - תמחור דינמי ועקביות באזורי ביקוש

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

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

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

לסיכום

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