2022Redis核心原理和應(yīng)?實(shí)踐

RedisRedis第第PAGE100226開篇：授人以魚不若授人以漁——Redis可以用來(lái)做什么 由Redis面試想到 小冊(cè)的內(nèi)容范 Redis可以做什么 小 擴(kuò)展閱 基礎(chǔ)：萬(wàn)丈高樓平地起——Redis基礎(chǔ)數(shù)據(jù)結(jié) Redis安 Redis基礎(chǔ)數(shù)據(jù)結(jié) string(字符串 list(列表 hash(字典 set(集合 容器型數(shù)據(jù)結(jié)構(gòu)的通用規(guī) 思考&作 擴(kuò)展閱 應(yīng)用1：千帆競(jìng)發(fā)——分布式 分布式 超時(shí)問 可重入 思考 應(yīng)用2：緩兵之計(jì)——延時(shí)隊(duì) 異步消息隊(duì) 隊(duì)列空了怎么辦 隊(duì)列延 空閑連接自動(dòng)斷 鎖沖突處 延時(shí)隊(duì)列的實(shí) 進(jìn)一步優(yōu) 思 應(yīng)用3：節(jié)衣縮食——位 基本使 統(tǒng)計(jì)和查 魔術(shù)指令 思考&作 應(yīng)用4：四兩撥千斤—— 使用方 pfadd這個(gè)pf是什么意思 pfmerge適合什么場(chǎng)合用 注意事 HyperLogLog實(shí)現(xiàn)原 pf的內(nèi)存占用為什么是 思考&作 擴(kuò)展閱 應(yīng)用5：層巒疊嶂——布隆過(guò)濾 布隆過(guò)濾器是什么 Redis中的布隆過(guò)濾 布隆過(guò)濾器基本使 注意事 布隆過(guò)濾器的原 空間占用估 實(shí)際元素超出時(shí)，誤判率會(huì)怎樣變 用不上Redis4.0怎么辦 布隆過(guò)濾器的其它應(yīng) 擴(kuò)展閱 應(yīng)用6：斷尾求生——簡(jiǎn)單限 如何使用Redis來(lái)實(shí)現(xiàn)簡(jiǎn)單限流策略 解決方 小 應(yīng)用7：一毛不拔——漏斗限 思 拓展閱 應(yīng)用8：近水樓臺(tái)—— 用數(shù)據(jù)庫(kù)來(lái)算附近的 GeoHash算 Redis的Geo指令基本使 小結(jié)&注意事 應(yīng)用9：大海撈針—— scan基礎(chǔ)使 字典的結(jié) scan遍歷順 字典擴(kuò) 對(duì)比擴(kuò)容縮容前后的遍歷順 漸進(jìn)式 更多的scan指 大key掃 擴(kuò)展閱 原理1：鞭辟入里——線程IO模 非阻塞 事件輪詢(多路復(fù)用 指令隊(duì) 響應(yīng)隊(duì) 定時(shí)任 擴(kuò)展閱 原理2：交頭接耳——通信協(xié) RESP(RedisSerialization 客戶端->服務(wù) 服務(wù)器->客戶 小 擴(kuò)展閱 原理3：未雨綢繆——持久 快照原 AOF原 AOF重 運(yùn) Redis4.0混合持久 思考 原理4：雷厲風(fēng)行——管 Redis的消息交 管道壓力測(cè) 深入理解管道本 小 原理5：同舟共濟(jì)——事 Redis事務(wù)的基本使 原子 優(yōu) 思考 原理6：小道消息—— 消息多 模式訂 消息結(jié) PubSub缺 補(bǔ) 原理7：開源節(jié)流——小對(duì)象壓 32bitvs 小對(duì)象壓縮存儲(chǔ) 內(nèi)存回收機(jī) 內(nèi)存分配算 擴(kuò)展閱 原理8：有備無(wú)患——主從同 CAP原 最終一 主從同 增量同 快照同 增加從節(jié) 無(wú)盤復(fù) Wait指 小 集群1：李代桃僵—— 消息丟 Sentinel基本使 作 集群2：分而治之—— Codis分片原 不同的Codis實(shí)例之間槽位關(guān)系如何同步 擴(kuò) 自動(dòng)均 Codis的代 Codis的優(yōu) MGET指令的操作過(guò) 架構(gòu)變 Codis的尷 Codis的后臺(tái)管 思考&作 集群3：眾志成城—— 槽位定位算 跳 遷 容 網(wǎng)絡(luò)抖 可能下線(PFAIL-PossiblyFail)與確定下線 Cluster基本使 槽位遷移感 集群變更感 思考&作 拓展1：耳聽八方—— 消息 消息內(nèi) 增刪改 獨(dú)立消 創(chuàng)建消費(fèi) 消 Stream消息太多怎么辦 消息如果忘記ACK會(huì)怎樣 PEL如何避免消息丟失 Stream的高可 分區(qū) 小 拓展2：無(wú)所不知——Info指 Redis每秒執(zhí)行多少次指令 Redis連接了多少客戶端 Redis內(nèi)存占用多大 復(fù)制積壓緩沖區(qū)多大 思 拓展3：拾遺漏補(bǔ)——再談分布式 Redlock算 Redlock使用場(chǎng) 擴(kuò)展閱 拓展4：朝生暮死——過(guò)期策 過(guò)期的key集 定時(shí)掃描策 從庫(kù)的過(guò)期策 拓展5：優(yōu)勝劣汰—— LRU算 近似LRU算 擴(kuò)展閱 思考&作 拓展6：平波緩進(jìn)——懶惰刪 Redis為什么要懶惰刪除(lazy 異步隊(duì) AOFSync也很 更多異步刪除 擴(kuò)展閱 拓展7：妙手仁心——優(yōu)雅地使用 重 作 拓展8：居安思?！Ｗo(hù) 指令安 端口安 Lua腳本安 SSL代 小 拓展9：隔墻有耳——Redis安全通 spiped原 spiped使用入 作 源碼1：極度深寒——探索「字符串」內(nèi)部結(jié) embstrvs 擴(kuò)容策 思 源碼2：極度深寒——探索「字典」內(nèi) dict內(nèi)部結(jié) 漸進(jìn)式 查找過(guò) hash函 hash攻 擴(kuò)容條 縮容條 set的結(jié) 思 源碼3：極度深寒——探索「壓縮列表」內(nèi) 增加元 級(jí)聯(lián)更 IntSet小整數(shù)集 思 源碼4：極度深寒——探索「快速列表」內(nèi) 每個(gè)ziplist存多少元素 壓縮深 擴(kuò)展閱 源碼5：極度深寒——探索「跳躍列表」內(nèi)部結(jié) 基本結(jié) 查找過(guò) 隨機(jī)層 插入過(guò) 刪除過(guò) 更新過(guò) 如果score值都一樣呢 元素排名是怎么算出來(lái)的 思 后 源碼6：極度深寒——探索「緊湊列表」內(nèi) 級(jí)聯(lián)更 取代 思 源碼7：極度深寒——探索「基數(shù)樹」內(nèi) 應(yīng) 結(jié) 增刪節(jié) 思 尾聲：百尺竿頭——繼續(xù)深造指 參考資 開篇：授人以魚不若授人以漁Redis可以用來(lái)做什么Redis是互聯(lián)網(wǎng)技術(shù)領(lǐng)域使用最為廣泛的存儲(chǔ)中間件，它是「RemoteService」的首字母縮寫，也就是「遠(yuǎn)程字典服務(wù)」。Redis以其超高的性能、完美的文檔、公司都在使用Redis，比如Twitter、YouPorn、暴雪娛樂、Github、StackOverflow、騰訊、Redis的了Redis面Redis技能的時(shí)候，面試官通常問的第一個(gè)問題就是“Redis能用來(lái)做什么？”，第一個(gè)回答往往都會(huì)是「緩存」。緩存確實(shí)是Redis使用最多的領(lǐng)域，它相比Memcache而言更加易于理解、使用和控制。Redis的鎖方法都是別人（應(yīng)該是架構(gòu)師）封裝好的，拿過(guò)來(lái)直接使用，內(nèi)部細(xì)節(jié)沒有去了Redis的面試題，之前準(zhǔn)備了很多，但是真正能Redis背后的原理和實(shí)踐經(jīng)驗(yàn)，做到知其然也知其所以然，為未來(lái)進(jìn)階成長(zhǎng)為架構(gòu)師做Redis最常用最核心知識(shí)點(diǎn)，但限于篇幅和精力，并沒有涵蓋Redis全部的內(nèi)容知識(shí)點(diǎn)，比如Redis內(nèi)置的lua腳本引擎就完全沒有提有一天流量漲上來(lái)了，Redis的這些稀有的高級(jí)功能勢(shì)必能立即派上用場(chǎng)。知。如果被采納，會(huì)考慮福利反饋。RedisRedis可以做什么Redis的業(yè)務(wù)應(yīng)用范圍非常廣泛，讓我們以掘金技術(shù)社區(qū)（juejin.im）的帖子模塊為實(shí)例，梳理一下，Redis可以用在哪些地方？1、記錄帖子的點(diǎn)贊數(shù)、評(píng)論數(shù)和點(diǎn)擊數(shù)(hash)2、記錄用戶的帖子ID(排序)，便于快速顯示用戶的帖子列表(zset)3、記錄帖子的標(biāo)題、摘要、作者和封面信息，用于列表頁(yè)展示(hash)4、記錄帖子的點(diǎn)贊用戶ID列表，評(píng)論ID列表，用于顯示和去重計(jì)數(shù)(zset)5、緩存近期熱帖內(nèi)容(帖子內(nèi)容空間占用比較大)，減少數(shù)據(jù)庫(kù)壓力(hash)6、記錄帖子的相關(guān)文章ID，(list)7、ID是整數(shù)自增的，RedisID(計(jì)數(shù)器)8、收藏集和帖子之間的關(guān)系(zset)9、記錄熱榜帖子ID列表，總熱榜和分類熱榜(zset)10、緩存用戶行為歷史，進(jìn)行惡意行為過(guò)濾(zset,hash)Redis的基礎(chǔ)應(yīng)用，也是日常開發(fā)中最常見的應(yīng)用（Redis基外，還有很多其它的Redis高級(jí)應(yīng)用，大多數(shù)同學(xué)可能從未接觸過(guò)，這部分我會(huì)在后續(xù)的章小Redis的基礎(chǔ)知識(shí)，這部分內(nèi)容估計(jì)本小冊(cè)大多數(shù)讀者都已經(jīng)非Redis基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)已經(jīng)了然于胸，可以直接跳到下一章節(jié)閱讀Redis的高級(jí)知識(shí)。位讀者務(wù)必堅(jiān)持到最后，相信你會(huì)明顯感受到技術(shù)能力的升華。大家加油RedisRedis面試總結(jié)的一篇原創(chuàng)分享，供大家參考閱讀，這篇文章也被IT技術(shù)圈大號(hào)「高可用架構(gòu)」轉(zhuǎn)載。RedisAntirezRedis6379？Redis由意大利人SalvatoreSanfilippo（網(wǎng)名Antirez）開發(fā)，上圖是他的個(gè)人照片。Antirez不僅帥的不像實(shí)力派，15年》，用自己的成長(zhǎng)經(jīng)歷來(lái)鼓勵(lì)那些非英語(yǔ)系的技Redis6379，這個(gè)端口號(hào)也不的位置決定的。「MERZ」在Antirez的朋友廣告女郎「AlessiaMerz」在電視節(jié)目上說(shuō)了一Antirez的朋友圈似乎有那么點(diǎn)猥瑣。AntirezRedis的開源事業(yè)持續(xù)貢獻(xiàn)力量。下面兩篇文章是老錢翻閱了Redis作者的Redis找到了一個(gè)新家——VMWare《Redis作者Antirez基礎(chǔ)：——Redis基千里之行，始于足下。本節(jié)我們的學(xué)習(xí)目標(biāo)是：快速理解并掌握Redis的基礎(chǔ)知識(shí)。Redis最簡(jiǎn)單最容易掌握的知識(shí)，如果讀者已經(jīng)很熟悉Redis本節(jié)的動(dòng)畫有點(diǎn)晃眼，閱讀起來(lái)不那么舒服，可以看看作者的另一篇文章《Redis數(shù)據(jù)結(jié)構(gòu)RedisRedisRedisRedisLinux或者M(jìn)acWindows可以考慮使用虛擬機(jī)。1、Docker安裝2、通過(guò)Github源碼編譯3、apt-getinstall(Ubuntu)、yuminstall(RedHat)brewinstall(Mac)。4、如果讀者懶于安裝操作，也可以使用網(wǎng)頁(yè)版的WebRedis直接體驗(yàn)。Docker方式redisdockerpullredis#運(yùn)行redis容器dockerrun--namemyredis-d-p6379:6379redis-clidockerexec-itmyredisredis-Githubgitclone--branch2.8--depth1cdredis#編譯cd，daemonize./redis-serverdaemonizeyes#運(yùn)行命令行./redis-#brewinstallredis#ubuntuapt-getinstallredis#redhatyuminstallredis#運(yùn)行客戶端redis-Redis基Redis有5種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，分別為：string(字符串)、list(列表)、set(集合)、hash(哈希)zset有序集合)5Redis知識(shí)最基礎(chǔ)也最重要的部分，它也是在Redis面試題中問到最多的內(nèi)容。Redis5Redis的命令非常string字符串字符串string是Redis最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。Redis所有的數(shù)據(jù)結(jié)構(gòu)都是以唯一的keykeyvalue數(shù)據(jù)。不同類型的數(shù)據(jù)結(jié)構(gòu)的差異就在于value的結(jié)構(gòu)不一樣。使用JSON序列化成字符串，然后將序列化后的字符串塞進(jìn)Redis來(lái)緩存。同樣，取用戶Redis的字符串是動(dòng)態(tài)字符串，是可以修改的字符串，內(nèi)部結(jié)構(gòu)實(shí)現(xiàn)上類似于Java的capacitylen1M時(shí)，擴(kuò)容都是加倍現(xiàn)有的空間，如果超過(guò)1M，擴(kuò)容時(shí)一次只會(huì)多擴(kuò)1M的空間。需要注意的是字符串最大長(zhǎng)度為512M。setnamecodeholegetnameexistsname(integer)1delname(integer)getnamesetname1codeholesetname2holycodermgetname1name2name3msetname1boyname2girlname3mgetname1name2setkey設(shè)置過(guò)期時(shí)間，到點(diǎn)自動(dòng)刪除，這個(gè)功能常用來(lái)控制緩存的失效時(shí)間。不過(guò)這個(gè)「自動(dòng)刪除」的機(jī)制是比較復(fù)雜的，如果你感興趣，可以繼續(xù)深入閱讀此書第26節(jié)《朝生暮死——setnamegetnameexpirename55s...#waitforgetnamesetexname5codehole5sgetname...#waitforgetnamesetnxnamecodeholenameset(integer)1getnamesetnxname(integer)0namesetgetnamevaluesignedlong的最大最小值，超過(guò)了這個(gè)值，Redissetage30incrage(integer)31incrbyage5(integer)36incrbyage-5(integer)31setcodehole9223372036854775807#Long.Maxincr(error)ERRincrementordecrementwould8bit組成，如此便可以將一個(gè)字符串看成很多bit的組合，這便是bitmap「位圖」數(shù)據(jù)結(jié)構(gòu)，位圖的具體使用會(huì)放到后面的章節(jié)來(lái)32節(jié)《極度深寒——list列表RedisJavaLinkedList，注意它是鏈表而不是數(shù)組。這意味著list的插入和刪除操作非?？?，時(shí)間復(fù)雜度為O(1)，但是索引定位很慢，時(shí)間復(fù)雜度為Redis的列表結(jié)構(gòu)常用來(lái)做異步隊(duì)列使用。將需要延后處理的任務(wù)結(jié)構(gòu)體序列化成字符串塞進(jìn)Redis的列表，另一個(gè)線程從這個(gè)列表中輪詢數(shù)據(jù)進(jìn)行處理。rpushbookspythonjavagolang(integer)3llenbooks(integer)3lpopbookslpopbookslpopbookslpopbooksrpushbookspythonjavagolang(integer)3rpopbooksrpopbooksrpopbooksrpoplindex相當(dāng)于Java鏈表的get(intindex)方法，它需要對(duì)鏈表進(jìn)行遍歷，性能隨著參數(shù)index增大而變差。ltrim和字面上的含義不太一樣，個(gè)人覺得它叫l(wèi)retain(保留)更合適一ltrim跟的兩個(gè)參數(shù)start_index和end_index定義了一個(gè)區(qū)間，在這個(gè)區(qū)間內(nèi)的值，ltrimltrim來(lái)實(shí)現(xiàn)一個(gè)定長(zhǎng)的鏈表，這一點(diǎn)非常有用。index可以為負(fù)數(shù)，index=-1index=-2表示倒數(shù)第二個(gè)元rpushbookspythonjava(integer)lindexbooks1O(n)lrangebooks01，O(n)ltrimbooks11O(n)lrangebooks0-ltrimbooks10llenbooks(integer)0Redis底層存儲(chǔ)的還不是一個(gè)簡(jiǎn)單的linkedlist，而是稱之為快速鏈表quicklist的一個(gè)結(jié)構(gòu)。首先在列表元素較少的情況下會(huì)使用一塊連續(xù)的內(nèi)存存儲(chǔ)，這個(gè)結(jié)構(gòu)是ziplist，也即是quicklist。因?yàn)槠胀ǖ逆湵硇枰母郊又羔樋臻g太大，會(huì)比較浪費(fèi)空間，而且會(huì)加重內(nèi)存的碎片化。比如這個(gè)列表里存的只是intprev和nextRedisziplistquicklist。也就是將多個(gè)ziplist使用雙向指針串起來(lái)使用。這樣既滿足了快速的插入刪除性能，又不會(huì)出現(xiàn)太大的空34節(jié)——探索「壓縮列表」內(nèi)部》和第35節(jié)《極度深寒——探索「快速列表」內(nèi)部》hash字典Redis的字典相當(dāng)于Java語(yǔ)言里面的HashMap，它是無(wú)序字典。內(nèi)部實(shí)現(xiàn)結(jié)構(gòu)上同JavaHashMap+hash的數(shù)組位置碰撞不同的是，Redis的字典的值只能是字符串，另外它們r(jià)ehash的方式不一樣，因?yàn)镴avaHashMap在字典很大時(shí)，rehashrehash。Redis為了高性能，不能堵塞服務(wù)，所以采用了漸進(jìn)式rehash策略。rehashrehashhash結(jié)構(gòu)，查詢時(shí)會(huì)同時(shí)查詢兩個(gè)hashhash的子指令中，循序漸進(jìn)地將舊hash的內(nèi)容一點(diǎn)點(diǎn)遷移到新的hash結(jié)構(gòu)中。當(dāng)hashhash結(jié)構(gòu)也可以用來(lái)存儲(chǔ)用戶信息，不同于字符串一次性需要全部序列化整個(gè)對(duì)象，hash可以對(duì)用戶結(jié)構(gòu)中的每個(gè)字段單獨(dú)存儲(chǔ)。這樣當(dāng)我們需要獲取用戶信息時(shí)可以進(jìn)行部分hash也有缺點(diǎn)，hashhash還是字符hsetbooksjavathinkinjava"(integer)1hsetbooksgolang"concurrencyingo"(integer)1hsetbookspython"pythoncookbook"(integer)1hgetallbooksentries()，keyvalue"thinkin"concurrencyin"pythonhlenbooks(integer)3hgetbooksjava"thinkinjava"hsetbooksgolang"learninggoprogramming"0(integer)0hgetbooksgolang"learninggohmsetbooksjava"effectivejava"python"learningpython"golang"moderngolangprogramming"#批量set同字符串一樣，hashkeyhincrby，和incr使用基本一樣。hincrbyuser-laoqianage1(integer)30關(guān)于字典的內(nèi)部結(jié)構(gòu)實(shí)現(xiàn)，請(qǐng)閱讀此書第33節(jié)《極度深寒——探索「字典」內(nèi)部》set集合RedisJavaHashSet，它內(nèi)部的鍵值對(duì)是無(wú)序的唯一的。它的內(nèi)部實(shí)現(xiàn)相當(dāng)于一個(gè)特殊的字典，字典中所有的value都是一個(gè)值NULL。set結(jié)構(gòu)可以用來(lái)存儲(chǔ)活動(dòng)中獎(jiǎng)的用戶ID，因?yàn)橛腥ブ毓δ?，可以保證同一個(gè)用戶不會(huì)中獎(jiǎng)兩次。saddbooks(integer)saddbookspython(integer)0saddbooksjavagolang(integer)2smembersbookssetsismemberbooksjavavaluecontains(o)(integer)1sismemberbooksrust(integer)0scardbookscount()(integer)3spopbookszsetzsetRedis提供的最為特色的數(shù)據(jù)結(jié)構(gòu)，它也是在面試中面試官最愛問的數(shù)據(jù)結(jié)JavaSortedSetHashMap的結(jié)合體，一方面它是一個(gè)set，保證了內(nèi)部value的唯一性，另一方面它可以給每個(gè)value賦予一個(gè)score，代表這個(gè)value的排序權(quán)zsetvaluezset可以用來(lái)存粉絲列表，valueID，score是關(guān)注時(shí)間。我們可以對(duì)粉絲列表按關(guān)注時(shí)間zset還可以用來(lái)存儲(chǔ)學(xué)生的成績(jī)，valueID，score是他的考試成績(jī)。我們zaddbooks9.0"thinkinjava"(integer)1zaddbooks8.9"javaconcurrency"(integer)1zaddbooks8.6"javacookbook"(integer)1zrangebooks01score"java"java"thinkinzrevrangebooks01score"thinkin"java"javazcardbookscount()(integer)3zscorebooks"javaconcurrency"value"8.9000000000000004scoredoublezrankbooks"javaconcurrency"(integer)1zrangebyscorebooks08.91"java"javazrangebyscorebooks-inf8.91withscores8.91]zset，同時(shí)返回分值。inf代表infinite，無(wú)窮大的意思。"java"javazrembooks"javaconcurrency"value(integer)1zrangebooks0-"java"thinkinzset內(nèi)部的排序功能是通過(guò)「跳躍列表」數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的，它的結(jié)構(gòu)非常特殊，也比zset要支持隨機(jī)的插入和刪除，所以它不好使用數(shù)組來(lái)表示。我們先看一個(gè)普通的score值進(jìn)行排序。這意味著當(dāng)有新元素需要插入時(shí)，要定位到——部門，每個(gè)部門會(huì)從組長(zhǎng)列表中推二級(jí)代表，再串起來(lái)。最終就形成了金字塔結(jié)構(gòu)。想想你老家在世界地圖中的位置：亞洲->中國(guó)->安徽省->安慶市->樅陽(yáng)縣->湯溝鎮(zhèn)->田間村->xxxx這個(gè)元素，同時(shí)處于L0、L1和L2層，可以快速在不同層次之間進(jìn)行「跳躍」。首先L0層肯定是100%了，L1層只有50%的概率，L2層只有25%的概率，L312.5%L31層。絕大多數(shù)元素都過(guò)不了幾層，只有極少現(xiàn)，請(qǐng)閱讀此書第36節(jié)《極度深寒——探索「跳躍列表」內(nèi)部結(jié)構(gòu)》list/set/hash/zset1、createifnot如果容器不存在，那就創(chuàng)建一個(gè)，再進(jìn)行操作。比如rpushRedis就會(huì)自動(dòng)創(chuàng)建一個(gè)，然后再rpush2、dropifnolpop操作到最后一Redis所有的數(shù)據(jù)結(jié)構(gòu)都可以設(shè)置過(guò)期時(shí)間，時(shí)間到了，Redis會(huì)自動(dòng)刪除相應(yīng)的對(duì)象。需要注意的是過(guò)期是以對(duì)象為單位，比如一個(gè)hash結(jié)構(gòu)的過(guò)期是整個(gè)hash對(duì)象的過(guò)期，而不是其中的某個(gè)子key。set:6379>setcodeholeyoyo:6379>expirecodehole(integer):6379>ttl(integer):6379>setcodeholeyoyo:6379>ttl(integer)-&作1、Java用戶，請(qǐng)定義一個(gè)用戶信息結(jié)構(gòu)體，然后使用fastjson象進(jìn)行序列化和反序列化，再使用jedis對(duì)Redis緩存的用戶信息進(jìn)行存和取2、Python用戶，使用內(nèi)置的JSON包就可以了。然后通過(guò)redis-py來(lái)Redis緩存的用戶信息進(jìn)行存和取3、想想如果要改成用hash結(jié)構(gòu)來(lái)緩存用戶信息，你該如何封裝比較合適4、想想平時(shí)還有哪些指令你平時(shí)用過(guò)而本小節(jié)沒有提到的？回想一下掘金社區(qū)的功能hash還是string應(yīng)用1：千帆競(jìng)發(fā)——分布式態(tài)這兩個(gè)操作不是原子的。（Wiki解釋：所謂原子操作是指不會(huì)被線程調(diào)度機(jī)制打斷的操作；這種操作一旦開始，就一直運(yùn)行到結(jié)束，中間不會(huì)有任何contextswitch線程切換。）這個(gè)時(shí)候就要使用到分布式鎖來(lái)限制程序的并發(fā)執(zhí)行。Redis分布式鎖使用非常廣泛，分布式分布式鎖本質(zhì)上要實(shí)現(xiàn)的目標(biāo)就是在Redis里面占一個(gè)“茅坑”，當(dāng)別的進(jìn)程也要來(lái)占setnx(setifnotexists)完了，再調(diào)用del指令釋放茅坑。setnxlock:codeholetrue...dosomethingcriticaldellock:codehole(integer)1于是我們?cè)谀玫芥i之后，再給鎖加上一個(gè)過(guò)期時(shí)間，比如5s，這樣即使中間出現(xiàn)異常也可以保證5秒之后鎖會(huì)自動(dòng)釋放。setnxlock:codeholetrue...dosomethingcriticaldellock:codehole(integer)1setnxexpire之間服務(wù)器進(jìn)程突然掛掉了，可能是因?yàn)闄C(jī)器掉電或者是被人為殺掉的，就會(huì)導(dǎo)致expire得不到執(zhí)行，也會(huì)造成死鎖。setnxexpire是兩條指令而不是原子指令。如果這兩條指令可Redisexpiresetnxsetnx沒搶到鎖，expireif-else分支邏輯，事務(wù)的特點(diǎn)是一口氣執(zhí)行，要么全部執(zhí)行要么一個(gè)都不執(zhí)行。為了解決這個(gè)疑難，Redislibrary，專門用來(lái)解決這個(gè)問意味著你不能僅僅使用Jedis或者redis-py就行了，還得引入分布式鎖的library。為了治理這個(gè)亂象，Redis2.8版本中作者加入了set指令的擴(kuò)展參數(shù)，使得setnx和expire指令可以一起執(zhí)行，徹底解決了分布式鎖的亂象。從此以后所有的第三方分布式鎖library可以休息了。>setlock:codeholetrueex5nxOK...dosomethingcritical...>dellock:codeholesetnxexpire組合在一起的原子指令，它就是分布式鎖的超Redis的分布式鎖不能解決超時(shí)問題，如果在加鎖和釋放鎖之間的邏輯執(zhí)行的太長(zhǎng)，以至為了避免這個(gè)問題，Redis分布式鎖不要用于較長(zhǎng)時(shí)間的任務(wù)。如果真的偶爾出現(xiàn)了，數(shù)tag ifredis.set(key,tag,nx=True,ex=5): delifequals有一個(gè)更加安全的方案是為set指令的value參數(shù)設(shè)置為一個(gè)隨機(jī)數(shù)，釋放鎖時(shí)先匹配keyvaluekey不是一個(gè)原子操作，Redis也沒有提供類似于delifequalsLuaLua腳本可#ifredis.call("get",KEYS[1])==ARGV[1]thenreturnredis.call("del",KEYS[1])

returnJavaReentrantLockRedis分setThreadlocal變量#-*-coding:utf-8importredisimportlocks=threading.local()locks.redis={}defreturndef_lock(client,def_unlock(client,key):deflock(client,key=key_for(user_id)ifkeyinlocks.redis:locks.redis[key]+=1returnTrueok=_lock(client,key)ifnotok:returnFalselocks.redis[key]=1returnTruedefunlock(client,user_id):key=key_for(user_id)ifkeyinlocks.redis:iflocks.redis[key]<=0:returnFalseclient=print"lock",lock(client,"codehole")print"lock",lock(client,print"unlock",unlock(client,"codehole")print"unlock",unlock(client,邏輯結(jié)構(gòu)上進(jìn)行調(diào)整完全可以不使用可重入鎖。下面是Java版本的可重入鎖。privateThreadLocal<Map>lockers=newThreadLocal<>();privateJedisjedis;publicRedisWithReentrantLock(Jedisjedis){this.jedis=jedis;returnjedis.set(key,"","nx","ex",5L)!=privatevoid_unlock(Stringkey){privateMap<String,Integer>currentLockers(){Map<String,Integer>refs=lockers.get();if(refs!=null){returnreturnlockers.get();publicbooleanlock(Stringkey){Maprefs=currentLockers();IntegerrefCnt=refs.get(key);if(refCnt!=null){returnbooleanok=this._lock(key);if(!ok){returnreturntrue;publicbooleanunlock(Stringkey){Maprefs=currentLockers();IntegerrefCnt=refs.get(key);if(refCnt==null){returnrefCnt-=if(refCnt>0)}elsethis._unlock(key);returnpublicstaticvoidmain(String[]args){Jedisjedis=newJedis();RedisWithReentrantLockredis=newRedisWithReentrantLock(jedis);跟Python版本區(qū)別不大，也是基于ThreadLocal思考1、Review下你自己的項(xiàng)目代碼中的分布式鎖，它的使用方式是否標(biāo)準(zhǔn)正確2、如果你還沒用過(guò)分布式鎖，想想自己的項(xiàng)目中是否可以用上應(yīng)用2：緩兵之計(jì)——延我們平時(shí)習(xí)慣于使用Rabbitmq和Kafka作為消息隊(duì)列中間件，來(lái)給應(yīng)用程序之間增加使用過(guò)Rabbitmq的同學(xué)知道它使用起來(lái)有多復(fù)雜，發(fā)消息之前要?jiǎng)?chuàng)建Exchange，再創(chuàng)QueueQueueExchangerouting-有了RedisRedis就可以非常輕松的搞定。Redis的消息隊(duì)列不是專業(yè)的消息隊(duì)列，它沒有非常多的高級(jí)特性，沒有ack保證，如果對(duì)消息的可靠性有著極致的追求，那么它就不適合使用。Redislist(列表)rpush/lpush操作入隊(duì)列，lpop和rpop來(lái)出隊(duì)列。rpushnotify-queueapplebananapear(integer)3llennotify-queue(integer)3lpopnotify-queuellennotify-queue(integer)2lpopnotify-queuellennotify-queue(integer)1lpopnotify-queuellennotify-queue(integer)0lpopnotify-queuerpushlpoplpushrpop結(jié)合使用，效果是一pop操作來(lái)獲取消息，然后進(jìn)行處理。處理完了再接著獲取消息，poppoppop，CPU，redisQPS也會(huì)被拉高，如果這樣空輪詢的客戶端有幾十來(lái)個(gè)，Redis的慢查詢可能會(huì)顯著增多。sleep1s鐘就可以了。不但客戶端的CPU能降下來(lái)，Redis的QPS也降下來(lái)了。 python java睡如果只有1個(gè)消費(fèi)者，那么這個(gè)延遲就是1s。如果有多個(gè)消費(fèi)者，這個(gè)延遲會(huì)有所下降，因種方式當(dāng)然可以，不過(guò)有沒有更好的解決方案呢？當(dāng)然也有，那就是blpop/brpop。bblocking息的延遲幾乎為零。用blpop/brpoplpop/rpop，就完美解決了上面的問題。...什么問題？——空閑連接的問題。如果線程一直阻塞在哪里，Redis的客戶端連接就成了閑置連接，閑置過(guò)久，服務(wù)器一般會(huì)主動(dòng)斷開連接，減少閑置資源占用。這個(gè)時(shí)候blpop/brpop會(huì)拋出異常來(lái)。所以編寫客戶端消費(fèi)者的時(shí)候要小心，注意捕獲異常，還要重試。一般有3種策略來(lái)處理加鎖失敗：2、sleep一會(huì)再重試；3、將請(qǐng)求轉(zhuǎn)移至延時(shí)隊(duì)列，過(guò)一會(huì)再試sleep會(huì)阻塞當(dāng)前的消息處理線程，會(huì)導(dǎo)致隊(duì)列的后續(xù)消息處理出現(xiàn)延遲。如果碰撞的比較頻繁或者隊(duì)列里消息比較多，sleepkey導(dǎo)致加鎖不成Rediszset(有序列表)來(lái)實(shí)現(xiàn)。我們將消息序列化成一個(gè)字符串作為zset的value，這個(gè)消息的到期處理時(shí)間作為score，然后用多個(gè)線程輪詢zset獲取到期defmsg.id valuevalue=retry_tstime.time 5redis.zadd("delay-queue",retry_ts,value)defloop():while#最多取1values=redis.zrangebyscore("delay-queue",0,time.time(),start=0,num=1)ifnotvalues: value =", if msg=json.loads(value)Rediszrem方法是多線程多進(jìn)程爭(zhēng)搶任務(wù)的關(guān)鍵，它的返回值決定了當(dāng)前實(shí)例有沒有搶到任務(wù)，因?yàn)閘oop方法可能會(huì)被多個(gè)線程、多個(gè)進(jìn)程調(diào)用，同一個(gè)任務(wù)可能會(huì)被多個(gè)進(jìn)程線程搶到，通過(guò)zremhandle_msg進(jìn)行異常捕獲，避免因?yàn)閭€(gè)別任務(wù)處理問題導(dǎo)致循環(huán)異常退出。以下是Java版本的延時(shí)隊(duì)列實(shí)現(xiàn)，因?yàn)橐褂玫絁sonfastjson庫(kù)的支持。importjava.util.Set;importimportimportredis.clients.jedis.Jedis;publicclassRedisDelayingQueue<T>{staticclassTaskItem<T>{publicStringid;publicTmsg;fastjsongenericprivateJedisjedis;privateStringpublicRedisDelayingQueue(Jedisjedis,StringqueueKey){this.jedis=jedis;this.queueKey=publicvoiddelay(Tmsg)TaskItemtask=newtask.id task.msg=Strings fastjson,)+, ,5spublicvoidloop()Setvalues=jedis.zrangeByScore(queueKey,0,System.currentTimeMillis(),0,1);if(values.isEmpty()){try catch(InterruptedExceptione){Strings=ifjedis.zrem(queueKeys0 TaskItemtaskJSON.parseObject(sTaskType);fastjsonpublicvoidhandleMsg(Tmsg){publicstaticvoidmain(String[]args){Jedisjedis=newJedis();RedisDelayingQueuequeue=newRedisDelayingQueue<>(jedis,"q-demo");Threadproducer=newThread(){publicvoidrun()for(inti=0;i<10;i++)Threadconsumer=newThread(){publicvoidrun(){try{zrem進(jìn)行爭(zhēng)搶，那些沒搶到luascripting來(lái)優(yōu)化一下這個(gè)邏輯，將zrangebyscorezrem一同挪到服務(wù)器端進(jìn)行原子化操作，這樣多個(gè)進(jìn)程之間爭(zhēng)搶任務(wù)時(shí)就不1、Redis作為消息隊(duì)列為什么不能保證100%的可靠性？2、使用LuaScripting來(lái)優(yōu)化延時(shí)隊(duì)列的邏輯。應(yīng)用3：節(jié)衣縮食——位bool型數(shù)據(jù)需要存取，比如用戶一年的簽到記錄，簽了是1，沒簽是0，要記錄365天。如果使用普通的key/value，每個(gè)用戶要記錄365為了解決這個(gè)問題，Redis提供了位圖數(shù)據(jù)結(jié)構(gòu)，這樣每天的簽到記錄只占據(jù)一個(gè)位，365365個(gè)位，46(一個(gè)稍長(zhǎng)一點(diǎn)的字符串)就可以完全容納下，這就大大byte數(shù)組。我們get/setgetbit/setbit等將byte數(shù)組看成「位數(shù)組」來(lái)處理。RedisRedis的位圖有Redis的位數(shù)組是自動(dòng)擴(kuò)展，如果設(shè)置了某個(gè)偏移位置超出了現(xiàn)有的內(nèi)容范圍，就會(huì)自hello(set指令)，首先我們需要得到hello的ASCII碼，用Python命令行可以很方便地得到每個(gè)字符的ASCII碼的二進(jìn)制>>> >>>bin(ord('e'))>>>bin(ord('l'))>>>bin(ord('l'))>>>bin(ord('o'))redis-cli8位，我們只需要設(shè)置1的位，如上圖所示，h1/2/4位需要設(shè)置，e9/10/13/15位需要:6379>setbits1:6379>setbits2:6379>setbits4:6379>setbits9:6379>setbits10:6379>setbits13:6379>setbits15:6379>getsetbit對(duì)位值進(jìn)行逐個(gè)設(shè)置，「整存」就是使用字符串一次性填充:6379>setbitw1(integer):6379>setbitw2(integer):6379>setbitw4(integer):6379getbitw (integer):6379>getbitw(integer):6379>getbitw(integer):6379>getbitw(integer):6379setw (integer):6379>getbitw(integer):6379>getbitw(integer):6379>getbitw(integer):6379>getbitw(integer)如果對(duì)應(yīng)位的字節(jié)是不可打印字符，redis-cli16:6379>setbitx0(integer):6379>setbitx1(integer):6379>getRedisbitcountbitpos，bitcount用來(lái)統(tǒng)計(jì)指定位置范圍內(nèi)1的個(gè)數(shù)，bitpos用來(lái)查找指定范圍內(nèi)出現(xiàn)的第一個(gè)0或1。比如我們可以通過(guò)bitcount統(tǒng)計(jì)用戶一共簽到了多少天，通過(guò)bitpos指令查找用戶從哪一天開始第一次簽到。如果指定了范圍參數(shù)[startend]，就可以統(tǒng)計(jì)在某個(gè)時(shí)間范圍內(nèi)用戶遺憾的是，start和end參數(shù)是字節(jié)索引，也就是說(shuō)指定的位范圍必須是8的倍數(shù)，Antirez為什么要這樣設(shè)計(jì)。因?yàn)檫@個(gè)設(shè)部取出來(lái)(getrange可以取出字符串的子串)然后在內(nèi)存里進(jìn)行統(tǒng)計(jì)，這個(gè)非常繁瑣。bitcountbitpos指令:6379>setwhello:6379>bitcount(integer):6379bitcountw0 1(integer):6379bitcountw0 1(integer):6379bitposw #第一個(gè)0(integer):6379bitposw #第一個(gè)1(integer):6379bitposw11 1(integer):6379bitposw12 1(integer)魔術(shù)指令前文我們?cè)O(shè)置(setbit)和獲取(getbit)指定位的值都是單個(gè)位的，如果要一次操作多個(gè)位，就必須使用管道來(lái)處理。不過(guò)Redis的3.2版本以后新增了一個(gè)功能強(qiáng)大的指令，有了這條指令，不用管道也可以一次進(jìn)行多個(gè)位的操作。bitfield有三個(gè)子指令，分別是get/set/incrby64個(gè)連續(xù)的位，如果超過(guò)64位，就得使用多個(gè)子指令，bitfield可以一次執(zhí)行多個(gè)子指令。接下來(lái)我們對(duì)照著上面的圖看個(gè)簡(jiǎn)單的例子:6379>setwhello:6379bitfieldwgetu4 4(integer):6379bitfieldwgetu3 3(integer):6379bitfieldwgeti4 41)(integer):6379bitfieldwgeti3 31)(integer)-多可以獲取64位，無(wú)符號(hào)數(shù)只能獲取63位(因?yàn)镽edis協(xié)議中的integer是有符號(hào)數(shù)，最大64位，不能傳遞64位無(wú)符號(hào)值)。如果超出位數(shù)限制，Redis就會(huì)告訴你參數(shù)錯(cuò)誤。接下來(lái)我們一次執(zhí)行多個(gè)子指令:6379>bitfieldwgetu40getu32geti40geti3(integer)(integer)(integer)(integer)-wowset子指令將第二個(gè)字符e改成a，aASCII碼是97:6379bitfieldwsetu88 88971)(integer):6379>get再看第三個(gè)子指令incrby，它用來(lái)對(duì)指定范圍的位進(jìn)行自增操作。既然提到自增，就有8255，加1后就會(huì)溢出，會(huì)全部變零。如果是8位有符號(hào)數(shù)127，加1后就會(huì)溢出變成-128。接下來(lái)我們實(shí)踐一下這個(gè)子指令incrby:6379>setwhello:6379bitfieldwincrbyu42 41)(integer):6379>bitfieldwincrbyu421)(integer):6379>bitfieldwincrbyu421)(integer):6379>bitfieldwincrbyu421)(integer):6379>bitfieldwincrbyu421)(integer):6379bitfieldwincrbyu42 1)(integer)bitfield指令提供了溢出策略子指令overflow，用戶可以選擇溢出行為，默認(rèn)是折返(wrap)，還可以選擇失敗(fail)報(bào)錯(cuò)不執(zhí)行，以及飽和截?cái)?sat)，超過(guò)了范圍就停留在最大最小值。overflow指令只影響接下來(lái)的第一條指令，這條指令執(zhí)行完后溢出策略會(huì)變成默認(rèn)值折返(wrap)。飽和截?cái)郤AT:6379>setw:6379>bitfieldwoverflowsatincrbyu421)(integer):6379>bitfieldwoverflowsatincrbyu421)(integer):6379>bitfieldwoverflowsatincrbyu421)(integer):6379>bitfieldwoverflowsatincrbyu421)(intege):6379>bitfieldwoverflowsatincrbyu421)(integer):6379bitfieldwoverflowsatincrbyu42 1)(integer):6379>setwhello:6379>bitfieldwoverflowfailincrbyu421)(integer):6379>bitfieldwoverflowfailincrbyu421)(integer):6379>bitfieldwoverflowfailincrbyu421)(integer):6379>bitfieldwoverflowfailincrbyu42(integer):6379>bitfieldwoverflowfailincrbyu42(integer):6379bitfieldwoverflowfailincrbyu42 &作1、文中我們使用位操作設(shè)置了he兩個(gè)字符，請(qǐng)讀者將完整的hello單詞中5個(gè)字符2、bitfield可以同時(shí)混合執(zhí)行多個(gè)set/get/incrby子指令，請(qǐng)讀者嘗試完成應(yīng)用4：四兩撥千斤UV數(shù)據(jù)，然后讓你來(lái)開發(fā)這個(gè)統(tǒng)計(jì)模PVRedis計(jì)數(shù)器就可以了，這個(gè)計(jì)數(shù)器的key后綴加上當(dāng)天的日期。這樣來(lái)一個(gè)請(qǐng)求，incrby一次，最終就可以統(tǒng)計(jì)出所有的PVUV不一樣，它要去重，同一個(gè)用戶一天之內(nèi)的多次訪問請(qǐng)求只能計(jì)數(shù)一次。這就ID，無(wú)論是登陸用戶還是未登陸用戶都需要一個(gè)唯一ID來(lái)標(biāo)識(shí)。你也許已經(jīng)想到了一個(gè)簡(jiǎn)單的方案，那就是為每一個(gè)頁(yè)面一個(gè)獨(dú)立的set集合來(lái)存儲(chǔ)所IDsaddID塞進(jìn)去就可scardUV數(shù)據(jù)。沒錯(cuò)，這但是，如果你的頁(yè)面訪問量非常大，比如一個(gè)爆款頁(yè)面幾千萬(wàn)的UV，你需要一個(gè)很大set集合來(lái)統(tǒng)計(jì)，這就非常浪費(fèi)空間。如果這樣的頁(yè)面很多，那所需要的存儲(chǔ)空間是驚人太精確，105w106w這兩個(gè)數(shù)字對(duì)于老板們來(lái)說(shuō)并沒有多大區(qū)別，So，有沒有更好的解這就是本節(jié)要引入的一個(gè)解決方案，RedisHyperLogLog數(shù)據(jù)結(jié)構(gòu)就是用來(lái)解決這種統(tǒng)計(jì)問題的。HyperLogLog提供不精確的去重計(jì)數(shù)方案，雖然不精確但是也不是非常不精確，標(biāo)準(zhǔn)誤差是0.81%，這樣的精確度已經(jīng)可以滿足上面的UV統(tǒng)計(jì)需求了。HyperLogLogRedis的高級(jí)數(shù)據(jù)結(jié)構(gòu)，它非常有用，但是令人感到意外的HyperLogLog提供了兩個(gè)指令pfadd和pfcount，根據(jù)字面意義很好理解，一個(gè)是增加計(jì)數(shù)，一個(gè)是獲取計(jì)數(shù)。pfaddsetsaddID，就將用戶ID塞進(jìn)去就是。pfcount和scard用法是一樣的，直接獲取計(jì)數(shù)值。:6379>pfaddcodeholeuser1(integer)1:6379>pfcount(integer):6379>pfaddcodeholeuser2(integer)1:6379>pfcount(integer):6379>pfaddcodeholeuser3(integer)1:6379>pfcount(integer):6379>pfaddcodeholeuser4(integer)1:6379>pfcount(integer):6379>pfaddcodeholeuser5(integer)1:6379>pfcount(integer):6379>pfaddcodeholeuser6(integer)1:6379>pfcount(integer):6379>pfaddcodeholeuser7user8user9user10(integer)1:6379>pfcount(integer)Python！Python#coding:utf-8importredisclient=redis.StrictRedis()foriinrange(1000):client.pfadd("codehole","user%d"%i)total=client.pfcount("codehole")iftotal!=printtotal,i+1Java也不錯(cuò)，大同小異，下面是JavapublicclassPfTestpublicstaticvoidmain(String[]args){Jedisjedis=newJedis();for(inti=0;i<1000;i++){jedis.pfadd("codehole","user"+i);longtotal=jedis.pfcount("codehole");if(total!=i+1){System.out.printf("%d%d\n",total,i+1);pythonpftest.py99100當(dāng)我們加入第100個(gè)元素時(shí)，結(jié)果開始出現(xiàn)了不一致。接下來(lái)我們將數(shù)據(jù)增加到#coding:utf-8importredisclient=redis.StrictRedis()foriinrange(100000):client.pfadd("codehole","user%d"%i)print100000,client.pfcount("codehole")JavapublicclassJedisTestpublicstaticvoidmain(String[]args){Jedisjedis=newJedis();for(inti=0;i<100000;i++){jedis.pfadd("codehole","user"+i);longtotal=jedis.pfcount("codehole");System.out.printf("%d%d\n",100000,total);pythonpftest.py100000997232770.277%UV統(tǒng)計(jì)需求來(lái)說(shuō)，誤差率也不算高。pfcount的結(jié)果沒有任何改變，還是99723，說(shuō)明它確實(shí)具備去重功能。pfadd這個(gè)pf是什么意思HyperLogLogPhilippeFlajolet的首字母縮寫，老師覺得他pfmerge適合什么場(chǎng)合用HyperLogLogpfaddpfcountpfmerge，用于將多個(gè)pf計(jì)數(shù)值累加在一起形成一個(gè)新的pf值。其中頁(yè)面的UV訪問量也需要合并，那這個(gè)時(shí)候pfmerge就可以派上用場(chǎng)了。注意事HyperLogLog這個(gè)數(shù)據(jù)結(jié)構(gòu)不是免費(fèi)的，不是說(shuō)使用這個(gè)數(shù)據(jù)結(jié)構(gòu)要花錢，它需要占據(jù)12k的存儲(chǔ)空間，所以它不適合統(tǒng)計(jì)單個(gè)用戶相關(guān)的數(shù)據(jù)。如果你的用戶上億，可以算算，這個(gè)空間成本是非常驚人的。但是相比set存儲(chǔ)方案，HyperLogLog所使用的空間那真RedisHyperLogLog的存儲(chǔ)進(jìn)行了優(yōu)化，在計(jì)數(shù)比較用空間漸漸超過(guò)了閾值時(shí)才會(huì)一次性轉(zhuǎn)變成稠密矩陣，才會(huì)占用12k的空間。HyperLogLogHyperLogLog的使用非常簡(jiǎn)單，但是實(shí)現(xiàn)原理比較復(fù)雜，如果讀者沒有特別的興趣，下HyperLogLogk，通k一下隨機(jī)整數(shù)的數(shù)量和k值的關(guān)系。importmathimportrandomdefforiinxrange(1,ifvalue>>i<<i!=value:returni-classdefinit(self):self.maxbits=0defvalue=random.randint(0,2**32-1)bits=low_zeros(value)ifbits>self.maxbits:self.maxbits=bitsclassExperiment(object):definit(self,self.n=self.keeper=defforiinrange(self.n):defprintself.n,'%.2f'%math.log(self.n,2),foriinrange(1000,100000,100):exp=Experiment(i)JavapublicclassPfTest{staticclassBitKeeper{privateintmaxbits;publicvoidrandom(){longvalue=ThreadLocalRandom.current().nextLong(2L<<32);intbits=lowZeros(value);if(bits>this.maxbits){this.maxbits=bits;privateintlowZeros(longvalue){inti=1;for(;i<32;i++)if(value>>i<<i!=value){returni-staticclassExperiment{privateintn;privateBitKeeperkeeper;publicExperiment(intn){this.n=this.keeper=newpublicvoidwork()for(inti=0;i<n;i++){publicvoiddebug()System.out.printf("%d%.2f%d\n",this.n,Math.log(this.n)/Math.log(2),publicstaticvoidmain(String[]args)for(inti=1000;i<100000;i+=100)Experimentexp=newExperiment(i);3640015.153650015.163660015.163670015.163680015.173690015.173700015.183710015.183720015.183730015.193740015.193750015.193760015.20K和N N2^K2^(K+1)2^K，這明顯是不合理的。這里可以采用多個(gè)BitKeeper，然后進(jìn)行加權(quán)估計(jì)，就可以得到一個(gè)比較準(zhǔn)確的值。importmathimportrandomdefforiinxrange(1,ifvalue>>i<<i!=value:returni-classBitKeeper(object):definit(self):self.maxbits=defrandom(self,bits=low_zeros(m)ifbits>self.maxbits:self.maxbits=classdefinit(self,n,k=1024):self.n=nself.k=self.keepers=[BitKeeper()foriindefforiinm=random.randint(0,1<<32-#確保同一個(gè)整數(shù)被分配到同一個(gè)桶里面，摘取高位后取模keeperself.keepers[((m&0xfff0000)16)len(self.keepers)]defsumbits_inverse forkeeperinsumbits_inverse+=1.0/float(keeper.maxbits)avgbitsfloat(self.k)/sumbits_inversereturn2**avgbits*self.kforiinrange(100000,1000000,100000):exp=Experiment(i)est=printi,'%.2f'%est,'%.2f'%(abs(est-i)/JavapublicclassPfTest{staticclassBitKeeper{privateintpublicvoidrandom(longvalue){intbits=lowZeros(value);if(bits>this.maxbits){this.maxbits=bits;privateintlowZeros(longvalue){inti=1;for(;i<32;i++)if(value>>i<<i!=value){returni-staticclassExperiment{privateintn;privateintprivateBitKeeper[]keepers;publicExperiment(intn){publicExperiment(intn,intk){this.n=n;this.k=this.keepers=newBitKeeper[k];for(inti=0;i<k;i++){this.keepers[i]=newpublicvoidwork()for(inti=0;i<this.n;i++)longm=ThreadLocalRandom.current().nextLong(1L<<BitKeeperkeeper=keepers[(int)(((m&0xfff0000)>>16)%keepers.length)];publicdoubleestimate(){doublesumbitsInverse=0.0;for(BitKeeperkeeper:keepers){sumbitsInverse+=1.0/(float)keeper.maxbits;doubleavgBits=(float)keepers.length/sumbitsInverse;returnMath.pow(2,avgBits)*this.k;publicstaticvoidmain(String[]args)for(inti=100000;i<1000000;i+=100000)Experimentexp=newExperiment(i);doubleest=System.out.printf("%d%.2f%.2f\n",i,est,Math.abs(est-i)/1024(倒數(shù)的平均)。普通的平均法可能10000097287.38200000189369.02300000287770.04400000401233.52500000491704.97600000604233.92700000721127.67800000832308.12900000870954.8610000001075497.64HyperLogLog要比上面的示例代碼更加復(fù)雜一些，也更加精確一些。上面的這個(gè)算法在隨機(jī)次數(shù)很少的情況下會(huì)出現(xiàn)除零錯(cuò)誤，因?yàn)閙axbits=0是不可以求倒數(shù)的。pf的內(nèi)存占用為什么是我們?cè)谏厦娴乃惴ㄖ惺褂昧?024個(gè)桶進(jìn)行獨(dú)立計(jì)數(shù)，不過(guò)在Redis的HyperLogLog163842^14，每個(gè)桶的maxbits6bits來(lái)存儲(chǔ)，最大可以表示maxbits=632^14*6/8=12k字節(jié)。&作pfmerge合并到一起，觀察HyperLogLog復(fù)雜的公式推導(dǎo)請(qǐng)閱讀Count-DistinctProblem，如果你的概率好，那就建議不要看了（另，這個(gè)PPT需要翻墻觀看）應(yīng)用5：層巒疊嶂——布隆HyperLogLog數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行估數(shù)，它非常有價(jià)值，可以解決HyperLogLog結(jié)構(gòu)里面了，它就無(wú)能為力了，它只提供了pfadd和pfcount方法，沒有提供pfcontains這種方法。exists查(BloomFilter)閃亮登場(chǎng)了，它就是專門用來(lái)解決這種去重問題的。90%以上，只是稍微有那么點(diǎn)不精確，也就是有setcontains方法判斷某(某些熟臉的系數(shù)組合)，所以誤判以前見過(guò)(誤判)，但是絕大多數(shù)新內(nèi)容它都能準(zhǔn)確識(shí)別。這樣就Redis中的布隆RedisRedis4.0提供了插件功能之后才正式登場(chǎng)。布隆過(guò)濾器作為一個(gè)插件加載到RedisServer中，給Redis提供了強(qiáng)大的布隆去重功能。Redis4.0Dockerdockerpull dockerrunp6379:6379 redis布隆過(guò)濾器有二個(gè)基本指令，bf.add添加元素，bf.exists查詢?cè)厥欠翊嬖?，它的用法和set集合的sadd和sismember差不多。注意bf.add只能一次添加一個(gè)元素，如果想要bf.madd指令。同樣如果需要一次查詢多個(gè)元素是否存在，就需要用到bf.mexists指令。:6379>bf.addcodeholeuser1(integer)1:6379>bf.addcodeholeuser2(integer)1:6379>bf.addcodeholeuser3(integer)1:6379>bf.existscodeholeuser1(integer)1:6379>bf.existscodeholeuser2(integer)1:6379>bf.existscodeholeuser3(integer)1:6379>bf.existscodehole(integer):6379>bf.maddcodeholeuser4user5(integer)(integer)(integer):6379>bf.mexistscodeholeuser4user5user6(integer)(integer)(integer)(integer)Python腳本加入很多元素，看看加到第幾#coding:utf-importclient=redis.StrictRedis()foriinrange(100000):client.execute_command("bf.add","codehole","user%d"%ret=client.execute_command("bf.exists","codehole","user%d"%i)ifret==0:printiJava客戶端Jedis-2.x沒有提供指令擴(kuò)展機(jī)制，所以你無(wú)法直接使用Jedis來(lái)訪問RedisModulebf.xxx指令。RedisLabsJReBloom，但是它是基Jedis-3.0，Jedis-3.0release，沒有進(jìn)入maven的中央倉(cāng)庫(kù)，需要在Github上下載。在使用上很不方便，如果怕麻煩，還可以使用lettuce，它是另一個(gè)Redis的客戶端，相比Jedis而言，它很早就支持了指令擴(kuò)展。publicclassBloomTestpublicstaticvoidmain(String[]args){Clientclient=newClient();for(inti=0;i<100000;i++){client.add("codehole","user"+i);booleanret=client.exists("codehole","user"+i);if(!ret){執(zhí)行上面的代碼后，你會(huì)張大了嘴巴發(fā)現(xiàn)居然沒有輸出，塞進(jìn)去了1000000試試，你會(huì)發(fā)現(xiàn)依bf.exists去查找沒見過(guò)的元素，看看它是不是#coding:utf-8importredisclient=redis.StrictRedis()foriinrange(100000):client.execute_command("bf.add","codehole","user%d"%i+1，ret=client.execute_command("bf.exists","codehole","user%d"%(i+1))ifret==1:printiJava版publicclassBloomTestpublicstaticvoidmain(String[]args){Clientclient=newClient();for(inti=0;i<100000;i++){client.add("codehole","user"+i);booleanret=client.exists("codehole","user"+(i+1));if(ret){運(yùn)行后，我們看到了輸出是214，也就是到第2142組，將其中一組塞入#coding:utf-importredisimportrandomclient=CHARS=''.join([chr(ord('a')+i)foriinrange(26)])defrandom_string(n):chars=foriinidx=random.randint(0,len(CHARS)-1)returnusers=list(set([random_string(64)foriinrange(100000)]))print'totalusers',len(users)users_train=users[:len(users)/2]users_test=users[len(users)/2:]falses=0foruserinuser