太變態(tài)了，每秒 10W 并發(fā)的無鎖緩存，你敢信？
有一類業(yè)務(wù)場景：
- 超高吞吐量，每秒要處理海量請求；
- 寫多讀少，大部分請求是對數(shù)據(jù)進(jìn)行修改，少部分請求對數(shù)據(jù)進(jìn)行讀?。?/li>
快狗打車，場景舉例：
- 司機(jī)地理位置信息會隨時變化，可能每幾秒鐘地理位置要修改一次；
- 用戶打車的時候查看某個司機(jī)的地理位置，查詢地理位置的頻率相對較低；
這里要用到兩個接口：
(1) 大量修改司機(jī)信息：
void SetDriverInfo(long driver_id, DriverInfo info);(2) 相對少量查詢司機(jī)信息：
DriverInfo GetDriverInfo(long driver_id); 這一類業(yè)務(wù)，一般怎么實(shí)現(xiàn)呢？
具體到底層的實(shí)現(xiàn)，往往是一個Map內(nèi)存緩存：
- 查詢key定長，例如：司機(jī)ID；
- 返回value也定長，例如：司機(jī)實(shí)體序列化后的二進(jìn)制串；
即，類似這樣的一個kv緩存結(jié)構(gòu)：
Map<driver_id, DriverInfo>這個kv內(nèi)存緩存是一個臨界資源，對它的并發(fā)訪問，有什么注意事項(xiàng)么？
臨界資源的訪問，需要注意加讀寫鎖，實(shí)施互斥。
以下，是加鎖寫入的偽代碼：
void SetDriverInfo(long driver_id, DriverInfo info){
WriteLock (m_lock);
Map<driver_id>= info;
UnWriteLock(m_lock);
}畫外音：假設(shè)info已經(jīng)序列化。
以下，是加鎖讀取的偽代碼：
DriverInfo GetDriverInfo(long driver_id){
DriverInfo t;
ReadLock(m_lock);
t= Map<driver_id>;
UnReadLock(m_lock);
return t;
}當(dāng)吞吐量很高時，上述流程可能存在什么問題？
假設(shè)快狗打車有100w司機(jī)同時在線，每個司機(jī)每5秒更新一次經(jīng)緯度狀態(tài)，那么每秒就有20w次寫并發(fā)操作。
假設(shè)快狗打車日訂單1000w個，平均每秒大概也有300個下單，對應(yīng)到查詢并發(fā)量，大概每秒1000級別的并發(fā)讀操作。
在這樣的吞吐量下（每秒20w寫，1k讀），鎖m_lock會成為潛在瓶頸，導(dǎo)致Map訪問效率極低。
有什么潛在的優(yōu)化方法么？
鎖沖突之所以嚴(yán)重，是因?yàn)檎麄€Map共用一把鎖，鎖的粒度太粗。
畫外音：可以認(rèn)為是一個數(shù)據(jù)庫的“庫級別鎖”。
是否可能進(jìn)行水平拆分，來降低鎖沖突呢？
答案是肯定的。
畫外音：類似于數(shù)據(jù)庫里的分庫，把一個庫鎖變成多個庫鎖，來提高并發(fā)，降低鎖沖突。
我們可以把1個Map水平切分成N個Map：
void SetDriverInfo(long driver_id, DriverInfo info){
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把鎖
}如此優(yōu)化，能否提高性能？
- 一個Map變成了N個Map，每個Map的并發(fā)量，變成了1/N；
- 同時，每個Map的數(shù)據(jù)量，變成了1/N；
所以理論上，鎖沖突會成平方指數(shù)降低，性能會提升。
有沒有可能，進(jìn)一步細(xì)化鎖粒度，一個元素一把鎖呢？
答案也是肯定的。
畫外音：可以認(rèn)為是一個數(shù)據(jù)庫的“庫級別鎖”，優(yōu)化為“行級別鎖”。
不妨設(shè)driver_id是遞增生成的，并且假設(shè)內(nèi)存比較大，此時可以把Map優(yōu)化成Array，并把鎖的粒度細(xì)化到最細(xì)的，每個司機(jī)信息一個鎖：
void SetDriverInfo(long driver_id, DriverInfo info){
index = driver_id;
WriteLock (m_lock[index]); //超級大內(nèi)存，一條記錄一個鎖，鎖行鎖
Array[index]= info; //driver_id就是Array下標(biāo)
UnWriteLock (m_lock[index]); // 解鎖行鎖
}
這個方案使得鎖沖突降到了最低，但鎖資源大增，在數(shù)據(jù)量非常大的情況下，內(nèi)存往往是裝不下的。
畫外音：數(shù)據(jù)量比較小的時候，可以一個元素一把鎖，典型的是連接池，每個連接用一把鎖表示連接是否可用。
還沒有方法進(jìn)一步降低鎖沖突，提升并發(fā)量呢？
寫多讀少的業(yè)務(wù)，有一種優(yōu)化方案：無鎖緩存，將鎖沖突降低到。
無鎖緩存，可能存在什么問題？
如果緩存不加鎖，讀寫吞吐量可以達(dá)到極限，但是多線程對緩存中同一塊定長數(shù)據(jù)進(jìn)行寫操作時，有可能出現(xiàn)不一致的臟數(shù)據(jù)。
這個方案為了提高性能，犧牲了一致性。
讀取時，獲取到了錯誤的數(shù)據(jù)，是不能接受的。
畫外音：作為緩存，允許cache miss，卻不允許讀臟數(shù)據(jù)。
臟數(shù)據(jù)是如何產(chǎn)生的？
不加鎖，在多線程并發(fā)寫時，可能出現(xiàn)以下情況：
- 線程1對緩存進(jìn)行操作，對key想要寫入value1；
- 線程2對緩存進(jìn)行操作，對key想要寫入value2；
- 不加鎖，線程1和線程2對同一個定長區(qū)域進(jìn)行一個并發(fā)的寫操作，可能每個線程寫成功一半，導(dǎo)致出現(xiàn)臟數(shù)據(jù)產(chǎn)生，最終的結(jié)果即不是value1也不是value2，而是一個亂七八糟的不符合預(yù)期的值value-unexpected；
如何解決上述問題呢？
本質(zhì)上，這是一個數(shù)據(jù)完整性問題。
并發(fā)寫入的數(shù)據(jù)分別是value1和value2，讀出的數(shù)據(jù)是value-unexpected，數(shù)據(jù)被篡改，這本質(zhì)上是一個數(shù)據(jù)完整性的問題。
通常如何保證數(shù)據(jù)的完整性呢？
例如：運(yùn)維如何保證，從中控機(jī)分發(fā)到上線機(jī)上的二進(jìn)制沒有被篡改？
md5。
又例如：即時通訊系統(tǒng)中，如何保證接受方收到的消息，就是發(fā)送方發(fā)送的消息？
發(fā)送方除了發(fā)送消息本身，還要發(fā)送消息的簽名，接收方收到消息后要校驗(yàn)簽名，以確保消息是完整的，未被篡改。
“簽名”是一種常見的保證數(shù)據(jù)完整性的方案。
加入“簽名”保證數(shù)據(jù)的完整性之后，讀寫流程需要如何升級？
加上簽名之后，不但緩存要寫入定長value本身，還要寫入定長簽名（例如16bitCRC校驗(yàn)）：
- 線程1對緩存進(jìn)行操作，對key想要寫入value1，寫入簽名v1-sign；
- 線程2對緩存進(jìn)行操作，對key想要寫入value2，寫入簽名v2-sign；
- 如果不加鎖，線程1和線程2對同一個定長區(qū)域進(jìn)行一個并發(fā)的寫操作，可能每個線程寫成功一半，導(dǎo)致出現(xiàn)臟數(shù)據(jù)產(chǎn)生，最終的結(jié)果即不是value1也不是value2，而是一個亂七八糟的不符合預(yù)期的值value-unexpected，但簽名，一定是v1-sign或者v2-sign中的任意一個；
畫外音：16bit/32bit的寫可以保證原子性。
- 數(shù)據(jù)讀取的時候，不但要取出value，還要像消息接收方收到消息一樣，校驗(yàn)一下簽名，如果發(fā)現(xiàn)簽名不一致，緩存則返回NULL，即cache miss；
當(dāng)然，對應(yīng)到司機(jī)地理位置，除了內(nèi)存緩存之前，肯定需要timer對緩存中的數(shù)據(jù)定期落盤，寫入數(shù)據(jù)庫，如果cache miss，可以從數(shù)據(jù)庫中讀取數(shù)據(jù)。
這個方案，巧不巧秒？
總結(jié)
業(yè)務(wù)場景：
- 超高并發(fā)；
- 寫多讀少；
- 定長value；
可以用以下方法來提升吞吐量：
- 水平拆分來降低鎖沖突，思路是：單庫變多庫；
- Map轉(zhuǎn)Array的方式來最小化鎖沖突，一條記錄一個鎖，思路是：庫鎖變行鎖；
- 無鎖，最大化并發(fā)，思路是：行鎖變無鎖，完整性與性能的折衷；
- 通過簽名的方式保證數(shù)據(jù)的完整性，實(shí)現(xiàn)無鎖緩存，思路是：寫時寫簽名，讀時校驗(yàn)簽名；
知其然，知其所以然。
思路比結(jié)論更重要。
