歡迎來到「我是真的狗雜談世界」，關(guān)注不迷路
背景
最近需要將遇到的幾個(gè)排行需求點(diǎn)抽出來做一個(gè)獨(dú)立的通用排行組件，整理記錄一下古涧。
核心需求
- 能獲得連續(xù)的部分的榜單：比如前100名矮烹、第300～400名的用戶以及分值
- 能獲得任意單用戶信息：比如用戶A的分值與當(dāng)前排名
- 能操作榜單單用戶分值：比如為用戶A增加3分
- 上述功能要求實(shí)時(shí)
- 分值相同時(shí)图焰，要求按照達(dá)到分值時(shí)間的先后排序盐碱，先達(dá)到分值的用戶排在前面
- 分值是整數(shù)（或類似金額這種有限位小數(shù)榛了，也可以看為整數(shù)）矿咕，業(yè)務(wù)上一般高精度小數(shù)無場(chǎng)景意義
思考過程
說白了就是排序問題抢肛，相關(guān)的算法和結(jié)構(gòu)有很多了，可問題是總不能自己從零開始實(shí)現(xiàn)吧（也不是不可以）～～
那么在現(xiàn)有的存儲(chǔ)介質(zhì)上很容易想到Redis的ZSet數(shù)據(jù)類型(MySQL不是今天的主題碳柱，假裝想不到咳咳)
Redis ZSet
底層結(jié)構(gòu)與操作過程
ZSet數(shù)據(jù)類型的主要數(shù)據(jù)結(jié)構(gòu)是跳表捡絮，具有多層級(jí)結(jié)構(gòu)（因此對(duì)內(nèi)存要求稍稍高一點(diǎn)），具體的結(jié)構(gòu)和操作過程在「Tool 1.Redis搗騰系列」中繼續(xù)搗騰莲镣。
相關(guān)功能情況
現(xiàn)在只關(guān)注上述需求用到的幾個(gè)操作是否支持以及性能開銷情況：
- ZADD/ZINCRBY: O(log(N))
- ZSCORE: O(1)
- ZCARD: O(1)
- ZRANGE/ZREVRANGE: O(log(N)+M)福稳；
N為有序集的基數(shù)，而M為結(jié)果集的基數(shù) - ZRANK/ZREVRANK: O(log(N))
O(log(N))的時(shí)間復(fù)雜度理論上完全可以扛住上億數(shù)據(jù)的并發(fā)查詢（當(dāng)然并不建議真的在生產(chǎn)環(huán)境這么干）瑞侮。
O(log(N)+M)需要特別注意的圆，M是線性增長(zhǎng)的，需要嚴(yán)格控制上限
一些特點(diǎn)
ZSet在使用上是member->score結(jié)構(gòu)：
- member: 被排序的標(biāo)識(shí)半火，也是默認(rèn)的第二排序維度（score相同時(shí)越妈，redis以member的字典序排列）
- score: 被排序的分值，存儲(chǔ)類型是double
雙維度問題
如果直接按照上述用法進(jìn)行使用钮糖，那么只有第一排序維度score是我需要的梅掠，雖然有第二排序維度member，而需要的第二排序維度是時(shí)間。那怎么辦呢瓤檐？
思考技巧
我常常用來解決問題的思考技巧有：
- 加：加入其他模塊赂韵、組件來滿足需求
- 借：借助現(xiàn)有的但不滿足需求的模塊、組件利用轉(zhuǎn)換來滿足需求
- 合：將幾個(gè)模塊挠蛉、組件合并起來實(shí)現(xiàn)一個(gè)需求祭示，跟拆可以互相轉(zhuǎn)換只是視角層次不同
- 拆：將一個(gè)模塊、組件拆分為多個(gè)谴古，以滿足需求质涛，跟合可以互相轉(zhuǎn)換只是視角層次不同
實(shí)現(xiàn)思路
思路1：加結(jié)構(gòu)
粗暴一點(diǎn)：一個(gè)ZSet只有一個(gè)score滿足需求，那就同時(shí)維護(hù)兩個(gè)ZSet掰担，一個(gè)存分值一個(gè)存時(shí)間
- 優(yōu)點(diǎn)：從方案上說實(shí)現(xiàn)比較簡(jiǎn)單
- 缺點(diǎn)：具體實(shí)現(xiàn)上需要同時(shí)維護(hù)兩個(gè)ZSet汇陆，需要的空間略大；且對(duì)并發(fā)控制粒度要求大（讀寫鎖+鎖范圍是操作兩個(gè)ZSet期間）
思路2：借member
前面提到member是默認(rèn)的第二排序維度带饱，但直接使用是無法滿足時(shí)間排序的需求的毡代，那如果member的內(nèi)容中涵蓋了時(shí)間呢？
比如原始數(shù)據(jù)是這樣：
user=user1勺疼；score=100教寂；time=2022-12-15 13:30:30 user=user2；score=100执庐；time=2022-12-15 13:30:35
而存儲(chǔ)時(shí)將time+user作為member：
member=2022-12-15 13:30:30_user1酪耕；score=100 member=2022-12-15 13:30:35_user2；score=100這樣就借助了member來實(shí)現(xiàn)了時(shí)間維度的排序轨淌。
- 優(yōu)點(diǎn): 從方案上說實(shí)現(xiàn)也比較簡(jiǎn)單
- 缺點(diǎn)：在維護(hù)上仍舊需要另一個(gè)結(jié)構(gòu)來輔助映射用戶當(dāng)前時(shí)間（比如hash）迂烁，否則獲取用戶排行信息的時(shí)候無法確定member的值；同時(shí)每次修改用戶分值時(shí)必須控制并發(fā)和原子操作刪除原member和添加新member
思路3：拆/合score
前面還提到score的存儲(chǔ)類型是double递鹉，也就是說有很多位（不管二進(jìn)制位也好盟步、十進(jìn)制位也好），而數(shù)字的比較是高位相等時(shí)以低位來決定結(jié)果梳虽，這不是跟多維度排序的需求一樣嗎址芯？那如果我把這么多位拆成兩部分分別代表分值和時(shí)間，存儲(chǔ)時(shí)計(jì)算合并呢窜觉？
比如（以十進(jìn)制位舉例）原始數(shù)據(jù)是這樣：
user=user1谷炸；score=100；time=3092 user=user2禀挫；score=100旬陡；time=3093
而存儲(chǔ)時(shí)將score+time作為score（當(dāng)然這樣時(shí)間維度是順序反了，用一個(gè)大數(shù)去減就可以把順序帶回來）：
member=user1语婴；score=1003092 member=user2描孟；score=1003093這樣就將一個(gè)score拆成了多個(gè)存儲(chǔ)（或者說將多個(gè)存儲(chǔ)合存在一個(gè)score中）了驶睦。
- 優(yōu)點(diǎn)：無需維護(hù)額外的結(jié)構(gòu)，空間開銷少匿醒；且只需要控制寫鎖场航，不會(huì)干擾讀并發(fā)
- 缺點(diǎn)：score的計(jì)算相對(duì)復(fù)雜一點(diǎn)，且縮小了分值和時(shí)間的取值范圍廉羔；另外score的可讀性不那么好（取值范圍和可讀性在實(shí)踐中進(jìn)行了優(yōu)化）
實(shí)踐過程
細(xì)化方案
方案1：以十進(jìn)制對(duì)整數(shù)位進(jìn)行劃分
- Redis ZSet的score值在超過254后存儲(chǔ)和計(jì)算會(huì)出現(xiàn)問題溉痢，保險(xiǎn)起見，采用253最為最大整數(shù)：900719 9254740992
- 秒級(jí)時(shí)間戳需要10位憋他，因此低10位由秒級(jí)時(shí)間戳填充
- 高6位則可以由分值填充孩饼，但分值最大為900718
- 優(yōu)點(diǎn)：可讀性較高
- 缺點(diǎn)：分值范圍小
方案2：以二進(jìn)制對(duì)整數(shù)位進(jìn)行劃分
- 仍舊是2^53作為最大整數(shù)
- 采用低32作為時(shí)間戳（可表示到2106-02-07 14:28:16）
- 剩余高21位作為分值（可表示到2097152）
- 優(yōu)點(diǎn)：分值范圍較方案1變大了一些（如果壓縮時(shí)間戳位數(shù)，還可以再變大一倍）
- 缺點(diǎn)：可讀性更差了（想象一下兩個(gè)數(shù)轉(zhuǎn)換成二進(jìn)制后再組合成一個(gè)新的數(shù)）
方案3：利用double的浮點(diǎn)計(jì)算
- double的有效位可以保證在15位以上
- 將分值作為score的整數(shù)部分
- 將時(shí)間戳逆向后作為score的小數(shù)部分
- 優(yōu)點(diǎn)：可讀性較高竹挡；利用浮點(diǎn)數(shù)特點(diǎn)镀娶，分值取值范圍可以很大（起碼2^53沒有問題了）
- 缺點(diǎn)：也是因?yàn)楦↑c(diǎn)數(shù)特點(diǎn)，隨著分值（整數(shù)部分）的逐漸增大揪罕，時(shí)間戳（小數(shù)部分）精度逐漸變小
選擇
最后我選擇了方案3梯码，因?yàn)榭紤]到有分值大小和時(shí)間精度高低兩個(gè)維度的指標(biāo)，方案3在不同場(chǎng)景下的匹配度如下：
| 分值小 | 分值大 | |
|---|---|---|
| 時(shí)間精度高 | 匹配度高 | 匹配度低 |
| 時(shí)間精度低 | 匹配度高 | 匹配度高 |
根據(jù)上表好啰，業(yè)務(wù)業(yè)務(wù)需要：
- 對(duì)于分值上限腥绦（百萬級(jí)別以下）的業(yè)務(wù)場(chǎng)景，方案3可以保障時(shí)間高精度
- 對(duì)于分值上限高（千萬級(jí)別以上）的業(yè)務(wù)場(chǎng)景坎怪，分值往往是從小累計(jì)到大的且在小分值時(shí)競(jìng)爭(zhēng)激烈（容易出現(xiàn)同分多，達(dá)到同分的時(shí)間間隔小的情況）大分值時(shí)則不激烈廓握，采用方案3可以在分值較小時(shí)仍舊保障時(shí)間高精度搅窿，分值大時(shí)一般對(duì)時(shí)間精度要求也低了
- 另外還可以根據(jù)業(yè)務(wù)來收縮時(shí)間戳（小數(shù)部分）的范圍來擴(kuò)大秒級(jí)時(shí)間精度下的分值（整數(shù)部分）范圍
DEMO
// lock acquire
// 計(jì)算分值部分
$nowScore = $redis->zScore($key, $member);
$setScore = $addScore + intval($nowScore);
// 計(jì)算時(shí)間戳部分（可做到百萬級(jí)別分值仍舊保持秒級(jí)時(shí)間戳精度，還可以繼續(xù)優(yōu)化這塊提升分值上限）
$maxTime = 4102415999; // 2099-12-31 23:59:59
$nowTime = $maxTime - time();
$timeScore = bcdiv($nowTime, $maxTime, 10);
$finalScore = bcadd($setScore, $timeScore, 10);
// 設(shè)置
$redis->zAdd($key, $finalScore, $member);
// lock release
