[[381030]]

本文轉(zhuǎn)載自微信公眾號「Java極客技術(shù)」，作者 鴨血粉絲  。轉(zhuǎn)載本文請聯(lián)系Java極客技術(shù)公眾號。

Redis 作為當代互聯(lián)網(wǎng)行業(yè)無可替代的 Key-Value 數(shù)據(jù)庫，在我們?nèi)粘５墓ぷ髦姓紦?jù)主要的角色，對于常用的命令相信大家都很熟悉。今天給大家分享一個平時可能用到的少，但是也很重要的一個類型 BitArray。我們先通過簡單的命令使用，了解該命令的用法，然后再給大家介紹一下底層的實現(xiàn)原理，幫助大家更好的了解。

簡單使用

我們先看下什么是BitArray 位數(shù)組。Redis 使用字符串對象來存儲位數(shù)組，一個 Byte 字節(jié)有 8 個 bit 位，通過控制每一個 bit 位為 0 或者 1來表示某個元素對應(yīng)的值或者狀態(tài)。通過使用 8 個 bit 位可以對復雜操作節(jié)省很多的空間。BitArray 相關(guān)的操作命令有 SETBIT,GETBIT,BITCOUNT,BITOP。下面我們依次看下命令的使用，最后再看下實現(xiàn)的原理。

首先我們在本地啟動一個 Redis 實例，再啟動一個客戶端去鏈接如下圖，

通過redis-cli 鏈接客戶端，執(zhí)行相應(yīng)的命令，接下來使用一下 BitArray 相關(guān)的命令，

通過setbit test 2 1 命令我們創(chuàng)建了一個名為 test 的 bitarray 并將其第二位設(shè)置成 1，再使用getbit test 2 獲取對應(yīng)位的值。setbit命令功能是將對應(yīng)的 key 指定 offset 的位置設(shè)置為 1 或 0，getbit 命令是獲取指定 offset 位置的值。test 是一個位數(shù)組通過上面的命令值變成0000 0010 。

接下來我們再創(chuàng)建一個名為test2的位數(shù)組，并且通過多次使用 setbit 命令和 bitcount ，bitcount 命令的作用是用來統(tǒng)計位數(shù)組中 1 的個數(shù)，通過下面我們看到第一次使用 bitcount test2 命令時結(jié)果為 1，當使用了 setbit test2 1 1 命令后再次使用 bitcount 命令我們發(fā)現(xiàn)結(jié)果已經(jīng)變成 2 了。其中test2 的剛開始是0000 0100 后面變成0000 0101。

bitop 命令相信大家都能理解，都是一些與，或，異或，非的運算，就不贅述了，具體使用可以看上圖。

原理

前面說到 Redis 是通過字符串對象來實現(xiàn)位數(shù)組的，所以字符串對象有的功能，在位數(shù)組上面都是有的，在Redis 底層位數(shù)組的存儲結(jié)構(gòu)也是基于 SDS (簡單動態(tài)字符串)的，如下：

其中 len 字段表示包含的 buf 數(shù)組的個數(shù)，buf[i] 表示的是第i個字節(jié)數(shù)組里面具體的數(shù)值，buf[len] 是末尾的分隔符\0 。上圖中的buf[0] 是一個字節(jié)，其中有 8 個 bit 位，在使用了 setbit 命令后初始值為0000 0000，buf[1] 中就是分隔符\0。

SETBIT

當我們執(zhí)行setbit key offset value 命令時，我們分兩步：

1. 計算出創(chuàng)建多少個字節(jié)數(shù)組(offset / 8) + 1;
2. 判斷是否長度不夠需要進行擴容;
3. 計算出 offset 對應(yīng)的字節(jié)位置 byte = offset / 8;
4. 計算出 offset 對應(yīng)的 bit 位，bit = (offset mod 8) + 1;
5. 根據(jù) offset 找到對應(yīng)的位置將此處的值改成value 并返回舊值;

假設(shè)我們執(zhí)行的命令時setbit test2 3 1，第一步先計算字節(jié)個數(shù) (3 / 8) + 1 = 1，計算出來我們只需要一個字節(jié);第二步跟原始 len 進行比較，發(fā)現(xiàn)不需要擴容;3. 根據(jù) offset 計算存放的字節(jié) 3 / 8 = 0 則，存放的 buf[0] 中;第四部計算 bit，( 3 mod 8) + 1 = 4，表示的是第四個 bit 位。經(jīng)過一輪 test2 就變成了0000 1000。

setbit 命令執(zhí)行的操作都是常數(shù)級別的，時間復雜度為 O(1)。

GETBIT

我們知道的setbit 命令是如何實現(xiàn)的，那么getbit 命令也就知道如何計算了，過程是類似的。

1. 找到對應(yīng)的字節(jié)數(shù)組 byte = offset / 8;
2. 計算出對應(yīng)的 bit 位bit = (offset mod 8) + 1;

經(jīng)過上面的計算我們可以知道當執(zhí)行命令 getbit test2 3 的時候，先算出 3 / 8 = 0 ，找到 buf[0]，再使用(3 mod 8) + 1 = 4，找到 bit 位。

看到這里細心的小伙伴就會有疑問，會說不對啊，根據(jù)這個計算返回的值應(yīng)該是 0 啊，因為上面 setbit命令執(zhí)行完的結(jié)果是0000 1000 啊。

能發(fā)現(xiàn)這個問題的小伙伴說明很用心在看了，這里就要跟大家說下了，雖然 setbit 命令執(zhí)行完結(jié)果是0000 1000 但是在 「buf[0] 中存儲的確實反過來的，即為0001 0000」。采用的是逆序的方式來保存位數(shù)組的。

之所以采用逆序保存位數(shù)組是為了減少位數(shù)組的移動，提高性能，感興趣的小伙伴可以自行研究一下。

BITCOUNT 命令

bitcount 命令是用來計算一個位數(shù)組中 1 的個數(shù)，說起來比較簡單，但是實現(xiàn)起來卻很有講究。我們設(shè)想一下，統(tǒng)計一個位數(shù)組中 1 的個數(shù)有多少個，最簡單的辦法就是遍歷，依次累加。但是當我們的位數(shù)組很大的時候，整個效率就會變得非常慢，因為遍歷是跟長度正相關(guān)的，當存放 100MB 的位數(shù)組整個遍歷需要八億次。而當達到 500MB 時整個遍歷就達到了四十億次!

在 Redis 中采用的是查表和 variable-precision SWAR 算法，查表是指當位數(shù)組長度小于 128 時，直接根據(jù)預(yù)設(shè)的映射表找到對應(yīng) 1 的個數(shù)，直接返回。而variable-precision SWAR 算法相對比較復雜，阿粉也還要再研究研究，今天就先不分享了。

BITOP 命令

bitop 命令相對簡單一點，因為 Redis 底層是基于 C 語言實現(xiàn)的，C語言本身就支持相關(guān)的邏輯運算。因為本身就是二進制位數(shù)組，所以對應(yīng)的邏輯運算會簡單很多就不贅述了，相信大家都能理解。

參考資料

Redis 設(shè)計與實現(xiàn)(第二版)