حساب المسند الموزع على دفق الحدث

Question

سؤالي هو في الواقع طلب أوراق أو مقالات أو نصوص أو كتب حول المشكلة التي أحاول حلها في عملي.

أنا أعمل على برنامج يحسب قيمة أصلية (صواب أو خطأ) لكائن معين في نظام موزع حيث يوجد تيار من الأحداث التي يمكن أن تغير سمات الكائن ، وبالتالي ، القيمة الأصلية.عندما تتغير القيمة الأصلية ، يجب على البرنامج إرسال إشعار حول هذا التغيير.

على سبيل المثال ، ضع في اعتبارك أن هناك كائنا A التي لها سمة تسمى name والنظر في أن هناك المسند P وهذا صحيح عندما يكون الكائن name يساوي Jhon.يحتوي كل حدث في الدفق على طابع زمني وقيمة لاسم السمة.لذا ضع في اعتبارك التسلسل التالي للأحداث:

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 2 }
e3 = { name: Peter, timestamp: 3 }
e4 = { name: Doug, timestamp: 4 }
e5 = { name: Jhon, timestamp: 5 }

في هذه المشكلة ، يكون للأحداث علاقة ترتيب كاملة:إذا كان لديك حدثين يمكنك دائما أن تقول أي واحد هو أقدم منهم.

الآن ، لا تظهر الأحداث بالضرورة في الدفق بالترتيب الصحيح وفقا للطابع الزمني.كل حدث فريد من نوعه للطابع الزمني الخاص به ، لذلك لا يوجد حدثان أو أكثر بنفس الطابع الزمني لنفس الكائن.أيضا ، لا تشكل الطوابع الزمنية بالضرورة تسلسلا يزداد دائما بمقدار واحد:إذا رأينا e1 مع الطابع الزمني 1 و e3 مع الطابع الزمني 3, ، لا يعني وجود e2 مع الطابع الزمني 2.ليس هناك ما يضمن أنه سيتم استلام جميع الأحداث أو متى سيتم استلامها.إنه جزء من المشكلة التي نعرفها فقط عن وجود الأحداث التي نراها في الدفق.

السيناريو الحقيقي هو أسوأ من ذلك:هناك العديد من أجهزة الكمبيوتر التي تعالج هذا التدفق من الأحداث بشكل متوازي.ومع ذلك ، من أجل البساطة ، سأذهب إلى أبعد من ذلك في هذا المثال بالنظر إلى جهاز كمبيوتر واحد فقط.

إذا وصلت الأحداث وتمت معالجتها بالترتيب الموضح أعلاه ، فيجب أن تكون الإشعارات المرسلة:

P(A) = true when e1 arrives
P(A) = false when e3 arrives
P(A) = true when e5 arrives.

هذا هو التسلسل الصحيح للإشعارات لأنه يحترم ترتيب الطابع الزمني.الآن ، تخيل أن الكمبيوتر يتلقى الأحداث بالترتيب التالي:

e1, e5, e2, e4, e3

سترسل الخوارزمية الساذجة التي لا تأخذ في الاعتبار الطابع الزمني للحدث تسلسلا غير صحيح من الإشعارات:

P(A) = true when e1 arrives
P(A) = false when e4 arrives

الخوارزمية التي أعمل عليها تأخذ في الاعتبار الطوابع الزمنية وتستنتج متى كان يجب إرسال إشعار ولكن لم يتم إرساله.لذلك عندما e3 يصل وسوف تلاحظ أن الإخطار P(A) = true ل e5 لم يتم إرسالها.هذا يشبه إلى حد ما إعادة اختراع العجلة ، على الرغم من أنني لست على علم بأي قراءة حول هذه المشكلة.أود بعض الإشارات إلى هذه المشكلة أو إلى شيء مشابه ، مثل بعض الأوراق التي تتناول هذا النوع من المشاكل.

المشكلة الحقيقية أكثر تعقيدا لأنها تنطوي على تخزين المسند $\مرات$ حالة الكائن في قاعدة بيانات تعمل كحالة مشتركة بين أجهزة الكمبيوتر التي تعالج الدفق وأنا أتحدث عن آلاف الأحداث التي تصل في الثانية ، لذا لا يمكن الاحتفاظ بجميع الأحداث المخزنة في بعض قواعد البيانات.

هل هناك أي أدب حول المشكلة التي وصفتها?لو ذلك, هل يمكن أن تعطيني روابط إليها?

أود أن أرى ورقة أو نصا يشرح خوارزمية تحل هذه المشكلة وسيكون من الأفضل أن تقدم هذه الورقة أدلة حول الخوارزمية (على سبيل المثال.صحة).

إذا لم تكن هذه الورقة موجودة (أعتقد في الواقع أن هذا هو الحال) ، فسأقبل إجابة تصف خوارزمية وتقدم حجة أو دليلا على صحتها.

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

Answer 1

استحالة النتيجة #1:الأحداث المسقطة

لا يمكن حل المشكلة بشكل عام;لا توجد طريقة لضمان تلبية متطلباتك إذا تم إسقاط بعض الأحداث (أي لم يتم استلامها).فكر أولا في هذا الدفق:

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 4 }

حيث ترى الخوارزمية كلا الحدثين.بعد ذلك ، ضع في اعتبارك هذا الدفق:

e1' = { name: Jhon, timestamp: 1 }
e2' = { name: Pete, timestamp: 2 }
e3' = { name: Jhon, timestamp: 3 }
e4' = { name: Jhon, timestamp: 4 }

حيث ترى الخوارزمية الأحداث فقط e1',e4' (يتم فقدان الأحداث الأخرى ولم تتلق أبدا).قد تلاحظ أن ما تراه الخوارزمية في كلتا الحالتين متطابق ، لذلك ستكون مخرجاتها متطابقة في كلتا الحالتين.ومع ذلك ، تختلف الإجابة الصحيحة في هاتين الحالتين ، لذلك لا يوجد أمل في خوارزمية تنتج دائما مخرجات صحيحة.(الاستجابة الصحيحة في الحالة الأولى هي عدم إصدار إخطارات;الاستجابة الصحيحة في الحالة الثانية هي إنتاج إشعارين ، أحدهما للإشارة إلى أن المسند خاطئ بعد الاستلام e2', ، واحد للإشارة إلى أن المسند صحيح بعد تلقي e3'.)

ليس من الواضح كيفية تكييف المتطلبات للتعامل مع هذا الموقف.الحل الوحيد المعقول الذي يمكنني رؤيته هو القول إن الإخطارات التي يتم إنتاجها يجب أن تعتمد فقط على الأحداث المستلمة ، وليس على الأحداث التي يتم إرسالها.هذا يعادل تحديد أنه لا يمكن إسقاط الأحداث.

نتيجة الاستحالة #2:إعادة ترتيب الأحداث

أنت تذكر أنه يجب أن تكون قادرا على التعامل مع الأحداث المعاد ترتيبها ، دون تخزين جميع الأحداث في الذاكرة ، ومع إعادة الطلب التعسفي.ومع ذلك ، فإن هذه المتطلبات غير متوافقة:وهذا أمر مستحيل تحقيقه.النظر في سلسلة طويلة من الأحداث مع الطوابع الزمنية 2,4,6,8,10,12,...في نهاية التسلسل الطويل للأحداث ، إذا وصل حدث ذي طابع زمني غريب ، فإن الطريقة الوحيدة للتأكد من أنه يمكنك التعامل معه بشكل صحيح هي تخزين التاريخ الكامل للأحداث الماضية (أو الحالات السابقة للكائن).

لذلك ، سيكون عليك الاسترخاء في متطلبات إعادة الطلب أيضا.ربما كنت على استعداد لتخزين جميع الأحداث في الذاكرة إلى الأبد.(إذا كان الأمر كذلك ، لديك حل.) ربما تكون على استعداد لفرض قيود على إعادة الطلب ، على سبيل المثال ، لن يتأخر أي حدث لأكثر من 10 دقائق.(إذا كان الأمر كذلك ، لديك فقط لتخزين التاريخ لمدة 10 دقيقة الماضية ، ويمكن حذف كل شيء من كبار السن.) ربما يكون هناك شيء آخر أكثر منطقية في وضعك الخاص.

ولكن الشيء الوحيد الذي ليس خيارا هو فرض جميع المتطلبات القوية المذكورة في سؤالك ، وتتطلب خوارزمية صحيحة دائما.

---

لست على علم بأي أدبيات حول هذا الموضوع ولا أرى بشكل خاص أي سبب لتوقع وجود أي منها.إنها مجموعة محددة جدا من المتطلبات ، ويبدو لي أن المهمة الناتجة إما تافهة أو مستحيلة الحل.هذه عادة ليست نوع من المشاكل التي تميل إلى أن تدرس في الأدب.ربما كنت قد تكون مهتمة في هياكل البيانات الثابتة, ، ولكن هذه مجرد طريقة رائعة لتخزين التاريخ الكامل للأحداث ، والتي قلت أنك تريد القيام بها;ولا تحتاج إلى بنية بيانات خيالية للقيام بذلك في وضعك الخاص.