[[381030]]

本文轉載自微信公眾號「Java極客技術」，作者 鴨血粉絲  。轉載本文請聯系Java極客技術公眾號。

Redis 作為當代互聯網行業無可替代的 Key-Value 數據庫，在我們日常的工作中占據主要的角色，對于常用的命令相信大家都很熟悉。今天給大家分享一個平時可能用到的少，但是也很重要的一個類型 BitArray。我們先通過簡單的命令使用，了解該命令的用法，然后再給大家介紹一下底層的實現原理，幫助大家更好的了解。

簡單使用

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

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

通過redis-cli 鏈接客戶端，執行相應的命令，接下來使用一下 BitArray 相關的命令，

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

接下來我們再創建一個名為test2的位數組，并且通過多次使用 setbit 命令和 bitcount ，bitcount 命令的作用是用來統計位數組中 1 的個數，通過下面我們看到第一次使用 bitcount test2 命令時結果為 1，當使用了 setbit test2 1 1 命令后再次使用 bitcount 命令我們發現結果已經變成 2 了。其中test2 的剛開始是0000 0100 后面變成0000 0101。

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

原理

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

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

SETBIT

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

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

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

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

GETBIT

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

1. 找到對應的字節數組 byte = offset / 8;
2. 計算出對應的 bit 位bit = (offset mod 8) + 1;

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

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

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

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

BITCOUNT 命令

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

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

BITOP 命令

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

參考資料

Redis 設計與實現(第二版)