Node.js와 Redis를 사용하여 Bloom Filters의 강력한 기능을 살펴보세요-Word누르다-php.cn

使用 Node.js 和 Redis 探索 Bloom Filter 的魅力

올바른 사용 사례에서 블룸 필터는 마술처럼 보입니다. 너무 대담한 표현이지만, 이 튜토리얼에서는 이 이상한 데이터 구조와 이를 가장 잘 사용하는 방법, 그리고 Redis와 Node.js를 사용한 몇 가지 실제 예제를 살펴보겠습니다.

블룸 필터는 확률적 단방향 데이터 구조입니다. 이 문맥에서 "필터"라는 단어는 혼동될 수 있습니다. 필터는 활성 동사라는 의미이지만 저장 공간, 명사로 생각하는 것이 더 쉬울 수 있습니다. 간단한 블룸 필터를 사용하면 다음 두 가지 작업을 수행할 수 있습니다.

항목을 추가하세요.
항목이 이전에 추가되지 않았는지 확인하세요.

다음은 이해해야 할 중요한 제한 사항입니다. 항목을 삭제할 수 없으며 블룸 필터에 항목을 나열할 수도 없습니다. 또한 과거에 항목이 필터에 추가되었는지 여부를 확인할 수 없습니다. 이것이 블룸 필터의 확률적 특성이 작용하는 지점입니다. 즉, 오탐은 가능하지만 오탐은 가능하지 않습니다. 필터가 올바르게 설정되면 오탐 가능성이 매우 적습니다.

삭제 또는 크기 조정과 같은 추가 기능을 추가하는 다양한 블룸 필터가 있지만 복잡성과 제한 사항도 추가됩니다. 변형으로 넘어가기 전에 먼저 간단한 블룸 필터를 이해하는 것이 중요합니다. 이 글에서는 간단한 Bloom 필터만을 소개합니다.

이러한 제한을 통해 고정 크기, 해시 기반 암호화, 빠른 조회 등 많은 이점을 얻을 수 있습니다.

블룸 필터를 설정할 때 크기를 지정해야 합니다. 이 크기는 고정되어 있으므로 필터에 10억 개 항목이 있는 경우 지정된 크기 이상으로 커지지 않습니다. 필터에 더 많은 항목을 추가할수록 오탐 가능성이 높아집니다. 더 작은 필터를 지정하면 더 큰 필터를 사용할 때보다 거짓양성률이 더 빠르게 증가합니다.

블룸 필터는 단방향 해싱 개념을 기반으로 구축되었습니다. 비밀번호를 올바르게 저장하는 것과 마찬가지로 Bloom 필터는 해싱 알고리즘을 사용하여 전달된 항목의 고유 식별자를 결정합니다. 해시는 본질적으로 되돌릴 수 없으며 겉보기에 임의의 문자열로 표시됩니다. 따라서 누군가가 블룸 필터에 액세스하면 아무것도 직접적으로 공개되지 않습니다.

마지막으로 블룸 필터는 빠릅니다. 이 작업에는 다른 방법보다 비교 횟수가 훨씬 적고 메모리에 쉽게 저장할 수 있어 성능에 영향을 미치는 데이터베이스 적중을 방지할 수 있습니다.

블룸 필터의 한계와 장점을 이해했으므로 이제 블룸 필터를 사용할 수 있는 몇 가지 상황을 살펴보겠습니다.

설정

Redis와 Node.js를 사용하여 Bloom 필터를 설명하겠습니다. Redis는 Bloom 필터의 저장 매체로, 속도가 빠르고 메모리 내이며 예시가 제대로 작동하도록 기본 포트에서 실행되는 특정 명령(

)이 있습니다. GETBIT、SETBIT），可以提高实施效率。我假设您的系统上安装了 Node.js、npm 和 Redis。您的 Redis 服务器应该在 localhost이 튜토리얼에서는 처음부터 필터를 구현하지 않습니다. 대신, npm에 사전 구축된 모듈인 Bloom-redis를 실제로 사용하는 데 중점을 둘 것입니다. Bloom-redis에는 매우 깔끔한 메소드 세트가 있습니다:

add、contains 和 clear앞서 언급했듯이 Bloom 필터는 항목의 고유 식별자를 생성하기 위해 해싱 알고리즘이 필요합니다. Bloom-redis는 잘 알려진 MD5 알고리즘을 사용합니다. 비록 Bloom 필터에는 적합하지 않을 수 있지만(약간 느리고 약간 과잉) 잘 작동합니다.

고유한 사용자 이름

사용자 이름, 특히 URL에서 사용자를 식별하는 이름은 고유해야 합니다. 사용자가 자신의 사용자 이름을 변경할 수 있는 애플리케이션을 구축하는 경우 사용자 이름 혼동과 공격을 피하기 위해 절대 사용되지 않는 사용자 이름을 원할 수 있습니다.

블룸 필터가 없으면 지금까지 사용된 모든 사용자 이름이 포함된 테이블을 참조해야 하므로 규모에 따라 매우 많은 비용이 소요될 수 있습니다. Bloom 필터를 사용하면 사용자가 새 이름을 채택할 때마다 항목을 추가할 수 있습니다. 사용자가 사용자 이름이 사용되었는지 확인할 때 해야 할 일은 블룸 필터를 확인하는 것뿐입니다. 요청한 사용자 이름이 이전에 추가되었는지 여부를 확실하게 알려줄 수 있습니다. 필터는 실제로 사용자 이름을 사용하지 않았음에도 사용자 이름을 사용했다고 잘못 반환할 수 있습니다. 그러나 이는 단지 예방 조치일 뿐 실제 피해를 입히지는 않습니다(사용자가 "k3w1d00d47"을 선언하지 못할 수 있다는 점 제외). .

이를 설명하기 위해 Express를 사용하여 빠른 REST 서버를 구축해 보겠습니다. 먼저

파일을 생성한 후 다음 터미널 명령을 실행합니다.

package.json

npm 安装bloom-redis --save

npm install express --save

bloom-redis의 기본 옵션 크기는 2MB로 설정되어 있습니다. 주의해서 틀린 말이지만 꽤 큽니다. 블룸 필터의 크기를 설정하는 것은 매우 중요합니다. 너무 크면 메모리가 낭비되고, 너무 작으면 거짓 긍정 비율이 너무 높아집니다. 크기를 결정하는 데 관련된 수학은 복잡하고 이 튜토리얼의 범위를 벗어나지만 다행히도 교과서를 해독하지 않고도 작업을 수행하는 블룸 필터 크기 계산기가 있습니다.

이제 다음과 같이 app.js을 생성합니다.

으아악

이 서버를 실행하려면: node app.js。转到浏览器并将其指向：https://localhost:8010/check?username=kyle。响应应该是：{"username":"kyle","status":"free"}.

이제 브라우저에서 http://localhost:8010/save?username=kyle 来保存该用户名。响应将是：{"username":"kyle","status":"created"}。如果返回地址 http://localhost:8010/check?username=kyle，响应将是 {"username":"kyle","status ":"已使用"}.同样，返回 http://localhost:8010/save?username=kyle 将导致 {"username":"kyle","status":"not -创建“}를 가리키도록 합시다.

터미널에서 필터의 크기를 확인할 수 있습니다. redis-cli strlen 用户名-bloom-filter.

이제 한 항목에 대해 338622가 표시됩니다.

이제 /save 경로를 사용하여 더 많은 사용자 이름을 추가해 보세요. 원하는만큼 시도해 볼 수 있습니다.

사이즈를 다시 확인해보면 사이즈가 조금씩 늘어난 것을 볼 수 있지만, 추가할 때마다 늘어나는 것은 아닙니다. 궁금하지 않나요? 내부적으로 블룸 필터는 사용자 이름-bloom에 저장된 문자열의 여러 위치에 개별 비트(1/0)를 설정합니다. 그러나 이들은 연속적이지 않으므로 인덱스 0에 비트를 설정한 다음 인덱스 10,000에 비트를 설정하면 그 사이의 모든 것이 0이 됩니다. 실용적인 목적을 위해 처음에는 각 작업의 정확한 메커니즘을 이해하는 것이 중요하지 않습니다. 단지 이것이 정상이며 Redis에 지정한 것보다 더 많은 것을 저장하지 않을 것이라는 점만 알아두세요.

새로운 콘텐츠

웹사이트의 신선한 콘텐츠는 사용자의 재방문을 유도할 수 있습니다. 그렇다면 매번 사용자에게 새로운 콘텐츠를 어떻게 보여줄 수 있을까요? 기존 데이터베이스 접근 방식을 사용하면 사용자 식별자와 스토리 식별자가 포함된 테이블에 새 행을 추가한 다음 콘텐츠를 표시하기로 결정할 때 테이블을 쿼리합니다. 여러분이 상상할 수 있듯이 특히 사용자와 콘텐츠가 성장함에 따라 데이터베이스는 매우 빠르게 성장할 것입니다.

이 경우 거짓 부정(예: 보이지 않는 콘텐츠를 표시하지 않음)의 결과는 매우 작으므로 블룸 필터를 실행 가능한 옵션으로 만듭니다. 언뜻 보면 각 사용자에게 Bloom 필터가 필요하다고 생각할 수도 있지만, 여기서는 사용자 식별자와 콘텐츠 식별자를 간단히 연결한 다음 해당 문자열을 필터에 삽입하겠습니다. 이렇게 하면 모든 사용자에 대해 단일 필터를 사용할 수 있습니다.

이 예에서는 콘텐츠를 표시하는 또 다른 기본 Express 서버를 구축해 보겠습니다. Route /show-content/any-username(any-username는 URL 안전 값임)을 방문할 때마다 사이트에 콘텐츠가 없어질 때까지 새로운 콘텐츠가 표시됩니다. 이 예에서 콘텐츠는 구텐베르그 프로젝트 상위 10권 도서의 첫 번째 줄입니다.

다른 npm 모듈을 설치해야 합니다. 터미널에서 실행: npm install async --save

새 app.js 파일:

으아악

개발 도구에서 왕복 시간에 주의를 기울이면 사용자 이름으로 단일 경로를 요청하는 횟수가 많을수록 시간이 더 오래 걸린다는 것을 알 수 있습니다. 필터를 확인하는 데는 고정된 시간이 소요되지만, 이 경우에는 더 많은 항목이 있는지 확인합니다. 블룸 필터는 알려줄 수 있는 내용이 제한되어 있으므로 각 항목의 존재 여부를 테스트하고 있습니다. 물론 이 예에서는 매우 간단하지만 수백 개의 프로젝트를 테스트하는 것은 비효율적입니다.

오래된 데이터

이 예에서는 POST를 통해 새 데이터를 수락하고 현재 데이터를 표시(GET 요청 사용)하는 두 가지 작업을 수행하는 작은 Express 서버를 구축합니다. 새 데이터가 서버에 게시되면 애플리케이션은 해당 데이터가 필터에 존재하는지 확인합니다. 존재하지 않으면 Redis의 컬렉션에 추가하고, 그렇지 않으면 null을 반환합니다. GET 요청은 Redis에서 이를 가져와 클라이언트로 보냅니다.

이것은 처음 두 경우와 다르며, 오탐은 허용되지 않습니다. 우리는 첫 번째 방어선으로 블룸 필터를 사용할 것입니다. 블룸 필터의 속성을 고려하면 필터에 무언가가 없다는 것만 확인할 수 있으므로 이 경우 데이터를 계속해서 허용할 수 있습니다. 블룸 필터가 필터에 있을 수 있는 데이터를 반환하는 경우 실제 데이터 소스를 확인합니다.

那么，我们得到了什么？我们获得了不必每次都检查实际来源的速度。在数据源速度较慢的情况下（外部 API、小型数据库、平面文件的中间），确实需要提高速度。为了演示速度，我们在示例中添加 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);

로그인 후 복사

由于使用浏览器 POST 到服务器可能会很棘手，所以让我们使用curl 来测试。

curl --data“您的数据放在这里”--header“内容类型：text/plain”http://localhost:8012/

可以使用快速 bash 脚本来显示填充整个过滤器的外观：

#!/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 get stale-filter ，您将看到各个字节增加。完整的过滤器将为每个字节 \xff 。此时，过滤器将始终返回正值。

结论

布隆过滤器并不是万能的解决方案，但在适当的情况下，布隆过滤器可以为其他数据结构提供快速、有效的补充。

如果您仔细注意开发工具中的往返时间，您会发现使用用户名请求单个路径的次数越多，所需的时间就越长。虽然检查过滤器需要固定的时间，但在本例中，我们正在检查是否存在更多项目。布隆过滤器能够告诉您的信息有限，因此您正在测试每个项目是否存在。当然，在我们的示例中，它相当简单，但测试数百个项目效率很低。

위 내용은 Node.js와 Redis를 사용하여 Bloom Filters의 강력한 기능을 살펴보세요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!