[[381030]]

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

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

簡單使用

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

首先我們在本地啟動(dòng)一個(gè) Redis 實(shí)例，再啟動(dòng)一個(gè)客戶端去鏈接如下圖，

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

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

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

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

原理

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

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

SETBIT

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

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

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

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

GETBIT

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

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

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

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

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

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

BITCOUNT 命令

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

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

BITOP 命令

bitop 命令相對簡單一點(diǎn)，因?yàn)?Redis 底層是基于 C 語言實(shí)現(xiàn)的，C語言本身就支持相關(guān)的邏輯運(yùn)算。因?yàn)楸旧砭褪嵌M(jìn)制位數(shù)組，所以對應(yīng)的邏輯運(yùn)算會(huì)簡單很多就不贅述了，相信大家都能理解。

參考資料

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