להבין את mapReduce מהשורש

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

פונקציות מסדר גבוה

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

היכולת הזו קיימת לא רק בשפות פונקציונאליות טהורות, והיא מאפשרת דברים מאוד מעניינים ביכולת לקחת כמה פונקציות קטנות ולהרכיב מהן פונקציה גדולה יותר, 'לעטוף' פונקציות וכו'. בפייתון ורובי זה נקרא lambda functions, אנחנו נראה דוגמאות בשפת groovy שם זה נקרא closures (אגב, בג'אווה מדברים על תוספת כזו כבר הרבה זמן, אבל בינתיים זה לא קרה):

//first class function

def add = {a,b -> return a+b}

/*the same as

def add(a,b){

return a+b

}

*/

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

דוגמא אחרת היא איטרציה על רשומה. במקום זה:

for (elem in list) println elem

אפשר לכתוב

list.each{println it}

שימו לב, בדוגמא האחרונה לא נתתי שם לארגומנט אלא עשיתי שימוש בברירת מחדל it.

מה זה נותן?

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

def add = {sum, elem -> sum += elem}

def sum=0

list.each{sum=add sum it}

הקוד מסכם את איברי הרשימה.

למה זה מעניין? כי בשורה הבאה אני הופך את זה לגנרי:

def reduce = {list, sum, func -> list.each{sum=func(sum,it)};sum}

println reduce(list, 0, add)

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

רוצים כפל במקום חיבור? אין בעיה:

def mult = {sum, elem -> sum *= elem}

println reduce(list, 1, mult)

רוצים רקורסיה? אין צורך לגעת באיטרציה, רק להרכיב פונקציות:

println reduce(list, reduce(list, 0,add), add)

אגב, אין צורך לכתוב לבד את פונקצית reduce, בשפת groovy היא נקראת inject.

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

Reduce – צמצום נתונים לערך בודד על פי פונ' אגרגציה. לדוגמא סיכום אברים.

Map – יצירת מבנה נתונים מקביל בו כל ערך הוא תוצאה של הפעלת פונקצית הארגומנט על הערך המקורי.

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

אחד הדברים שזה מאפשר זה חסכון של boilerplate או קוד חוזר. דוגמא שאני אוהב היא מימוש פונקציונאלי של quicksort:

def sort(list) {

    if (list.isEmpty()) return list

    def pivot = list[0]

    sort(list.findAll{it < pivot}) + pivot + sort(list.findAll{it > pivot})

}

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

חישוב פונקציונאלי מקבילי

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

Def list = [1,2,3,4,5,6,7,8]

Def total = 0

For (number in list) total +=number

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

כדי לשפר את התהליך, קונים עוד 3 מחשבים, ומציעים לעבוד בצורה הבאה:

דקה 1: כל צמד מספרים מחובר על ידי אחד המחשבים

דקה 2: תוצאות 1, 2 מחוברות על ידי מחשב 1 והזוג האחר על ידי מחשב 2

דקה 3: שני הסכומים מחוברים במחשב 1

סה"כ במקום 8 דקות, לקח לנו 3 (לוג 2 של 8).

המימוש כמובן דרש כתיבת קוד שעוסק בתקשורת בין המכונות, תזמון, טיפול בכשלים וכו'.

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

Reduce(list, 0, {sum, elem->sum+=elem})

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

אז מה זה mapReduce?

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

Sum(1,2,3,4)=sum(sum(1,2),sum(3,4))

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

Freq(1,2,2,1,3,3,1,4,4,1,5,5,1,2,2) != Freq(freq(1,2,2),freq(1,3,3),freq(1,4,4), freq(1,5,5), freq(1,2,2))

כיוון ש:

Freq(1,2,2,1,3,3,1,4,4,1,5,5,1,2,2)=1

ואילו:

Freq(freq(1,2,2),freq(1,3,3),freq(1,4,4), freq(1,5,5), freq(1,2,2))=freq(2,3,4,5,2)=2

כלומר לא כל בעיה ניתנת לחלוקה ומקבול בצורה 'טבעית'.

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

שלב המיפוי היה נותן תוצאה כזו (צמצום כל סגמנט נתונים למפת שכיחויות):

(1:1, 2:2),(1:1, 3:2), (1:1, 4:2), (1:1, 5:2), (1,1, 2:2)

ושלב הצמצום (אגרגציה של כל המפות):

(1:5, 2:4 ,3:2, 4:2, 5:2)

וקיבלנו תוצאה נכונה – 1 הוא המספר הכי שכיח.

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

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

2 מחשבות על “להבין את mapReduce מהשורש

  1. פינגבק: GPars – מערכים מקביליים | אותיות ומספרים

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s