| |
我們的需求是這樣的：服務(wù)程序每周會(huì)停機(jī)一次。每周總共涉及的玩家數(shù)據(jù) 10 萬組。每組數(shù)據(jù) 4k 到 32K 之間。都是文本數(shù)據(jù)�？梢钥闯梢粋�(gè) id 到數(shù)據(jù)串的 key/value 數(shù)據(jù)儲(chǔ)存服務(wù)。經(jīng)估算，總數(shù)據(jù)可以全部放入內(nèi)存。數(shù)據(jù)會(huì)頻繁更新，更新后長(zhǎng)度會(huì)改變。
我花了一天實(shí)現(xiàn)這個(gè) k/v 內(nèi)存數(shù)據(jù)服務(wù)。為了最大利用內(nèi)存，并同時(shí)保證效率，以及代碼實(shí)現(xiàn)的簡(jiǎn)潔。我采用預(yù)先分配好整塊內(nèi)存的方案，把內(nèi)存切割成 1K 為單位的區(qū)塊。并用單向鏈表串起來�？紤]到內(nèi)存 cache 的命中效率。鏈表指針本身和數(shù)據(jù)儲(chǔ)存區(qū)分離。（大多數(shù)時(shí)候，我們只需要訪問鏈表指針，而不需要訪問具體數(shù)據(jù)）
鏈表指針采用序號(hào)，而非內(nèi)存地址。這樣即使在 64bit 系統(tǒng)上，依然使用 4 字節(jié)索引（可以最大可管理 4T 數(shù)據(jù)，足夠了）。單向鏈表可以比雙向鏈表節(jié)省一半的指針操作以及節(jié)約少量?jī)?nèi)存。代價(jià)是代碼寫起來繁雜一點(diǎn)。
所有內(nèi)存區(qū)塊分成兩部分：空閑區(qū)塊和已用區(qū)塊。一開始全部空間都是空閑。一旦向內(nèi)放入一段數(shù)據(jù)，就從空閑鏈表上摘下夠用的區(qū)塊，放到已用鏈表的尾部。如果 cache 空間滿，則從已用區(qū)塊鏈表頭部移掉一些空間還給空間區(qū)塊（這些數(shù)據(jù)區(qū)是長(zhǎng)久未訪問過的）。每次讀取一段數(shù)據(jù)，都將其調(diào)整到已用鏈表的末尾，保證最后才清理。
另外做一個(gè) hash 表，從 id 映射到在 cache 中區(qū)塊段的頭（由于是單向鏈表，具體實(shí)現(xiàn)時(shí)應(yīng)保存上一個(gè)節(jié)點(diǎn)）。這樣可以用 O(1) 時(shí)間查詢指定 id 對(duì)應(yīng)的數(shù)據(jù)區(qū)，
保存在 cache 中的數(shù)據(jù)不必在地址上完全連續(xù)，這好比磁盤的分簇管理。和磁盤不同，內(nèi)存的隨機(jī)訪問性能和順序訪問性能差異更小。這樣有利于內(nèi)存空間利用效率。
本新聞共 2頁(yè),當(dāng)前在第 2頁(yè) 1 2 |
| 【收藏】【打印】【進(jìn)入論壇】 |
|
|
|
|
| |
|
|
|
