寫(xiě)入流程
- 先加鎖
- 往隊(duì)列里加入數(shù)據(jù)（有可能有別的線程也加入數(shù)據(jù)）
- wait等待隊(duì)首數(shù)據(jù)的線程被喚醒（此時(shí)其它數(shù)據(jù)可以寫(xiě)入隊(duì)列）
while (!w.done && &w != writers_.front()) {
? w.cv.Wait();
}
- 持有隊(duì)首數(shù)據(jù)的線程被喚醒忧侧，獲取最新的sequence
- 獲取當(dāng)前隊(duì)列里的最后一個(gè)數(shù)據(jù)
- 將當(dāng)前隊(duì)首至隊(duì)尾的數(shù)據(jù)（為了批量寫(xiě)入）整合
- 解鎖（此時(shí)后面的線程又可以寫(xiě)入隊(duì)列拥诡，因?yàn)殛?duì)首到隊(duì)尾的數(shù)據(jù)已經(jīng)被緩存），且第一個(gè)插入的線程為新的隊(duì)首瞒瘸，wait等待喚醒（步驟2）
- 插入數(shù)據(jù)
- 上鎖操作隊(duì)列拳锚，將此線程隊(duì)首至隊(duì)尾的數(shù)據(jù)都置為已讀，并且喚醒相關(guān)數(shù)據(jù)的線程（這樣喚醒的時(shí)候發(fā)現(xiàn)w.done猾漫，自己的數(shù)據(jù)已經(jīng)和別人的一起寫(xiě)進(jìn)去了点晴，所以直接返回）
- 喚醒此時(shí)新的隊(duì)首
leveldb多線程寫(xiě)的關(guān)鍵
經(jīng)過(guò)系統(tǒng)性的分析，我們了解到leveldb實(shí)現(xiàn)高性能安全讀寫(xiě)的幾個(gè)關(guān)鍵點(diǎn)：
- 利用隊(duì)列將寫(xiě)入線程排隊(duì)有序執(zhí)行悯周，寫(xiě)操作實(shí)現(xiàn)了邏輯上的單線程操作粒督；
- 在寫(xiě)入文件和MemTable過(guò)程是無(wú)鎖狀態(tài)，此時(shí)可以同時(shí)寫(xiě)入和讀取數(shù)據(jù)禽翼，合并多個(gè)數(shù)據(jù)寫(xiě)入進(jìn)一步提升寫(xiě)入性能屠橄；
- 利用原子指針代替鎖避免了鎖本身帶來(lái)的線程切換開(kāi)銷；
- 如果通過(guò)迭代器遍歷節(jié)點(diǎn)時(shí)闰挡，因?yàn)閷?xiě)入和讀取指針都是原子的锐墙，所以也不存在安全問(wèn)題；
同時(shí)讀寫(xiě)為何是安全的
- 整個(gè)寫(xiě)入過(guò)程操作鏈表的時(shí)候有兩個(gè)步驟长酗，分別是先讓節(jié)點(diǎn)指向后向節(jié)點(diǎn)溪北，然后再讓前向節(jié)點(diǎn)指向自己，第一步因?yàn)闆](méi)有實(shí)際操作鏈表夺脾，所以本身就是安全的之拨，只有第二步執(zhí)行的過(guò)程如果線程切換或者同時(shí)讀取(畢竟都是多核的機(jī)器)才會(huì)有可能存在不安全的可能；
- 無(wú)論是寫(xiě)入還是讀取(通過(guò)迭代器順序讀取除外)咧叭，都是先要seek蚀乔，即定位，seek是從高到低方式訪問(wèn)鏈表逐漸逼近期望節(jié)點(diǎn)菲茬，而節(jié)點(diǎn)插入是從低到高插入鏈表吉挣，一旦seek過(guò)程訪問(wèn)了還沒(méi)有插入完畢的節(jié)點(diǎn)時(shí)派撕，該節(jié)點(diǎn)的低于當(dāng)前高度的鏈表已經(jīng)插入完畢，所以也不存在安全問(wèn)題听想；
- 單向鏈表插入實(shí)際上只有一步操作腥刹，只要這個(gè)操作是原子的可以保證安全。
- 因?yàn)镸emTable沒(méi)有刪除操作汉买，永遠(yuǎn)是添加操作衔峰，也進(jìn)一步鞏固了該設(shè)計(jì)方案
