מפה וצמצם - MapReduce

בקורס באלגוריתמים, סיבוכיות או מבנה נתונים למדנו על כל מיני שיטות לייעל את החישובים שלנו, במו איך למיין מערך ב (nlog(n או איך לעשות חיפוש בינרי, או איך לעשות שליפה ב (1)O בממוצע.
כל אלה, כבודם במקומם מונח ויש להם חשיבות ראשונה במעלה אצל כל מהנדס תוכנה.
אבל החיים מלמדים אותנו שלפעמים לא די בכך. לפעמים אנו נתקלים במשימות חישוביות שלא ניתן למצוא להן פתרון יעיל יותר וכאשר צריך לעשות חישוב על נתונים מרובים זה יכול לקחת שנים.
אז למה לדבר בחשאיות? הבה נפצח בדוגמה הבאה: נתונה קבוצה של מסמכים (עמודי אינטרנט לדוגמא) ועליכם לסרוק את המסמכים ולספור עבור כל מילה, כמה פעמים היא מופיעה בסך כל המסמכים, למשל המלה "ראשון" כמה פעמים היא נמצאת בכל המסמכים ביחד. אז מה עושים? כנראה שאין דרך טובה יותר מאשר פשוט לסרוק את כולם ולספור אחד אחד. כן, אין מה לעשות. הסיבוכיות של דבר כזה היא לא רעה, (O(n אם יש קצת מזל, אבל במחשבה שניה, אם אוסף המסמכים הוא "כל האינטרנט" אז יש לנו בעיה, יוסטון. איך אפשר לסרוק את כל המסמכים של האינטרנט? עד שנספיק לסרוק את כל מה שאנחנו חושבים שיש באינטרנט היום, כשנסיים כבר חצי מהאינטרנט ישתנה.
אז מה עושים? ממקבלים!
הפתרון הוא מקבול הבעיה. מחלקים את העבודה בין מאות או אלפי מחשבים, כל אחד עושה חלק קטן מהעבודה ובסופו של דבר מדווח תוצאות לבסיס האם, אשר עושה סיכום ומחזיר תשובה.
כבר בפוסט הקודם אמרתי שבגוגל אוהבים למקבל דברים, אז הנה עוד דוגמה למקבול של העניינים.
רגע, רגע, רגע, רק שניה אחת, מה אתה בא לטעון ש"בגוגל המציאו את המיקבול"? וודאי שלא, בגוגל לא המציאו את המקבול, ברור שעשו את זה בעולם המחשבים עוד הרבה לפני גוגל, עוד כשלארי וסרגיי היו בשא"שים , אבל מה שכן המציאו בגוגל זו שיטה מאוד פשוטה למקבל תוכניות.
כל אחד יכול למקבל, אבל מי שאי פעם יצא לו לכתוב תוכנית שרצה על cluster ענק של מחשבים, מבין שיש בזה לא מעט בעיות. הבעיה הראשונה היא למצוא את האלגוריתם המתאים כך שהעבודה תחולק באופן יעיל, שלא יקרה שיש מכונות שטוחנות CPU בזמן שאחרות סתם יושבות ומחכות. הבעיה השניה היא תקשורת מעל הרשת - לא להעמיס את הרשת יותר מידי כדי שלא יהיו צווארי בקבוק, לא לאבד נתונים ברשת, לשלוח את מה שצריך, אבל רק את מה שצריך, לכווץ את הנתונים לפני השליחה ועוד. ומה עושים אם אחד המחשבים מתרסק? בדרך כלל כשכותבים תכנה למחשב בודד ניתן להתחמק מהבעיה עם התרוץ של אם המחשב התרסק כנראה שיש למשתמש בעיות יותר דחופות כעת ובכלל, מה הסיכוי שזה יקרה? אולם כאשר מריצים תוכנית על אלפי מחשבים יש סיכוי גבוה מאוד שלפחות אחד הדיסקים יתרסק או שסתם איזשהו מחשב יקבל חום וצרבת. אז איך יודעים שאחד מהם מת ולא מחכים לו לעד? ואיך משחזרים את הנתונים שלו? כל אלה ועוד הן בעיות אמיתיות ולא פשוטות שכל מי שכתב תוכנה שרצה באופן מבוזר צריך לקחת בחשבון, ובלי שום קשר בכלל למה צריכה הותכנה לעשות, כלומר האם צריך לספור מילים במסמכים או לעשות משהו אחר. ולמי פתרונים?
בגוגל הבינו שיש פה איזושהי בעיה כללית שדורשת פתרון כללי ואבסטרקטי ולכן המציאו את הפתרון שנקרא MapReduce או בעברית מפה (מלשון למפות) וצמצם.
הפתרון של גוגל הוא פלטפורמה לכתיבת תכניות מקביליות. הפלטפורמה דואגת לפתור לך את כל הבעיות הכלליות, דוגמת תקשורת, סנכרון, מחשבים שנופלים שחזור אינפורמציה, נסיון חוזר ועוד, ומה שאתה צריך לעשות זה רק להגדיר את הבעיה הספציפית שלך שאתה רוצה לפתור, ובמקרה שלנו ספירת מילים. איך עושים את זה? מסתבר שניתן למדל בעיות כאלה לשני שלבים: שלב המיפוי ושלב הצמצום. בדוגמה שלנו שלב המיפוי יהיה כדלהלנצ'יק: חלק את כל המסמכים שווה בשווה בין כל המחשבים. כל מחשב יספור כמה פעמים מופיעה כל מילה. זהו, זה כל המיפוי. עכשיו בשלב הצמצום כל אחד מדווח על ממצאיו ויש מישהו שמסכם את המספרים. זה כל שלב הצמצום. זה כל כך פשוט שאתם בטח שואלים את עצמכם, רגע, נראה שחסר כאן משהו, אבל לא, לא חסר כאן כלום, זה כל הסיפור וזו הגאונות שבעניין, הפלטפורמה דואגת לכל העניינים מסביב ומה שנותר לכם לעשות זה רק להגדיר את לב הבעיה.

בואו נדבר תכל"ס - באיזו שפה כותבים דבר כזה? זה פשוט - ב ++C. רוצים דוגמא?


#include "mapreduce/mapreduce.h"
// User's map function
class WordCounter : public Mapper {
public:
 virtual void Map(const MapInput& input) {
  const string& text = input.value();
  const int n = text.size();
  for (int i = 0; i < n; ) {
   // Skip past leading whitespace
   while ((i < n) && isspace(text[i]))
   i++;
   // Find word end
   int start = i;
   while ((i < n) && !isspace(text[i]))
   i++;
   if (start < i)
   Emit(text.substr(start,i-start),"1");
  }
 }
};
REGISTER_MAPPER(WordCounter);

// User's reduce function
class Adder : public Reducer {
 virtual void Reduce(ReduceInput* input) {
  // Iterate over all entries with the
  // same key and add the values
  int64 value = 0;
  while (!input->done()) {
   value += StringToInt(input->value());
   input->NextValue();
  }
  // Emit sum for input->key()
  Emit(IntToString(value));
 }
};
REGISTER_REDUCER(Adder);

int main(int argc, char** argv) {
 ParseCommandLineFlags(argc, argv);
 MapReduceSpecification spec;
 // Store list of input files into "spec"
 for (int i = 1; i < argc; i++) {
  MapReduceInput* input = spec.add_input();
  input->set_format("text");
  input->set_filepattern(argv[i]);
  input->set_mapper_class("WordCounter");
 }
 // Specify the output files:
 // /gfs/test/freq-00000-of-00100
 // /gfs/test/freq-00001-of-00100
 // ...
 MapReduceOutput* out = spec.output();
 out->set_filebase("/gfs/test/freq");
 out->set_num_tasks(100);
 out->set_format("text");
 out->set_reducer_class("Adder");
 // Optional: do partial sums within map
 // tasks to save network bandwidth
 out->set_combiner_class("Adder");
 // Tuning parameters: use at most 2000
 // machines and 100 MB of memory per task
 spec.set_machines(2000);
 spec.set_map_megabytes(100);
 spec.set_reduce_megabytes(100);
 // Now run it
 MapReduceResult result;
 if (!MapReduce(spec, &result)) abort();
 // Done: 'result' structure contains info
 // about counters, time taken, number of
 // machines used, etc.
 return 0;
}


בהתחלה מגדירים את ה Mapper ולאחר מכן את ה Reducer וכותבים main קטן שמחלק את העבודה ביניהם ומתחיל את כל התהליך.

כל מה שכתבתי כאן אינו סוד מדינה. תוכלו למצוא מאמר מלא עם עוד הרבה הסברים כאן: http://labs.google.com/papers/mapreduce.html