BFS מול DFS במערכות Crawler: למה אסטרטגיית הסריקה משנה

מבוא: למה אסטרטגיית סריקה היא החלטה קריטית?

כשאנחנו בונים מערכת Crawler - כלומר תוכנה שעוברת על אתר שלם, נכנסת לכל הקישורים ואוספת מידע - אנחנו למעשה מבצעים מעבר על גרף (Graph). כל עמוד הוא צומת (Node), וכל קישור פנימי הוא קשת (Edge) שמחברת בין שני צמתים. הבעיה היא שהגרף הזה יכול להיות ענק - עשרות אלפי עמודים, עם קישורים מעגליים, עומק לא צפוי, ומגבלות זיכרון וזמן.

לכן, לפני שמתחילים את הסריקה, צריך לבחור את אסטרטגיית המעבר - האלגוריתם שקובע באיזה סדר נבקר בעמודים. הבחירה הזו לא טכנית בלבד: היא משפיעה על אילו עמודים ייסרקו ראשונים, כמה זיכרון יידרש, איך נוכל לעצור בעומק מסוים, ומה המשתמש יראה בדוח בסיום. שתי האסטרטגיות הנפוצות ביותר הן BFS (Breadth First Search) ו-DFS (Depth First Search).

הרעיון הבסיסי: גרף של קישורים

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

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

BFS - סריקה לרוחב (Breadth First Search)

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

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

הכלי המרכזי שמאפשר את ההתנהגות הזו הוא תור (Queue)- מבנה נתונים שעובד לפי עקרון FIFO (First In, First Out). הסורק מוסיף כתובות חדשות לסוף התור ושולף תמיד מהראש שלו. כך, כתובות שהתגלו מוקדם (באותה רמה) מטופלות לפני כתובות שהתגלו מאוחר יותר (ברמה הבאה). זה בדיוק מה שיוצר את ההתנהגות של "שכבה אחרי שכבה".

DFS - סריקה לעומק (Depth First Search)

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

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

המימוש משתמש ב-מחסנית (Stack) שעובדת לפי עקרון LIFO (Last In, First Out), או לחלופין ברקורסיה. ההבדל מ-BFS הוא קטן לכאורה: במקום לשלוף את הכתובת הוותיקה ביותר, שולפים את החדשה ביותר. אבל הוא משנה לחלוטין את סדר הסריקה ואת ההתנהגות של המערכת.

ההבדלים המעשיים: מה באמת חשוב?

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

• סדר הכיסוי: ב-BFS, תוך זמן קצר יש לנו תמונה רחבה של האתר - סרקנו את דף הבית ואת כל העמודים העיקריים שהוא מקשר אליהם. ב-DFS, ייתכן שנתקע בענף אחד לזמן רב (נגיד כל קטגוריית הבלוג), ולא נדע בכלל שיש קטגוריות אחרות עד שנסיים.
• שליטה בעומק: ב-BFS קל מאוד לעצור בעומק מסוים - פשוט לא מוסיפים לתור כתובות שהעומק שלהן עובר את הסף. ב-DFS זה אפשרי, אבל פחות טבעי, כי הסורק לא יודע בזמן אמת שהוא עמוק מדי ביחס לכל הענפים האחרים.
• צריכת זיכרון: ב-BFS, התור יכול להתפוצץ באתרים רחבים - דמיינו דף הבית שמפנה ל-10,000 מוצרים. כל 10,000 הכתובות ייכנסו לתור לפני שנעבור הלאה. ב-DFS, המחסנית נוטה להיות קטנה יותר (פרופורציונלית לעומק, לא לרוחב), אבל אם הגרף עמוק מאוד עלולה להיות חריגה של המחסנית בעבודה רקורסיבית.
• חשיבות העמודים שנסרקים קודם: במבנה הקלאסי של אתר, עמודים שקרובים לדף הבית הם בדרך כלל החשובים ביותר - קטגוריות ראשיות, דפי שירות מרכזיים, פרסומים עדכניים. BFS מבטיח שהם ייסרקו ראשונים, גם אם הסריקה נקטעת באמצע.
• מקביליות:BFS מתאים בצורה טבעית לעיבוד מקבילי (Batch Processing). במקום לטפל בכתובת אחת כל פעם, אפשר לקחת 10 או 20 כתובות מהתור בבת אחת ולסרוק אותן במקביל. ב-DFS, עצם הרעיון של "לצלול בענף אחד" הרבה פחות מתאים לעיבוד מקבילי.

אז מתי כן נרצה להשתמש ב-DFS?

למרות שהמאמר עד כה נשמע כאילו BFS עדיף תמיד, יש תרחישים שבהם DFS הוא הבחירה הנכונה. DFS מצוין כאשר:

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

איך Greadme פועלת: BFS עם בקרת עומק

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

למה זה חשוב במערכת Audit:

• העמודים החשובים נסרקים ראשונים: אם משתמש מריץ Crawl Scan על אתר של 500 עמודים, הוא מצפה לראות שהעמודים המרכזיים - דף הבית, הקטגוריות הראשיות, דפי השירות - נבדקו מיד ולא נשארו לסוף. BFS מספק את זה באופן טבעי.
• עצירה במקסימום עומק נשלט:לכל בדיקה יש תקרת עומק (למשל 3 רמות מדף הבית). עם BFS, העצירה היא פשוט "אל תוסיף לתור כתובות שהעומק שלהן עובר את הגבול" - בלי סיבוכי רקורסיה ובלי סכנה לחריגה מהעומק.
• אצוות (Batches) לעיבוד מקבילי: במקום לסרוק עמוד אחד בכל פעם, ניתן לקחת אצווה מהתור ולסרוק כמה עמודים במקביל. זה חוסך זמן משמעותי באתרים גדולים, ומנצל יעילות מלאה של משאבי השרת - משהו שאפשרי כמעט רק ב-BFS.
• מעקב התקדמות משמעותי:בגלל ש-BFS סורק "שכבה אחרי שכבה", ניתן להציג למשתמש אחוז התקדמות הגיוני יחסית למבנה האתר.

אם תרצו להעמיק בפרטים של מערכת ה-Audit של Greadme וכיצד Crawl Scan פועל בפועל, כתבתי על כך מאמר נפרד - מדריך מקיף לשימוש ב-Greadme.

סיבוכיות זמן וזיכרון

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

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

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

סיכום

BFS ו-DFS הם שני אלגוריתמים בסיסיים לסריקת גרפים, וההבדל ביניהם הוא לא רק טכני - הוא מעצב את ההתנהגות של המערכת שלכם. הכלל הפשוט ביותר לזכור: BFS משתמש בתור (Queue, FIFO) וסורק שכבה אחרי שכבה, DFS משתמש במחסנית (Stack, LIFO) וצולל עמוק לענף אחד לפני שחוזר.

במערכות Crawler, ברוב המקרים BFS הוא הבחירה המועדפת: הוא סורק קודם את העמודים החשובים ביותר (הקרובים לדף הבית), מאפשר בקרת עומק מדויקת, ומתאים לעיבוד מקבילי. זו בדיוק הסיבה ש-Greadme בחרה במבנה הזה לסריקת אתרים - כדי להבטיח שהמשתמשים יקבלו תמונה מלאה ומשמעותית של האתר שלהם, ולא רק של ענף אחד שהתמזל.

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