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

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

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

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

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

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

توجد متغيرات من مرشحات 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 الخاص بك كما يلي:

var
  Bloom         =   require('bloom-redis'),
  express       =   require('express'),
  redis         =   require('redis'),
  
  app,
  client,
  filter;

//setup our Express server
app = express();

//create the connection to Redis
client = redis.createClient();


filter = new Bloom.BloomFilter({ 
  client    : client, //make sure the Bloom module uses our newly created connection to Redis
  key       : 'username-bloom-filter', //the Redis key
  
  //calculated size of the Bloom filter.
  //This is where your size / probability trade-offs are made
  //http://hur.st/bloomfilter?n=100000&p=1.0E-6
  size      : 2875518, // ~350kb
  numHashes : 20
});

app.get('/check', function(req,res,next) {
  //check to make sure the query string has 'username'
  if (typeof req.query.username === 'undefined') {
    //skip this route, go to the next one - will result in a 404 / not found
    next('route');
  } else {
   filter.contains(
     req.query.username, // the username from the query string
     function(err, result) {
       if (err) { 
        next(err); //if an error is encountered, send it to the client
        } else {
          res.send({ 
            username : req.query.username, 
            //if the result is false, then we know the item has *not* been used
            //if the result is true, then we can assume that the item has been used
            status : result ? 'used' : 'free' 
          });
        }
      }
    );
  }
});


app.get('/save',function(req,res,next) {
  if (typeof req.query.username === 'undefined') {
    next('route');
  } else {
    //first, we need to make sure that it's not yet in the filter
    filter.contains(req.query.username, function(err, result) {
      if (err) { next(err); } else {
        if (result) {
          //true result means it already exists, so tell the user
          res.send({ username : req.query.username, status : 'not-created' });
        } else {
          //we'll add the username passed in the query string to the filter
          filter.add(
            req.query.username, 
            function(err) {
              //The callback arguments to `add` provides no useful information, so we'll just check to make sure that no error was passed
              if (err) { next(err); } else {
                res.send({ 
                  username : req.query.username, status : 'created' 
                });
              }
            }
          );
        }
      }
    });
  }
});

app.listen(8010);

لتشغيل هذا الخادم: عقدة 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 الجديد الخاص بك:

var
  async         =   require('async'),
  Bloom         =   require('bloom-redis'),
  express       =   require('express'),
  redis         =   require('redis'),
  
  app,
  client,
  filter,
  
  // From Project Gutenberg - opening lines of the top 10 public domain ebooks
  // https://www.gutenberg.org/browse/scores/top
  openingLines = {
    'pride-and-prejudice' : 
      'It is a truth universally acknowledged, that a single man in possession of a good fortune, must be in want of a wife.',
    'alices-adventures-in-wonderland' : 
      'Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it, \'and what is the use of a book,\' thought Alice \'without pictures or conversations?\'',
    'a-christmas-carol' :
      'Marley was dead: to begin with.',
    'metamorphosis' : 
      'One morning, when Gregor Samsa woke from troubled dreams, he found himself transformed in his bed into a horrible vermin.',
    'frankenstein'  : 
      'You will rejoice to hear that no disaster has accompanied the commencement of an enterprise which you have regarded with such evil forebodings.',
    'adventures-of-huckleberry-finn' : 
      'YOU don\'t know about me without you have read a book by the name of The Adventures of Tom Sawyer; but that ain\'t no matter.',
    'adventures-of-sherlock-holmes' :
      'To Sherlock Holmes she is always the woman.',
    'narrative-of-the-life-of-frederick-douglass' :
      'I was born in Tuckahoe, near Hillsborough, and about twelve miles from Easton, in Talbot county, Maryland.',
    'the-prince' :
      'All states, all powers, that have held and hold rule over men have been and are either republics or principalities.',
    'adventures-of-tom-sawyer' :
      'TOM!'
  };


app = express();
client = redis.createClient();

filter = new Bloom.BloomFilter({ 
  client    : client,
  key       : '3content-bloom-filter', //the Redis key
  size      : 2875518, // ~350kb
  //size      : 1024,
  numHashes : 20
});

app.get('/show-content/:user', function(req,res,next) {
  //we're going to be looping through the contentIds, checking to see if they are in the filter.
  //Since this spends time on each contentId wouldn't be advisable to do over a high number of contentIds
  //But, in this case the number of contentIds is small / fixed and our filter.contains function is fast, it is okay.
  var
    //creates an array of the keys defined in openingLines
    contentIds = Object.keys(openingLines),
    //getting part of the path from the URI
    user = req.params.user,
    checkingContentId,
    found = false,
    done = false;
   
  //since filter.contains is asynchronous, we're using the async library to do our looping 
  async.whilst(
    //check function, where our asynchronous loop will end
    function () { return (!found && !done); },
    function(cb) {
      //get the first item from the array of contentIds
      checkingContentId = contentIds.shift();
      
      //false means we're sure that it isn't in the filter
      if (!checkingContentId)  {
         done = true; // this will be caught by the check function above
         cb();
      } else {
        //concatenate the user (from the URL) with the id of the content
        filter.contains(user+checkingContentId, function(err, results) {
          if (err) { cb(err); } else {
            found = !results;
            cb();
          }
        });
      }
    },
    function(err) {
      if (err) { next(err); } else {
        if (openingLines[checkingContentId]) {
          //before we send the fresh contentId, let's add it to the filter to prevent it from showing again
          filter.add(
            user+checkingContentId, 
            function(err) {
              if (err) { next(err); } else {
                //send the fresh quote
                res.send(openingLines[checkingContentId]);
              }
            }
          );
        } else {
          res.send('no new content!');
        }
      }
    }
  );
});

app.listen(8011);

إذا انتبهت بعناية إلى وقت الذهاب والإياب في أدوات 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إلى:

var
  async           =   require('async'),
  Bloom           =   require('bloom-redis'),
  bodyParser      =   require('body-parser'),
  express         =   require('express'),
  redis           =   require('redis'),
  
  app,
  client,
  filter,
  
  currentDataKey  = 'current-data',
  usedDataKey     = 'used-data';
  
app = express();
client = redis.createClient();

filter = new Bloom.BloomFilter({ 
  client    : client,
  key       : 'stale-bloom-filter',
  //for illustration purposes, this is a super small filter. It should fill up at around 500 items, so for a production load, you'd need something much larger!
  size      : 1024,
  numHashes : 20
});

app.post(
  '/',
  bodyParser.text(),
  function(req,res,next) {
    var
      used;
      
    console.log('POST -', req.body); //log the current data being posted
    console.time('post'); //start measuring the time it takes to complete our filter and conditional verification process
    
    //async.series is used to manage multiple asynchronous function calls.
    async.series([
      function(cb) {
        filter.contains(req.body, function(err,filterStatus) {
          if (err) { cb(err); } else {
            used = filterStatus;
            cb(err);
          }
        });
      },
      function(cb) {
        if (used === false) {
          //Bloom filters do not have false negatives, so we need no further verification
          cb(null);
        } else {
          //it *may* be in the filter, so we need to do a follow up check
          //for the purposes of the tutorial, we'll add a 150ms delay in here since Redis can be fast enough to make it difficult to measure and the delay will simulate a slow database or API call
          setTimeout(function() {
            console.log('possible false positive');
            client.sismember(usedDataKey, req.body, function(err, membership) {
              if (err) { cb(err); } else {
                //sismember returns 0 if an member is not part of the set and 1 if it is.
                //This transforms those results into booleans for consistent logic comparison
                used = membership === 0 ? false : true;
                cb(err);
              }
            });
          }, 150);
        }
      },
      function(cb) {
        if (used === false) {
          console.log('Adding to filter');
          filter.add(req.body,cb);
        } else {
          console.log('Skipped filter addition, [false] positive');
          cb(null);
        }
      },
      function(cb) {
        if (used === false) {
          client.multi()
            .set(currentDataKey,req.body) //unused data is set for easy access to the 'current-data' key
            .sadd(usedDataKey,req.body) //and added to a set for easy verification later
            .exec(cb); 
        } else {
          cb(null);
        }
      }
      ],
      function(err, cb) {
        if (err) { next(err); } else {
          console.timeEnd('post'); //logs the amount of time since the console.time call above
          res.send({ saved : !used }); //returns if the item was saved, true for fresh data, false for stale data.
        }
      }
    );
});

app.get('/',function(req,res,next) {
  //just return the fresh data
  client.get(currentDataKey, function(err,data) {
    if (err) { next(err); } else {
      res.send(data);
    }
  });
});

app.listen(8012);

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

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

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

#!/bin/bash
for i in `seq 1 500`;
do
  curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/
done   

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

استنتاج

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