Tair Bloom介紹,命令列表 - Tair

Bloom是一種機率性資料結構（space-efficient probabilistic data structure），在大規模資料中，僅需消耗較低的記憶體來判斷一個元素是否存在。而TairBloom基於Scalable Bloom Filter實現，具有動態擴容的能力，並且可以在擴容時維持誤判率的穩定性。

TairBloom簡介

在傳統的Redis資料結構中，可以使用Hash、Set、String的Bitset等實作類別似功能，但這些實現方式不是記憶體佔用量非常大，就是無法動態伸縮和保持誤判率不變。因此，TairBloom非常適合需要高效判斷大量資料是否存在且允許一定誤判率的業務情境。業務可以直接使用TairBloom提供的Bloom Filter（布隆過濾器）介面，無需二次封裝，更無需在本地實現布隆過濾器的功能。

主要特性

記憶體佔用低。
可動態擴容。
可自訂的誤判率（False Positive Rate）且在擴容時保持不變。

典型情境

適用於直播、音樂、電商等行業的推薦系統或爬蟲系統等，例如：

推薦系統：將使用者讀過的文章通過TairBloom記錄，並在給使用者推薦新文章前進行查詢，實現給使用者推薦感興趣，且沒讀過的文章。
爬蟲系統：在面對海量的URL時，將已經爬取過的URL進行過濾、去重操作，減少重複爬取的無效工作量。

最佳實務

基於TairBloom打造推薦系統

將已推薦給使用者的文章ID通過TairBloom記錄，並在推薦新文章前進行查詢、判斷，輕鬆實現給使用者推薦感興趣，且未推薦過的文章，虛擬碼如下：

void recommendedSystem(userid) {
    while (true) {
        // 從系統中隨機（或者根據使用者興趣）擷取一篇文章ID。
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // 如果發現可能已向使用者推薦過該文章，則推薦下一篇文章。
            continue;
        } else {
            // 確認未向使用者推薦過該文章，則向使用者發送推薦。
            sendRecommendMsg(docid);
            // 同時將已推薦的文章ID記錄至TairBloom。
            bf.add(userid, docid);
            break;
        }
    }
}

基於TairBloom最佳化爬蟲系統

在面對海量的URL時，將已經爬取過的URL進行過濾、去重操作，減少重複爬取的無效工作量，虛擬碼如下：

bool crawlerSystem( ) {
    while (true) {
        // 擷取待爬取的URL。
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // 如果該URL可能已被爬取，則跳過。
            continue;
        } else {
            // 爬取該URL內容。
            doDownload(url)
            // 並將該URL加入TairBloom。
            bf.add(url_bloom, url);
        }
    }
}

原理介紹

TairBloom作為一種Scalable Bloom Filter的實現，具有動態擴容的能力，同時誤判率（False Positive Rate）維持不變。而Scalable Bloom Filter是在Bloom Filter的基礎上進行最佳化的，下文將簡單介紹Bloom Filter與Scalable Bloom Filter的基本原理。

Bloom Filter
布隆過濾器是一個高空間利用率的機率性資料結構，由Burton Bloom於1970年提出，用於測試一個元素是否在集合中。
新建立的布隆過濾器是一串被置為0的Bit數組（假設有m位），同時聲明k個不同的Hash函數產生統一的隨機分布（k是一個小於m的常數）。向布隆過濾器中添加元素時，通過k個Hash函數將元素映射到Bit中的k個點，並將這些位置的值設定為1，一個Bit位可能被不同資料共用。下圖展示了假設布隆過濾器的k為3，向其插入X1、X2的過程。
查詢元素時，仍通過k個Hash函數得到對應的k個位，判斷目標位置是否為1，若目標位置全為1則認為該元素在布隆過濾器內，否則認為該元素不存在，下圖展示了在布隆過濾器中查詢Y1和Y2是否存在的過程。
由上圖可以發現，雖然從未向布隆過濾器中插入過Y2這個元素，但是布隆過濾器卻判斷Y2存在，因此，布隆過濾器是可能存在誤判的，即存在假陽性（false positive）。至此，可以得出關於布隆過濾器的幾個特性：
- Bit位可能被不同資料共用。
- 存在假陽性（false positive），且布隆過濾器中的元素越多，假陽性的可能性越大，但不存在假陰性（false negative），即不會將存在的元素誤判為不存在。
- 元素可以被加入布隆過濾器，但無法被刪除，因為Bit位是可以共用的，刪除時有可能會影響到其他元素。
Scalable Bloom Filter
隨著布隆過濾器中添加的元素越來越多，誤判率也越來越高，若希望誤判率穩定不變，需同步增加布隆過濾器的大小，但是布隆過濾器由於結構限制無法進行擴容。因此，Scalable Bloom Filter提出建立新的布隆過濾器，將多個布隆過濾器組裝成一個布隆過濾器使用。
下圖展示了一個Scalable Bloom Filter的基本模型（下文簡稱SBF）。該SBF一共包含BF0和BF1兩層。在一開始，SBF只包含BF0層，假設在插入a、b、c三個元素後，BF0層已經無法保證使用者設定的誤判率，此時會建立新的一層（BF1層）進行擴容。因此，後面的d、e、f元素會插入到BF1層中。同理，當BF1層也無法滿足誤判率時，會建立新的一層（BF2層），如此進行下去。
Scalable Bloom Filter只會向最後一層插入資料，同時也從最後一層開始查詢，直到查詢至BF0層。更多資訊，請參見Scalable Bloom Filter。

前提條件

執行個體為Tair記憶體型。

說明

最新小版本將提供更豐富的功能與穩定的服務，建議將執行個體的小版本升級到最新，具體操作請參見升級小版本。如果您的執行個體為叢集架構或讀寫分離架構，請將代理節點的小版本也升級到最新，否則可能出現命令無法識別的情況。

注意事項

操作對象為Tair執行個體中的TairBloom資料。

提前規劃好初始容量與錯誤率，若目標key的預計容量遠大於100，請通過BF.RESERVE建立TairBloom，不建議直接執行BF.ADD命令。

直接執行BF.ADD與執行BF.RESERVE的區別如下。

BF.ADD（或BF.MADD）：執行時若目標key不存在，Tair會自動建立TairBloom，預設容量（capacity）為100，錯誤率（error_rate）為0.01。若您的容量遠遠大於100，後續僅能通過擴容增加元素。
而TairBloom的擴容是通過增加Bloom Filter的層數來完成，每一層容量將增長，但是隨著不斷的擴容，TairBloom內部的層數會越來越多，此時會導致完成查詢任務需要遍曆多層Bloom Filter，效能將嚴重下降。
BF.RESERVE（或BF.INSERT）：執行時需要設定capacity（初始容量），該命令會在TairBloom的第一層初始化設定的容量，在TairBloom內部的Bloom Filter層數少，查詢速度快。

說明

以插入10,000,000個元素、錯誤率為0.01為例，直接通過BF.ADD建立，TairBloom需佔用176 MB；而通過BF.RESERVE建立時僅佔用16 MB。

雖然TairBloom支援擴容，但在實際使用過程中請避免發生擴容操作，建議將該功能視為保障措施，若實際容量超過預設容量時，TairBloom能通過擴容操作，保障業務正常寫入，規避線上事故。

下表為通過BF.RESERVE建立不同初始容量和錯誤率的key所佔用的記憶體，僅供參考。

容量（元素的個數）	false positive:0.01	false positive:0.001	false positive:0.0001
100,000	0.12 MB	0.25 MB	0.25 MB
1,000,000	2 MB	2 MB	4 MB
10,000,000	16 MB	32 MB	32 MB
100,000,000	128 MB	256 MB	256 MB
1,000,000,000	2 GB	2 GB	4 GB

由於TairBloom只能插入新元素且無法刪除已有元素，因此TairBloom的記憶體佔用量只會增加不會減少。為防止TairBloom越來越大，甚至導致Redis記憶體溢出（Out Of Memory），向您提供如下使用建議。
- 拆分業務資料：拆分、細化業務資料，避免將大量資料存入一個TairBloom中，這樣不僅會導致這個key過大，影響查詢效能，同時也會由於這個key中插入了過多資料，大部分的查詢流量都會請求到這個key所在的Redis執行個體上，從而造成熱點key，甚至發生訪問傾斜的情況。
  請拆分業務資料，將資料分散到多個TairBloom中，若您的執行個體為叢集執行個體，您可以將TairBloom分散到叢集內的各個執行個體上，均衡記憶體容量與流量，充分發揮分布式叢集的優勢。
- 定期重建：如果業務允許，您可以定期重建TairBloom，通過DEL刪除TairBloom，從後端資料庫拉取資料並重建TairBloom，以控制TairBloom的大小。
  您也可以在初期建立多個TairBloom，並採用多個TairBloom輪轉切換的方式實現控制單個TairBloom的大小。該方案的優點為僅需建立一次TairBloom，無需頻繁地重建TairBloom，缺點是需要建立多個TairBloom，會浪費部分記憶體空間。

命令列表

表 1. TairBloom命令

命令	文法	說明
BF.RESERVE	`BF.RESERVE key error_rate capacity`	建立一個大小為capacity，錯誤率為error_rate的空的TairBloom。
BF.ADD	`BF.ADD key item`	在Key指定的TairBloom中添加一個元素。
BF.MADD	`BF.MADD key item [item ...]`	在Key指定的TairBloom中添加多個元素。
BF.EXISTS	`BF.EXISTS key item`	檢查一個元素是否存在於Key指定的TairBloom中。
BF.MEXISTS	`BF.MEXISTS key item [item ...]`	同時檢查多個元素是否存在於Key指定的TairBloom中。
BF.INSERT	`BF.INSERT key [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS item [item ...]`	在Key指定的TairBloom中一次性添加多個元素，添加時可以指定大小和錯誤率，且可以控制在TairBloom不存在的時候是否自動建立。
BF.INFO	`BF.INFO key`	查看Key指定的TairBloom內部資訊，如當前層數和每一層的元素個數、錯誤率等。
DEL	`DEL key [key ...]`	使用原生Redis的DEL命令可以刪除一條或多條TairBloom資料。說明已加入TairBloom資料中的元素無法單獨刪除，您可以使用DEL命令刪除整條TairBloom資料。

說明本文的命令文法定義如下：

大寫關鍵字：命令關鍵字。
斜體：變數。
[options]：選擇性參數，不在括弧中的參數為必選。
A|B：該組參數互斥，請進行二選一或多選一。
...：前面的內容可重複。

BF.RESERVE

類別	說明
文法	`BF.RESERVE key error_rate capacity`
時間複雜度	O(1)
命令描述	建立一個大小為capacity，錯誤率為error_rate的空的TairBloom。
選項	Key：Key名稱（TairBloom資料結構），用於指定作為命令調用對象的TairBloom。 error_rate：期望的錯誤率（False Positive Rate），該值必須介於0和1之間。該值越小，精度越高，TairBloom的記憶體佔用量越大，CPU使用率越高。 capacity：TairBloom的初始容量，即期望添加到TairBloom中的元素的個數。當實際添加的元素個數超過該值時，TairBloom將通過增加Bloom Filter的層數完成自動擴容，該過程會導致查詢效能下降。每增加一層，就可能需要遍曆多層Bloom Filter來完成查詢。因此，如果對效能非常的敏感，需要在使用前充分評估要添加到TairBloom的元素個數，避免發生導致層數增加的擴容操作。
傳回值	OK：表示執行成功。其它情況返回相應的異常資訊。
樣本	命令樣本： `BF.RESERVE BFKEY 0.01 100` 返回樣本： `OK`

BF.ADD

類別	說明
文法	`BF.ADD key item`
時間複雜度	O(log N) ，其中N是TairBloom的層數。
命令描述	在Key指定的TairBloom中添加一個元素。說明若目標Key不存在，Tair會自動建立一個TairBloom，建立TairBloom的預設容量（capacity）為100，錯誤率（error_rate）為0.01。
選項	Key：Key名稱（TairBloom資料結構），用於指定作為命令調用對象的TairBloom。 item：需要添加到TairBloom的元素。
傳回值	1：表示該元素之前一定不存在，並往TairBloom中添加該元素。 0：表示該元素可能已存在，所以不會進行添加或更新操作。其它情況返回相應的異常資訊。
樣本	命令樣本： `BF.ADD BFKEY item1` 返回樣本： `(integer) 1`

BF.MADD

類別	說明
文法	`BF.MADD key item [item ...]`
時間複雜度	O(log N) ，其中N是TairBloom的層數。
命令描述	在Key指定的TairBloom中添加多個元素。說明若目標Key不存在，Tair會自動建立一個TairBloom，建立TairBloom的預設容量（capacity）為100，錯誤率（error_rate）為0.01。
選項	Key：Key名稱（TairBloom資料結構），用於指定作為命令調用對象的TairBloom。 item：需要添加到TairBloom的元素，可設定多個。
傳回值	1：表示該元素之前一定不存在，並往TairBloom中添加該元素。 0：表示該元素可能已存在，所以不會進行添加或更新操作。其它情況返回相應的異常資訊。
樣本	命令樣本： `BF.MADD BFKEY item1 item2 item3` 返回樣本： `(integer) 1 (integer) 1 (integer) 1`

BF.EXISTS

類別	說明
文法	`BF.EXISTS key item`
時間複雜度	O(log N) ，其中N是TairBloom的層數。
命令描述	檢查一個元素是否存在於Key指定的TairBloom中。
選項	Key：Key名稱（TairBloom資料結構），用於指定作為命令調用對象的TairBloom。 item：需要查詢的元素。
傳回值	0：表示該元素一定不存在。 1：表示該元素可能存在。其它情況返回相應的異常資訊。
樣本	命令樣本： `BF.EXISTS BFKEY item1` 返回樣本： `(integer) 1`

BF.MEXISTS

類別	說明
文法	`BF.MEXISTS key item [item ...]`
時間複雜度	O(log N) ，其中N是TairBloom的層數。
命令描述	同時檢查多個元素是否存在於Key指定的TairBloom中。
選項	Key：Key名稱（TairBloom資料結構），用於指定作為命令調用對象的TairBloom。 item：需要查詢的元素，可設定多個。
傳回值	0：表示該元素一定不存在。 1：表示該元素可能存在。其它情況返回相應的異常資訊。
樣本	命令樣本： `BF.MEXISTS BFKEY item1 item5` 返回樣本： `(integer) 1 (integer) 0`

BF.INSERT

類別	說明
文法	`BF.INSERT key [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS item [item ...]`
時間複雜度	O(log N) ，其中N是TairBloom的層數。
命令描述	在Key指定的TairBloom中一次性添加多個元素，添加時可以指定大小和錯誤率，且可以控制在TairBloom不存在的時候是否自動建立。
選項	Key：Key名稱（TairBloom資料結構），用於指定作為命令調用對象的TairBloom。 capacity：TairBloom的初始容量，即期望添加到TairBloom中元素的個數，當TairBloom已經存在時該值將被忽略。當實際添加的元素個數超過該值時，TairBloom將進行自動的擴容，該過程會導致效能有所下降，下降的程度是隨著元素個數的增長而下降的，這是因為TairBloom的擴容是通過增加Bloom Filter的層數來完成的。每增加一層，在查詢的時候就可能會遍曆多層Bloom Filter來完成，每一層的容量都是上一層的兩倍。因此，如果對效能非常的敏感，需要在使用前充分評估要添加到TairBloom的元素個數，避免發生擴容操作。 error_rate：期望的錯誤率（False Positive Rate），該值必須介於0和1之間。該值越小，精度越高，TairBloom的記憶體佔用量越大，CPU使用率越高。 NOCREATE：設定該選項後，當指定的TairBloom不存在的時候不要自動建立該TairBloom。該參數不能與CAPACITY和ERROR同時設定。 item：需要添加的元素，可設定多個。
傳回值	1：表示該元素之前一定不存在，並往TairBloom中添加該元素。 0：表示該元素可能已存在，所以不會進行添加或更新操作。其它情況返回相應的異常資訊。
樣本	命令樣本： `BF.INSERT bfkey1 CAPACITY 10000 ERROR 0.001 ITEMS item1 item2 item3` 返回樣本： `(integer) 1 (integer) 1 (integer) 1`

BF.INFO

類別	說明
文法	`BF.INFO key`
時間複雜度	O(log N) ，其中N是TairBloom的層數。
命令描述	查看Key指定的TairBloom內部資訊，如當前層數和每一層的元素個數、錯誤率等。
選項	Key：Key名稱（TairBloom資料結構），用於指定作為命令調用對象的TairBloom。
傳回值	執行成功將返回TairBloom資訊。其它情況返回相應的異常資訊。
樣本	命令樣本： `BF.INFO bk1` 返回樣本： `1) "total_items:6,num_blooms:2" 2) "bytes:4 bits:32 hashes:7 hashwidth:64 capacity:3 items:3 error_ratio:0.01" 3) "bytes:16 bits:128 hashes:9 hashwidth:64 capacity:10 items:3 error_ratio:0.0025"` BF.INFO返回參數說明： total_items表示總元素數量、num_blooms表示總Bloom Filter層數。每層Bloom Filter的資訊： bytes：佔用位元組數。 bits：佔用bit位元，bits = bytes * 8。 hashes：Hash函數數量。 hashwidth：Hash函數寬度。 capacity：容量。 items：元素數量。 error_ratio：錯誤率。