如何實現(xiàn)超高并發(fā)的無鎖緩存？
一、需求緣起
【業(yè)務(wù)場景】
有一類寫多讀少的業(yè)務(wù)場景：大部分請求是對數(shù)據(jù)進行修改，少部分請求對數(shù)據(jù)進行讀取。
例子1：滴滴打車，某個司機地理位置信息的變化(可能每幾秒鐘有一個修改)，以及司機地理位置的讀取(用戶打車的時候查看某個司機的地理位置)。
void SetDriverInfo(long driver_id, DriverInfoi); // 大量請求調(diào)用修改司機信息，可能主要是GPS位置的修改
DriverInfo GetDriverInfo(long driver_id); // 少量請求查詢司機信息
例子2：統(tǒng)計計數(shù)的變化，某個url的訪問次數(shù)，用戶某個行為的反作弊計數(shù)(計數(shù)值在不停的變)以及讀取(只有少數(shù)時刻會讀取這類數(shù)據(jù))。
void AddCountByType(long type); // 大量增加某個類型的計數(shù)，修改比較頻繁
long GetCountByType(long type); // 少量返回某個類型的計數(shù)
【底層實現(xiàn)】
具體到底層的實現(xiàn)，往往是一個Map(本質(zhì)是一個定長key，定長value的緩存結(jié)構(gòu))來存儲司機的信息，或者某個類型的計數(shù)。
【臨界資源】
這個Map存儲了所有信息，當并發(fā)讀寫訪問時，它作為臨界資源，在讀寫之前，一般要進行加鎖操作，以司機信息存儲為例：
- 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司機同時在線，每個司機沒5秒更新一次經(jīng)緯度狀態(tài)，那么每秒就有20w次寫并發(fā)操作。假設(shè)滴滴日訂單1000w個，平均每秒大概也有300個下單，對應(yīng)到查詢并發(fā)量，可能是1000級別的并發(fā)讀操作。
上述實現(xiàn)方案沒有任何問題，但在并發(fā)量很大的時候(每秒20w寫，1k讀)，鎖m_lock會成為潛在瓶頸，在這類高并發(fā)環(huán)境下寫多讀少的業(yè)務(wù)倉井，如何來進行優(yōu)化，是本文將要討論的問題。
二、水平切分+鎖粒度優(yōu)化
上文中之所以鎖沖突嚴重，是因為所有司機都公用一把鎖，鎖的粒度太粗(可以認為是一個數(shù)據(jù)庫的“庫級別鎖”)，是否可能進行水平拆分(類似于數(shù)據(jù)庫里的分庫)，把一個庫鎖變成多個庫鎖，來提高并發(fā)，降低鎖沖突呢?顯然是可以的，把1個Map水平切分成多個Map即可：
- void SetDriverInfo(long driver_id, DriverInfoinfo){
- i= driver_id % N; // 水平拆分成N份，N個Map，N個鎖
- WriteLock (m_lock [i]); //鎖第i把鎖
- Map[i]<driver_id>= info; // 操作第i個Map
- UnWriteLock (m_lock[i]); // 解鎖第i把鎖
- }
每個Map的并發(fā)量(變成了1/N)和數(shù)據(jù)量都降低(變成了1/N)了，所以理論上，鎖沖突會成平方指數(shù)降低。
分庫之后，仍然是庫鎖，有沒有辦法變成數(shù)據(jù)庫層面所謂的“行級鎖”呢，難道要把x條記錄變成x個Map嗎，這顯然是不現(xiàn)實的。
三、MAP變Array+最細鎖粒度優(yōu)化
假設(shè)driver_id是遞增生成的，并且緩存的內(nèi)存比較大，是可以把Map優(yōu)化成Array，而不是拆分成N個Map，是有可能把鎖的粒度細化到最細的(每個記錄一個鎖)。
- void SetDriverInfo(long driver_id, DriverInfoinfo){
- index= driver_id;
- WriteLock (m_lock [index]); //超級大內(nèi)存，一條記錄一個鎖，鎖行鎖
- Array[index]= info; //driver_id就是Array下標
- UnWriteLock (m_lock[index]); // 解鎖行鎖
- }
和上一個方案相比，這個方案使得鎖沖突降到了最低，但鎖資源大增，在數(shù)據(jù)量非常大的情況下，一般不這么搞。數(shù)據(jù)量比較小的時候，可以一個元素一個鎖的(典型的是連接池，每個連接有一個鎖表示連接是否可用)。
上文中提到的另一個例子，用戶操作類型計數(shù)，操作類型是有限的，即使一個type一個鎖，鎖的沖突也可能是很高的，還沒有方法進一步提高并發(fā)呢?
四、把鎖去掉，變成無鎖緩存
【無鎖的結(jié)果】
- void AddCountByType(long type /*, int count*/){
- //不加鎖
- Array[type]++; // 計數(shù)++
- //Array[type] += count; // 計數(shù)增加count
- }
如果這個緩存不加鎖，當然可以達到最高的并發(fā)，但是多線程對緩存中同一塊定長數(shù)據(jù)進行操作時，有可能出現(xiàn)不一致的數(shù)據(jù)塊，這個方案為了提高性能，犧牲了一致性。在讀取計數(shù)時，獲取到了錯誤的數(shù)據(jù)，是不能接受的(作為緩存，允許cache miss，卻不允許讀臟數(shù)據(jù))。
【臟數(shù)據(jù)是如何產(chǎn)生的】
這個并發(fā)寫的臟數(shù)據(jù)是如何產(chǎn)生的呢，詳見下圖：
1)線程1對緩存進行操作，對key想要寫入value1
2)線程2對緩存進行操作，對key想要寫入value2
3)如果不加鎖，線程1和線程2對同一個定長區(qū)域進行一個并發(fā)的寫操作，可能每個線程寫成功一半，導(dǎo)致出現(xiàn)臟數(shù)據(jù)產(chǎn)生，最終的結(jié)果即不是value1也不是value2，而是一個亂七八糟的不符合預(yù)期的值value-unexpected。
【數(shù)據(jù)完整性問題】
并發(fā)寫入的數(shù)據(jù)分別是value1和value2，讀出的數(shù)據(jù)是value-unexpected，數(shù)據(jù)的篡改，這本質(zhì)上是一個數(shù)據(jù)完整性的問題。通常如何保證數(shù)據(jù)的完整性呢?
例子1：運維如何保證，從中控機分發(fā)到上線機上的二進制沒有被篡改?
回答：md5
例子2：即時通訊系統(tǒng)中，如何保證接受方收到的消息，就是發(fā)送方發(fā)送的消息?
回答：發(fā)送方除了發(fā)送消息本身，還要發(fā)送消息的簽名，接收方收到消息后要校驗簽名，以確保消息是完整的，未被篡改。
當當當當 => “簽名”是一種常見的保證數(shù)據(jù)完整性的常見方案。
【加上簽名之后的流程】
加上簽名之后，不但緩存要寫入定長value本身，還要寫入定長簽名(例如16bitCRC校驗)：
1)線程1對緩存進行操作，對key想要寫入value1，寫入簽名v1-sign
2)線程2對緩存進行操作，對key想要寫入value2，寫入簽名v2-sign
3)如果不加鎖，線程1和線程2對同一個定長區(qū)域進行一個并發(fā)的寫操作，可能每個線程寫成功一半，導(dǎo)致出現(xiàn)臟數(shù)據(jù)產(chǎn)生，最終的結(jié)果即不是value1也不是value2，而是一個亂七八糟的不符合預(yù)期的值value-unexpected，但簽名，一定是v1-sign或者v2-sign中的任意一個
4)數(shù)據(jù)讀取的時候，不但要取出value，還要像消息接收方收到消息一樣，校驗一下簽名，如果發(fā)現(xiàn)簽名不一致，緩存則返回NULL，即cache miss。
當然，對應(yīng)到司機地理位置，與URL訪問計數(shù)的case，除了內(nèi)存緩存之前，肯定需要timer對緩存中的數(shù)據(jù)定期落盤，寫入數(shù)據(jù)庫，如果cache miss，可以從數(shù)據(jù)庫中讀取數(shù)據(jù)。
五、總結(jié)
在【超高并發(fā)】，【寫多讀少】，【定長value】的【業(yè)務(wù)緩存】場景下：
1)可以通過水平拆分來降低鎖沖突
2)可以通過Map轉(zhuǎn)Array的方式來最小化鎖沖突，一條記錄一個鎖
3)可以把鎖去掉，最大化并發(fā)，但帶來的數(shù)據(jù)完整性的破壞
4)可以通過簽名的方式保證數(shù)據(jù)的完整性，實現(xiàn)無鎖緩存
