轉(zhuǎn)載請(qǐng)注明出處哈:http://carlosfu.iteye.com/blog/2269678

  最近有點(diǎn)忙，一直沒更新博客，繼續(xù)堅(jiān)持下去。

一、背景 

  1. 什么是緩存無底洞問題：

 2. 緩存無底洞產(chǎn)生的原因：

   鍵值數(shù)據(jù)庫或者緩存系統(tǒng)，由于通常采用hash函數(shù)將key映射到對(duì)應(yīng)的實(shí)例，造成key的分布與業(yè)務(wù)無關(guān)，但是由于數(shù)據(jù)量、訪問量的需求，需要使用分布式后（無論是客戶端一致性哈性、redis-cluster、codis），批量操作比如批量獲取多個(gè)key(例如redis的mget操作)，通常需要從不同實(shí)例獲取key值，相比于單機(jī)批量操作只涉及到一次網(wǎng)絡(luò)操作，分布式批量操作會(huì)涉及到多次網(wǎng)絡(luò)io。

3. 無底洞問題帶來的危害：

  (1) 客戶端一次批量操作會(huì)涉及多次網(wǎng)絡(luò)操作，也就意味著批量操作會(huì)隨著實(shí)例的增多，耗時(shí)會(huì)不斷增大。

  (2) 服務(wù)端網(wǎng)絡(luò)連接次數(shù)變多，對(duì)實(shí)例的性能也有一定影響。

 
4. 結(jié)論：

  用一句通俗的話總結(jié)：更多的機(jī)器不代表更多的性能，所謂“無底洞”就是說投入越多不一定產(chǎn)出越多。

  分布式又是不可以避免的，因?yàn)槲覀兊木W(wǎng)站訪問量和數(shù)據(jù)量越來越大，一個(gè)實(shí)例根本坑不住，所以如何高效的在分布式緩存和存儲(chǔ)批量獲取數(shù)據(jù)是一個(gè)難點(diǎn)。

二、哈希存儲(chǔ)與順序存儲(chǔ)

   在分布式存儲(chǔ)產(chǎn)品中，哈希存儲(chǔ)與順序存儲(chǔ)是兩種重要的數(shù)據(jù)存儲(chǔ)和分布方式，這兩種方式不同也直接決定了批量獲取數(shù)據(jù)的不同，所以這里需要對(duì)這兩種數(shù)據(jù)的分布式方式進(jìn)行簡(jiǎn)要說明：

   1. hash分布：

   hash分布應(yīng)用于大部分key-value系統(tǒng)中，例如memcache, redis-cluster, twemproxy，即使像mysql在分庫分表時(shí)候，也經(jīng)常會(huì)用user%100這樣的方式。

   hash分布的主要作用是將key均勻的分布到各個(gè)機(jī)器，所以它的一個(gè)特點(diǎn)就是數(shù)據(jù)分散度較高，實(shí)現(xiàn)方式通常是hash(key)得到的整數(shù)再和分布式節(jié)點(diǎn)的某臺(tái)機(jī)器做映射，以redis-cluster為例子：

   問題：和業(yè)務(wù)沒什么關(guān)系，不支持范圍查詢。

  2. 順序分布

 3. 兩種分布方式的比較：

三、分布式緩存/存儲(chǔ)四種Mget解決方案

1. IO的優(yōu)化思路：

  (1) 命令本身的效率：例如sql優(yōu)化，命令優(yōu)化

  (2) 網(wǎng)絡(luò)次數(shù)：減少通信次數(shù)

  (3) 降低接入成本:長(zhǎng)連/連接池,NIO等。

  (4) IO訪問合并:O(n)到O(1)過程:批量接口(mget),

2.  如果只考慮減少網(wǎng)絡(luò)次數(shù)的話，mget會(huì)有如下模型：

3. 四種解決方案：

(1).串行mget

將Mget操作(n個(gè)key)拆分為逐次執(zhí)行N次get操作, 很明顯這種操作時(shí)間復(fù)雜度較高，它的操作時(shí)間=n次網(wǎng)絡(luò)時(shí)間+n次命令時(shí)間，網(wǎng)絡(luò)次數(shù)是n，很顯然這種方案不是最優(yōu)的，但是足夠簡(jiǎn)單。

(2). 串行IO

    將Mget操作(n個(gè)key)，利用已知的hash函數(shù)算出key對(duì)應(yīng)的節(jié)點(diǎn)，這樣就可以得到一個(gè)這樣的關(guān)系：Map<node, somekeys>，也就是每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的一些keys

    它的操作時(shí)間=node次網(wǎng)絡(luò)時(shí)間+n次命令時(shí)間，網(wǎng)絡(luò)次數(shù)是node的個(gè)數(shù)，很明顯這種方案比第一種要好很多，但是如果節(jié)點(diǎn)數(shù)足夠多，還是有一定的性能問題。

(3). 并行IO

   此方案是將方案（2）中的最后一步，改為多線程執(zhí)行，網(wǎng)絡(luò)次數(shù)雖然還是nodes.size()，但網(wǎng)絡(luò)時(shí)間變?yōu)閛(1)，但是這種方案會(huì)增加編程的復(fù)雜度。

   它的操作時(shí)間=1次網(wǎng)絡(luò)時(shí)間+n次命令時(shí)間

(4). hash-tag實(shí)現(xiàn)。

    第二節(jié)提到過，由于hash函數(shù)會(huì)造成key隨機(jī)分配到各個(gè)節(jié)點(diǎn)，那么有沒有一種方法能夠強(qiáng)制一些key到指定節(jié)點(diǎn)到指定的節(jié)點(diǎn)呢?

    redis提供了這樣的功能，叫做hash-tag。什么意思呢？假如我們現(xiàn)在使用的是redis-cluster（10個(gè)redis節(jié)點(diǎn)組成），我們現(xiàn)在有1000個(gè)k-v，那么按照hash函數(shù)(crc16)規(guī)則，這1000個(gè)key會(huì)被打散到10個(gè)節(jié)點(diǎn)上，那么時(shí)間復(fù)雜度還是上述(1)~(3)

    那么我們能不能像使用單機(jī)redis一樣，一次IO將所有的key取出來呢？hash-tag提供了這樣的功能，如果將上述的key改為如下，也就是用大括號(hào)括起來相同的內(nèi)容，那么這些key就會(huì)到指定的一個(gè)節(jié)點(diǎn)上。

   例如：

Java代碼  

1. user1,user2,user3......user1000  
2. {user}1,{user}2,{user}3.......{user}1000  

例如下圖：它的操作時(shí)間=1次網(wǎng)絡(luò)時(shí)間+n次命令時(shí)間

3. 四種批量操作解決方案對(duì)比：

四、總結(jié)和建議

    無底洞問題對(duì)資源和性能有一定影響，但是其實(shí)大部分系統(tǒng)不需要考慮這個(gè)問題，因?yàn)?/p>

    1. 99%公司的數(shù)據(jù)和流量無法和facebook相比。

    2. redis/memcache的分布式集群通常來講是按照項(xiàng)目組做隔離的，以我們經(jīng)驗(yàn)來看一般不會(huì)超過50對(duì)主從。   

    所以這里只是提供了一種優(yōu)化的思路，開闊一下視野。

五、參考文獻(xiàn)

1. Facebook's Memcached Multiget Hole: More machines != More Capacity  
2. Multiget的無底洞問題
3. 再說memcache的multiget hole（無底洞）