هل MapReduce شكل واحد من أشكال التماس الاستمرار (CPS)؟

Question

كما يقول العنوان. كنت أقرأ مهووس لغة أخرى: نمط التماس الاستمرارية وكنت أتساءل نوعًا ما إذا كان يمكن تصنيف MapReduce على أنه شكل واحد من أشكال نمط التماس المستمر AKA CPS.

أنا أتساءل أيضًا كيف يمكن أن تستخدم CPS أكثر من جهاز كمبيوتر لإجراء حساب معقد. ربما يجعل CPS من السهل العمل مع نموذج الممثل.

Answer 1

أود أن أقول إنهم متناقضون. من الواضح أن MapReduce يفسح المجال للتوزيع ، حيث يمكن لـ MAP القيام بمهام فرعية بشكل مستقل. مع CPS ، تكتب وظيفة متكررة حيث تنتظر كل مكالمة في حالة أصغر للعودة.

أعتقد أن CPS هي واحدة من أساليب البرمجة التي يصفها Guy Steele بأنها أشياء نحتاج إلى تفوقها وفرحها ، في حديثه مستقبل الموازي: ما المبرمج الذي يجب فعله؟

Answer 2

لن أقول ذلك. تقوم MapReduce بتنفيذ وظائف محددة من قبل المستخدم ، ولكن هذه معروفة باسم "عمليات الاسترجاعات". أعتقد أن CPS هو مفهوم مجردة للغاية يستخدم عادة لنمذجة سلوك مفاهيم معروفة مثل الوظائف ، والكوروتين ، وعمليات الاسترجاعات والحلقات. بشكل عام لا يستخدم مباشرة.

ثم مرة أخرى ، قد أكون مربكا مع الاستمرارية نفسها. أنا لست خبيرًا في أي واحد.

Answer 3

يستفيد كل من CPS و MapReduce من وظائف الترتيب الأعلى. هذا يعني أن كلاهما ينطوي على وظائف تتخذ وظائف كوسائط.

في حالة CPS لديك وظيفة (تسمى استمرار) مع حجة تقول ما يجب القيام به مع النتيجة. عادة (ولكن ليس دائمًا) يتم استخدام الاستمرار مرة واحدة. إنها وظيفة تحدد كيف يجب أن يستمر بقية الحساب. هذا أيضًا يجعله نوعًا من الأشياء التسلسلية. عادةً ما يكون لديك مؤشر ترابط واحد للتنفيذ ويحدد الاستمرار كيف ستستمر.

في حالة MapReduce ، فأنت تقدم وسيطات الوظائف التي يتم استخدامها عدة مرات. لا تمثل وظائف الوسيطة هذه حقًا بقية الحساب ، ولكن فقط لبنات البناء الصغيرة التي يتم استخدامها مرارًا وتكرارًا. غالبًا ما يمكن توزيع بت "مرارا وتكرارا" على آلات متعددة مما يجعل هذا النوع الموازي.

لذلك أنت محق في رؤية القواسم المشتركة. لكن أحدهم ليس حقًا مثالًا على الآخر.

Answer 4

Reduce MAP هو تنفيذ. يمكن أن تستخدم واجهة الترميز التي تتيح لك استخدام هذا التنفيذ الاستمرارية ؛ إنها حقًا مسألة كيفية استخلاص الإطار والتحكم في الوظائف. النظر في واجهات التصريح لـ Hadoop مثل الخنزير ، أو اللغات التعريفية بشكل عام مثل SQL ؛ يمكن تنفيذ الآلية الموجودة أسفل الواجهة بعدة طرق.

على سبيل المثال ، إليك تنفيذ Python Map-Reduce مجردة:

def mapper(input_tuples):
    "Return a generator of items with qualifying keys, keyed by item.key"
    # we are seeing a partition of input_tuples
    return (item.key, item) for (key, item) in input_items if key > 1)

def reducer(input_tuples):
    "Return a generator of items with qualifying keys"
    # we are seeing a partition of input_tuples
    return (item for (key, item) in input_items if key != 'foo')

def run_mapreduce(input_tuples):
    # partitioning is magically run across boxes
    mapper_inputs = partition(input_tuples)
    # each mapper is magically run on separate box
    mapper_outputs = (mapper(input) for input in mapper_inputs)
    # partitioning and sorting is magically run across boxes
    reducer_inputs = partition(
        sort(mapper_output for output in mapper_outputs))
    # each reducer is magically run on a separate box
    reducer_outputs = (reducer(input) for input in reducer_inputs)

وإليك نفس التنفيذ باستخدام coroutines ، مع تجريد أكثر سحرية مخفية:

def mapper_reducer(input_tuples):
    # we are seeing a partition of input_tuples
    # yield mapper output to caller, get reducer input
    reducer_input = yield (
        item.key, item) for (key, item) in input_items if key > 1)
    # we are seeing a partition of reducer_input tuples again, but the
    # caller of this continuation has partitioned and sorted
    # yield reducer output to caller
    yield (item for (key, item) in input_items if key != 'foo')