程序員的成長(zhǎng)之路

互聯(lián)網(wǎng)/程序員/技術(shù)/資料共享?

閱讀本文大概需要 4 分鐘。

來(lái)自：toutiao.com/i6767642839267410445

本文主要和大家分享一下redis的高級(jí)特性：bit位操作。

本文redis試驗(yàn)代碼基于如下環(huán)境：

操作系統(tǒng)：Mac OS 64位版本：Redis 5.0.7 64 bit 運(yùn)行模式：standalone mode

redis位操作

reids位操作也叫位數(shù)組操作、bitmap，它提供了SETBIT、GETBIT、BITCOUNT、BITTOP四個(gè)命令用于操作二進(jìn)制位數(shù)組。

先來(lái)看一波基本操作示例：

SETBIT

語(yǔ)法：SETBIT key offset value

即：命令 key 偏移量 0/1

setbit命令用于寫(xiě)入位數(shù)組指定偏移量的二進(jìn)制位設(shè)置值，偏移量從0開(kāi)始計(jì)數(shù)，且只允許寫(xiě)入1或者0，如果寫(xiě)入非0和1的值則寫(xiě)入失?。?/section>

GETBIT

語(yǔ)法：GETBIT key offset

即：命令 key 偏移量

gitbit命令用于獲取位數(shù)組指定偏移量上的二進(jìn)制值：

BITCOUNT

語(yǔ)法：BITCOUNT key

即：命令 key

bitcount命令用于獲取指定key的位數(shù)組中值為1的二進(jìn)制位的數(shù)量，之前我們寫(xiě)入了偏移量0的值為1，偏移量10 的值為1，偏移量8的值為0：

BITOP

語(yǔ)法：BITOP operation destkey key [key…]

即：命令操作結(jié)果目標(biāo)key key1 key2 …

bitop命令可以對(duì)多個(gè)位數(shù)組的key進(jìn)行and（按位與）、or（按位或）、xor（按位異或）運(yùn)算，并將運(yùn)算結(jié)果設(shè)置到destkey中：

底層數(shù)據(jù)結(jié)構(gòu)分析

SDS是redis中的一種數(shù)據(jù)結(jié)構(gòu)，叫做簡(jiǎn)單動(dòng)態(tài)字符串（Simple Dynamic String），并且它是一種二進(jìn)制安全的，在大多數(shù)的情況下redis中的字符串都用SDS來(lái)存儲(chǔ)。

SDS的數(shù)據(jù)結(jié)構(gòu)：

struct?sdshdr?{
?#記錄buff數(shù)組中已使用字節(jié)的數(shù)量
?#也是SDS所保存字符串的長(zhǎng)度
?int?len;
?#記錄buff數(shù)組中未使用字節(jié)的數(shù)量
?int?free;
?#字節(jié)數(shù)組，字符串就存儲(chǔ)在這個(gè)數(shù)組里
?char?buff\[\];
}

數(shù)據(jù)存儲(chǔ)示例：

SDS的優(yōu)點(diǎn)：

時(shí)間復(fù)雜度為O(1)
杜絕緩沖區(qū)溢出
減少修改字符串長(zhǎng)度時(shí)候所需的內(nèi)存重分配次數(shù)
二進(jìn)制安全的API操作
兼容部分C字符串函數(shù)

redis中的位數(shù)組采用的是String字符串?dāng)?shù)據(jù)格式來(lái)存儲(chǔ)，而字符串對(duì)象使用的正是上文說(shuō)的SDS簡(jiǎn)單動(dòng)態(tài)字符串?dāng)?shù)據(jù)結(jié)構(gòu)。

大家都知道的是一個(gè)字節(jié)用的是8個(gè)二進(jìn)制位來(lái)存儲(chǔ)的，也就是8個(gè)0或者1，即一個(gè)字節(jié)可以存儲(chǔ)十進(jìn)制0~127的數(shù)字，也即包含了所有的數(shù)字、英文大小寫(xiě)字母以及標(biāo)點(diǎn)符號(hào)。

1Byte=8bit 1KB=1024Byte 1MB=1024KB 1GB=1024MB

位數(shù)組在redis存儲(chǔ)世界里，每一個(gè)字節(jié)也是8位，初始都是：

0?0?0?0?0?0?0?0

而位操作就是在對(duì)應(yīng)的offset偏移量上設(shè)置0或者1，比如將第3位設(shè)置為1，即：

0?0?0?0?1?0?0?0
#對(duì)應(yīng)redis操作即：
setbit?key?3?1

在此基礎(chǔ)上，如果要在偏移量為13的位置設(shè)置1，即：

setbit?key?13?1
#對(duì)應(yīng)redis中的存儲(chǔ)為：
0?0?1?0?|?0?0?0?0?|?0?0?0?0?|?1?0?0?0

時(shí)間復(fù)雜度

GETBIT命令時(shí)間復(fù)雜度O(1)

STEBIT命令時(shí)間復(fù)雜度O(1)

BITCOUNT命令時(shí)間復(fù)雜度O(n)

BITOP命令時(shí)間復(fù)雜度O(n)、O(n2)

我們來(lái)看GETBIT以及SETBIT命令的時(shí)間復(fù)雜度為什么是O(1)，當(dāng)我們執(zhí)行一個(gè)SETBIT key 10086 1的值的時(shí)候，reids的計(jì)算方式如下：

獲取到要寫(xiě)入位數(shù)組中的哪個(gè)字節(jié)：10086÷8=1260，需要寫(xiě)入到位數(shù)組的下標(biāo)1260的字節(jié)

獲取要寫(xiě)入到這個(gè)字節(jié)的第幾位：10086 mod 8 = 6，需要寫(xiě)入到這個(gè)字節(jié)的下標(biāo)為6即第7位上去。

通過(guò)這兩種計(jì)算方式大家可以清晰的看到，位操作的GETBIT和SETBIT都是常量計(jì)算，因此它的時(shí)間復(fù)雜度為O(1)。

而B(niǎo)ITCOUNT命令需要對(duì)整個(gè)位數(shù)組的所有元素進(jìn)行遍歷算出值為1的有多少個(gè)，當(dāng)然redis對(duì)于大數(shù)據(jù)了的bit執(zhí)行bitcount命令會(huì)有一整套復(fù)雜的優(yōu)化的算法，但是核心思路還是這個(gè)意思，無(wú)非是減少部分遍歷查詢(xún)次數(shù)。比如以128位為一次遍歷，那么他的遍歷次數(shù)就是所有的位數(shù)除以128。

BITTOP命令則是根據(jù)不同的操作有不同的執(zhí)行方式。比如AND操作，則需要查看位值為1的即可。

存儲(chǔ)空間計(jì)算

根據(jù)上面的介紹，相信大家已經(jīng)知道了基于redis的位數(shù)組數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的數(shù)據(jù)占用內(nèi)存大小是怎么計(jì)算的了。比如有100億的數(shù)據(jù)，那么它需要的字節(jié)數(shù)組：

1000000000÷8÷1024÷1024≈119.21MB

也就是存儲(chǔ)10億的數(shù)據(jù)只需要119MB左右的內(nèi)存空間，這對(duì)于現(xiàn)在動(dòng)輒16G、32G集群版的redis，完全沒(méi)有問(wèn)題。

需要注意的是，如果你的數(shù)據(jù)量不大，那就不要把起始偏移量搞的很大，這樣也是占空間的，比如我們只需要存儲(chǔ)幾百條數(shù)據(jù)，但是其中的偏移量卻很大，這就會(huì)造成了很大的內(nèi)存空間浪費(fèi)。

應(yīng)用場(chǎng)景

實(shí)際項(xiàng)目開(kāi)發(fā)中有很多業(yè)務(wù)都適合采用redis的bit來(lái)實(shí)現(xiàn)。

用戶(hù)簽到場(chǎng)景

每天的日期字符串作為一個(gè)key，用戶(hù)Id作為offset，統(tǒng)計(jì)每天用戶(hù)的簽到情況，總的用戶(hù)簽到數(shù)

活躍用戶(hù)數(shù)統(tǒng)計(jì)

用戶(hù)日活、月活、留存率等均可以用redis位數(shù)組來(lái)存儲(chǔ)，還是以每天的日期作為key，用戶(hù)活躍了就寫(xiě)入offset為用戶(hù)id的位值1。

同理月活也是如此。

用戶(hù)是否在線(xiàn)以及總在線(xiàn)人數(shù)統(tǒng)計(jì)

同樣是使用一個(gè)位數(shù)組，用戶(hù)的id映射偏移量，在線(xiàn)標(biāo)識(shí)為1，下線(xiàn)標(biāo)識(shí)為0。即可實(shí)現(xiàn)用戶(hù)上下線(xiàn)查詢(xún)和總在線(xiàn)人數(shù)的統(tǒng)計(jì)

APP內(nèi)用戶(hù)的全局消息提示小紅點(diǎn)

現(xiàn)在大多數(shù)的APP里都有站內(nèi)信的功能，當(dāng)有消息的時(shí)候，則提示一個(gè)小紅點(diǎn)，代表用戶(hù)有新的消息。

推薦閱讀：

交公糧了：十一在家我都逛哪些技術(shù)網(wǎng)站？

訂單系統(tǒng)：從0到1設(shè)計(jì)思路

5T技術(shù)資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機(jī)，樹(shù)莓派，等等。在公眾號(hào)內(nèi)回復(fù)「2048」，即可免費(fèi)獲取??！

微信掃描二維碼，關(guān)注我的公眾號(hào)

朕已閱?

這么搞，10 億數(shù)據(jù)量只需要 100MB 內(nèi)存