100 more of those BITFIELDs

2016-02-26

再來 100 個 BITFIELD

原文由 Salvatore Sanfilippo 于 2016-02-26 發布，訂閱此部落格

今天 Redis 滿 7 歲了，為了稍微紀念一下這個日子，我花了最近幾天進行了一場有趣的程式馬拉松，實作了一個名叫 BITFIELD 的瘋狂新指令。

這個指令的核心概念其實並不新，過去我和其他人都曾提過，但從來沒有認真看待過，這個想法總是看起來有點奇怪。Redis 本來就已經有位元操作了：有些使用者很喜歡，這是把大量資料以精簡方式呈現的好方法。不過到目前為止，我們都是逐一分開處理每個位元，設定、測試、取得位元，計算某個範圍內被設定的位元數量等等。

那何不來實作 bitfield 呢？不論是短是長、任意大小的整數，放在任意的偏移位置上，讓我可以把一個 Redis 字串當作由 5 位元有號整數組成的陣列來用，一點空間都不浪費。

幾天前，來自 Redis Labs 的 Yoav Steinberg 比較認真地提出了一組指令，用來處理儲存在位元偏移上的任意大小整數。讀到那封郵件時我笑了，因為這有點算是我的秘密夢想。以 Yoav 的提案為起點，再加上其他 Redis Labs 工程師的回饋，我寫出了一個單一指令搭配子指令的初步規格，用簡短的名稱來定義型別，並對溢位語意加入非常細緻的控制。

幾分鐘前我剛完成第一版實作，因為原本的計畫就是要在今天發布，希望 Redis 能感受到我們在它生日這天真的有在做事。

完成後的 BITFIELD 指令支援以下幾種子指令：

SET <type> <offset> <value> — 設定指定的值並回傳其舊值。

GET <type> <offset> — 取得指定的值。

INCRBY <type> <offset> <increment> — 遞增指定的計數器。

還有一個額外的中繼指令叫做 OVERFLOW（猜猜看是做什麼的），用來設定後續指令的溢位語意（所以 OVERFLOW 可以指定多次）：

OVERFLOW SAT — 飽和模式，也就是當往某個方向溢位時，會讓整數飽和在該溢位方向的最大值。

OVERFLOW WRAP — 這就是一般的繞回，但有趣的是，這對有號整數也適用，會朝最負或最正的值繞回。

OVERFLOW FAIL — 在這個模式下，如果會造成溢位，操作就完全不會執行。

整數型別可以用「u」或「i」前綴加上位元數來指定，例如 u8、i5、u20 和 i53 都是合法的型別。有一個限制：目前無法指定 u64，因為 Redis 協定還無法回傳 64 位元無號整數。

來舉幾個例子：要遞增一個 8 位元無號整數，我可以這樣做：

127.0.0.1:6379> BITFIELD mykey incrby u8 100 1
1) (integer) 3

這是在偏移 100 的位置（也就是 bitmap 中的第 101 個位元）遞增一個 8 位元無號整數。

不過還有另一種指定偏移的方式，就是在偏移前加上「#」，意思是：「把字串當作指定大小的計數器陣列，來設定第 N 個計數器」。基本上這代表如果你對 8 位元型別使用 #10，偏移量就是用 8*10 計算得來，這樣我就能各自獨立地定址多個計數器，而不需要自己計算偏移量：

127.0.0.1:6379> BITFIELD mykey incrby u8 #0 1
1) (integer) 1
127.0.0.1:6379> BITFIELD mykey incrby u8 #0 1
1) (integer) 2
127.0.0.1:6379> BITFIELD mykey incrby u8 #1 1
1) (integer) 1
127.0.0.1:6379> BITFIELD mykey incrby u8 #1 1
1) (integer) 2

能夠控制溢位也很有趣。例如，一個 1 位元的無號計數器在預設的「wrap」溢位策略下，其實會在 0 和 1 之間切換：

127.0.0.1:6379> BITFIELD mykey incrby u1 100 1
1) (integer) 1
127.0.0.1:6379> BITFIELD mykey incrby u1 100 1
1) (integer) 0
127.0.0.1:6379> BITFIELD mykey incrby u1 100 1
1) (integer) 1
127.0.0.1:6379> BITFIELD mykey incrby u1 100 1
1) (integer) 0

如你所見，它會在 0 和 1 之間交替。

飽和模式也很有用：

127.0.0.1:6379> bitfield mykey overflow sat incrby i4 100 -3
1) (integer) -3
127.0.0.1:6379> bitfield mykey overflow sat incrby i4 100 -3
1) (integer) -6
127.0.0.1:6379> bitfield mykey overflow sat incrby i4 100 -3
1) (integer) -8
127.0.0.1:6379> bitfield mykey overflow sat incrby i4 100 -3
1) (integer) -8

如你所見，每次遞減 3，數值永遠不會低於 -8。

請注意，你可以在單一指令中執行多個操作。它永遠會回傳一個結果陣列：

127.0.0.1:6379> BITFIELD mykey get i4 100 set u8 200 123 incrby u8 300 1
1) (integer) -8
2) (integer) 123
3) (integer) 7

這個指令預期的用途是即時分析、A/B 測試、利用整數溢位每次向使用者顯示稍微不同的內容。把這麼多小型計數器以共享且節省記憶體的方式打包在一起，可以玩出很多花樣，但這就留給 Redis 社群中才華洋溢的程式設計師們去發揮了。

這個指令在接下來幾週內會被回溯移植到 Redis 的穩定版本，所以很快就能使用了。

對實作感到好奇嗎？它可能比你想像的還要複雜：https://github.com/antirez/redis/commit/70af626d613ebd88123f87a941b0dd3570f9e7d2

再來 100 個 BITFIELD

留言