Advertisement
  1. Code
  2. Redis
Code

فهم سحر مرشحات بلوم مع Node.js و Redis

by
Length:LongLanguages:

Arabic (العربية/عربي) translation by ansgaradh (you can also view the original English article)

في حالة الاستخدام الصحيحة ، تبدو مرشحات بلوم مثل السحر. هذا بيان جريء ، ولكن في هذا البرنامج التعليمي سوف نستكشف بنية البيانات الغريبة ، وأفضل طريقة لاستخدامها ، وبعض الأمثلة العملية باستخدام Redis و Node.js.

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

  1. أضف بندًا.
  2. تحقق من عدم إضافة عنصر مسبقًا.

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

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

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

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

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

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

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

اقامة

سنستخدم Redis و Node.js لتوضيح مرشحات Bloom. Redis هو وسيلة تخزين لمرشح Bloom الخاص بك؛ انها سريعة ، في الذاكرة ، ولها بعض الأوامر المحددة (GETBIT ، SETBIT ) التي تجعل التنفيذ فعالة. سأفترض أن لديك Node.js و npm و Redis مثبت على نظامك. يجب تشغيل خادم Redis الخاص بك على localhost في المنفذ الافتراضي حتى تعمل الأمثلة الخاصة بنا.

في هذا البرنامج التعليمي ، لن نطبق فلترًا من الألف إلى الياء ؛ بدلاً من ذلك ، سنركز على الاستخدامات العملية باستخدام وحدة مدمجة مسبقًا في npm: bloom-redis . ازهر رديس لديه مجموعة موجزة جدا من الطرق: إضافة ، يحتوي و اضحة .

كما ذكرنا سابقًا ، تحتاج عوامل تصفية Bloom إلى خوارزمية تجزئة لإنشاء معرفات فريدة لعنصر ما. يستخدم bloom-redis خوارزمية MD5 المعروفة ، والتي ، على الرغم من أنها ربما ليست مناسبة تمامًا لمرشح Bloom (بطيء قليلاً ، مبالغة في البتات) ، ستعمل بشكل جيد.

أسماء المستخدمين الفريدة

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

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

لتوضيح ذلك ، لنقم بإنشاء ملقم REST سريع باستخدام Express. أولاً ، قم بإنشاء ملفpackage.json ثم قم بتشغيل الأوامر الطرفية التالية.

npm install bloom-redis --save

npm install express --save

npm install redis --save

يكون حجم الخيارات الافتراضية لـ bloom-redis عند اثنين ميغا بايت. هذا يخطئ على جانب الحذر ، لكنه كبير جدا. يعد إعداد حجم مرشح بلوم أمرًا بالغ الأهمية: كبير جدًا وتهدر الذاكرة ، صغير جدًا ومعدل موجب كاذب سيكون مرتفعًا جدًا. يتم تضمين الرياضيات تشارك في تحديد حجم تماما وخارج نطاق هذا البرنامج التعليمي ، ولكن لحسن الحظ هناك آلة حاسبة حجم مرشح بلوم لإنجاز المهمة دون تكسير كتاب دراسي.

الآن ، قم بإنشاء app.js الخاص بك كما يلي:

لتشغيل هذا الخادم: عقدة app.js . انتقل إلى متصفحك وأشره إلى: https: // localhost: 8010 / check؟ username = kyle . يجب أن تكون الإجابة: {"اسم المستخدم": "kyle" ، "status": "free"} .

الآن ، دعنا نحفظ اسم المستخدم هذا من خلال توجيه المتصفح على http: // localhost: 8010 / save؟ username = kyle . ستكون الإجابة:{"اسم المستخدم": "kyle" ، "status": "created"} . إذا رجعت إلى العنوان http: // localhost: 8010 / check؟ username = kyle ، فستكون الإجابة {"اسم المستخدم": "kyle" و "status": "used"} . وبالمثل ، عند الرجوع إلىhttp: // localhost: 8010 / save؟ username = kyleسيؤدي إلى {"اسم المستخدم": "kyle" و "status": "not-created"} .

من الجهاز ، يمكنك رؤية حجم الفلتر: redis-cli strlen username-bloom-filter .

الآن ، مع عنصر واحد ، يجب أن تظهر 338622 .

والآن ، حاول إضافة المزيد من أسماء المستخدمين باستخدام المسار / save . جرب ما تشاء.

إذا قمت بفحص الحجم مرة أخرى ، قد تلاحظ أن حجمك قد ارتفع قليلاً ، ولكن ليس لكل إضافة.الغريب ، أليس كذلك؟ داخليًا ، يعمل مرشح بلوم على تعيين وحدات البت الفردية (1's / 0) في مواضع مختلفة في السلسلة المحفوظة عند اسم المستخدم -البلوم. ومع ذلك ، هذه ليست متجاورة ، لذلك إذا قمت بتعيين بت في فهرس 0 ثم واحد في الفهرس 10،000 ، سيكون كل شيء بين 0. بالنسبة للاستخدامات العملية ، ليس من المهم في البداية فهم الآليات الدقيقة لكل عملية - فقط اعلم أن هذا أمر طبيعي وأن تخزينك في Redis لن يتجاوز القيمة التي حددتها.

محتوى جديد

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

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

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

سنحتاج إلى تثبيت وحدة npm أخرى. من المحطة ، شغل: npm install async - save

ملف app.js الجديد الخاص بك:

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

بيانات تالفة

في هذا المثال ، سنقوم ببناء خادم Express صغير يقوم بعمل أمرين: قبول بيانات جديدة عبر POST ، وعرض البيانات الحالية (مع طلب GET). عندما تكون البيانات الجديدة POST'ed إلى الخادم ، سيتحقق التطبيق من وجودها في الفلتر. إذا لم يكن موجودًا ، سنقوم بإضافته إلى مجموعة في Redis ، وإلا فسنعود إلى null. سيقوم طلب GET بجلبه من Redis وإرساله إلى العميل.

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

إذن ، ماذا نكسب؟ نكتسب سرعة عدم التحقق من المصدر الفعلي في كل مرة. في الحالات التي يكون فيها مصدر البيانات بطيئًا (واجهات برمجة التطبيقات الخارجية ، قواعد بيانات pokey ، وسط ملف ثابت) ، تكون هناك حاجة إلى زيادة السرعة. لشرح السرعة ، دعنا نضيف تأخيرًا واقعيًا يبلغ 150 مللي ثانية في مثالنا. سنستخدم أيضًا console.time /console.timeEnd لتسجيل الاختلافات بين فحص مرشح Bloom وفحص الفلتر غير Bloom.

في هذا المثال ، سنستخدم أيضًا عددًا محدودًا جدًا من البتات: 1024 فقط. سوف تملأ بسرعة.عندما تملأ ، ستظهر المزيد والمزيد من الإيجابيات الخاطئة - سترى زيادة وقت الاستجابة مع تملأ المعدل الإيجابي الخاطئ.

يستخدم هذا الخادم نفس الوحدات النمطية كما كان من قبل ، لذا قم بتعيين ملف app.jsإلى:

بما أن POSTing إلى خادم يمكن أن تكون خادعة مع متصفح ، دعونا نستخدم curlللاختبار.

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

يمكن استخدام برنامج نصي باش سريع لإظهار مدى ملاءمة الفلتر بأكمله:

النظر في ملء أو مرشح كامل مثير للاهتمام. بما أن هذا الجهاز صغير ، يمكنك مشاهدته بسهولة مع redis-cli . من خلال تشغيلredis-cli تحصل على فلتر قديم من المحطة بين إضافة عناصر ، سترى زيادة البايت الفردي. سيكون عامل تصفية كامل \ xff لكل بايت. في هذه المرحلة ، سيعود الفلتر دائمًا إلى وضع إيجابي.

استنتاج

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

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.