無鎖緩存如何實(shí)現(xiàn)

一、需求緣起

【業(yè)務(wù)場景】

有一類寫多讀少的業(yè)務(wù)場景：大部分請求是對數(shù)據(jù)進(jìn)行修改，少部分請求對數(shù)據(jù)進(jìn)行讀取。

例子1：滴滴打車，某個(gè)司機(jī)地理位置信息的變化（可能每幾秒鐘有一個(gè)修改），以及司機(jī)地理位置的讀?。ㄓ脩舸蜍嚨臅r(shí)候查看某個(gè)司機(jī)的地理位置）。

void SetDriverInfo（long driver_id， DriverInfoi）; // 大量請求調(diào)用修改司機(jī)信息，可能主要是GPS位置的修改

DriverInfo GetDriverInfo（long driver_id）; // 少量請求查詢司機(jī)信息

例子2：統(tǒng)計(jì)計(jì)數(shù)的變化，某個(gè)url的訪問次數(shù)，用戶某個(gè)行為的反作弊計(jì)數(shù)（計(jì)數(shù)值在不停的變）以及讀?。ㄖ挥猩贁?shù)時(shí)刻會(huì)讀取這類數(shù)據(jù)）。

void Ad dCountByType（long type）; // 大量增加某個(gè)類型的計(jì)數(shù)，修改比較頻繁

long GetCountByType（long type）; // 少量返回某個(gè)類型的計(jì)數(shù)

【底層實(shí)現(xiàn)】

具體到底層的實(shí)現(xiàn)，往往是一個(gè)Map（本質(zhì)是一個(gè)定長key，定長value的緩存結(jié)構(gòu)）來存儲(chǔ)司機(jī)的信息，或者某個(gè)類型的計(jì)數(shù)。

【臨界資源】

這個(gè)Map存儲(chǔ)了所有信息，當(dāng)并發(fā)讀寫訪問時(shí)，它作為臨界資源，在讀寫之前，一般要進(jìn)行加鎖操作，以司機(jī)信息存儲(chǔ)為例：

void SetDriverInfo（long driver_id， DriverInfoinfo）{ WriteLock （m_lock）; Map《driver_id》= info; UnWriteLock（m_lock）; } DriverInfo GetDriverInfo（long driver_id）{ DriverInfo t; ReadLock（m_lock）; t= Map《driver_id》; UnReadLock（m_lock）; return t; }

【并發(fā)鎖瓶頸】

假設(shè)滴滴有100w司機(jī)同時(shí)在線，每個(gè)司機(jī)沒5秒更新一次經(jīng)緯度狀態(tài)，那么每秒就有20w次寫并發(fā)操作。假設(shè)滴滴日訂單1000w個(gè)，平均每秒大概也有300個(gè)下單，對應(yīng)到查詢并發(fā)量，可能是1000級(jí)別的并發(fā)讀操作。

上述實(shí)現(xiàn)方案沒有任何問題，但在并發(fā)量很大的時(shí)候（每秒20w寫，1k讀），鎖m_lock會(huì)成為潛在瓶頸，在這類高并發(fā)環(huán)境下寫多讀少的業(yè)務(wù)倉井，如何來進(jìn)行優(yōu)化，是本文將要討論的問題。

二、水平切分+鎖粒度優(yōu)化

上文中之所以鎖沖突嚴(yán)重，是因?yàn)樗兴緳C(jī)都公用一把鎖，鎖的粒度太粗（可以認(rèn)為是一個(gè)數(shù)據(jù)庫的“庫級(jí)別鎖”），是否可能進(jìn)行水平拆分（類似于數(shù)據(jù)庫里的分庫），把一個(gè)庫鎖變成多個(gè)庫鎖，來提高并發(fā)，降低鎖沖突呢？顯然是可以的，把1個(gè)Map水平切分成多個(gè)Map即可：

void SetDriverInfo（long driver_id， DriverInfoinfo）{ i= driver_id % N; // 水平拆分成N份，N個(gè)Map，N個(gè)鎖 WriteLock （m_lock ［i］）; //鎖第i把鎖 Map［i］《driver_id》= info; // 操作第i個(gè)Map UnWriteLock （m_lock［i］）; // 解鎖第i把鎖 }

每個(gè)Map的并發(fā)量（變成了1/N）和數(shù)據(jù)量都降低（變成了1/N）了，所以理論上，鎖沖突會(huì)成平方指數(shù)降低。

分庫之后，仍然是庫鎖，有沒有辦法變成數(shù)據(jù)庫層面所謂的“行級(jí)鎖”呢，難道要把x條記錄變成x個(gè)Map嗎，這顯然是不現(xiàn)實(shí)的。

三、MAP變Array+最細(xì)鎖粒度優(yōu)化

假設(shè)driver_id是遞增生成的，并且緩存的內(nèi)存比較大，是可以把Map優(yōu)化成Array，而不是拆分成N個(gè)Map，是有可能把鎖的粒度細(xì)化到最細(xì)的（每個(gè)記錄一個(gè)鎖）。

void SetDriverInfo（long driver_id， DriverInfoinfo）{ index= driver_id; WriteLock （m_lock ［index］）; //超級(jí)大內(nèi)存，一條記錄一個(gè)鎖，鎖行鎖 Array［index］= info; //driver_id就是Array下標(biāo) UnWriteLock （m_lock［index］）; // 解鎖行鎖 }

無鎖緩存如何實(shí)現(xiàn)

和上一個(gè)方案相比，這個(gè)方案使得鎖沖突降到了最低，但鎖資源大增，在數(shù)據(jù)量非常大的情況下，一般不這么搞。數(shù)據(jù)量比較小的時(shí)候，可以一個(gè)元素一個(gè)鎖的（典型的是連接池，每個(gè)連接有一個(gè)鎖表示連接是否可用）。

上文中提到的另一個(gè)例子，用戶操作類型計(jì)數(shù)，操作類型是有限的，即使一個(gè)type一個(gè)鎖，鎖的沖突也可能是很高的，還沒有方法進(jìn)一步提高并發(fā)呢？

四、把鎖去掉，變成無鎖緩存

【無鎖的結(jié)果】

void AddCountByType（long type /*， int count*/）{ //不加鎖 Array［type］++; // 計(jì)數(shù)++ //Array［type］ += count; // 計(jì)數(shù)增加count }

無鎖緩存如何實(shí)現(xiàn)

如果這個(gè)緩存不加鎖，當(dāng)然可以達(dá)到最高的并發(fā)，但是多線程對緩存中同一塊定長數(shù)據(jù)進(jìn)行操作時(shí)，有可能出現(xiàn)不一致的數(shù)據(jù)塊，這個(gè)方案為了提高性能，犧牲了一致性。在讀取計(jì)數(shù)時(shí)，獲取到了錯(cuò)誤的數(shù)據(jù)，是不能接受的（作為緩存，允許cache miss，卻不允許讀臟數(shù)據(jù)）。

【臟數(shù)據(jù)是如何產(chǎn)生的】

這個(gè)并發(fā)寫的臟數(shù)據(jù)是如何產(chǎn)生的呢，詳見下圖：

無鎖緩存如何實(shí)現(xiàn)

1）線程1對緩存進(jìn)行操作，對key想要寫入value1

2）線程2對緩存進(jìn)行操作，對key想要寫入value2

3）如果不加鎖，線程1和線程2對同一個(gè)定長區(qū)域進(jìn)行一個(gè)并發(fā)的寫操作，可能每個(gè)線程寫成功一半，導(dǎo)致出現(xiàn)臟數(shù)據(jù)產(chǎn)生，最終的結(jié)果即不是value1也不是value2，而是一個(gè)亂七八糟的不符合預(yù)期的值value-unexpected。

【數(shù)據(jù)完整性問題】

并發(fā)寫入的數(shù)據(jù)分別是value1和value2，讀出的數(shù)據(jù)是value-unexpected，數(shù)據(jù)的篡改，這本質(zhì)上是一個(gè)數(shù)據(jù)完整性的問題。通常如何保證數(shù)據(jù)的完整性呢？

例子1：運(yùn)維如何保證，從中控機(jī)分發(fā)到上線機(jī)上的二進(jìn)制沒有被篡改？

回答：md5

例子2：即時(shí)通訊系統(tǒng)中，如何保證接受方收到的消息，就是發(fā)送方發(fā)送的消息？

回答：發(fā)送方除了發(fā)送消息本身，還要發(fā)送消息的簽名，接收方收到消息后要校驗(yàn)簽名，以確保消息是完整的，未被篡改。

當(dāng)當(dāng)當(dāng)當(dāng) =》 “簽名”是一種常見的保證數(shù)據(jù)完整性的常見方案。

【加上簽名之后的流程】

無鎖緩存如何實(shí)現(xiàn)

加上簽名之后，不但緩存要寫入定長value本身，還要寫入定長簽名（例如16bitCRC校驗(yàn)）：

1）線程1對緩存進(jìn)行操作，對key想要寫入value1，寫入簽名v1-sign

2）線程2對緩存進(jìn)行操作，對key想要寫入value2，寫入簽名v2-sign

4）數(shù)據(jù)讀取的時(shí)候，不但要取出value，還要像消息接收方收到消息一樣，校驗(yàn)一下簽名，如果發(fā)現(xiàn)簽名不一致，緩存則返回NULL，即cache miss。

當(dāng)然，對應(yīng)到司機(jī)地理位置，與URL訪問計(jì)數(shù)的case，除了內(nèi)存緩存之前，肯定需要timer對緩存中的數(shù)據(jù)定期落盤，寫入數(shù)據(jù)庫，如果cache miss，可以從數(shù)據(jù)庫中讀取數(shù)據(jù)。