NoSQL理論研究：內(nèi)存是新的硬盤，硬盤是新的磁帶
“內(nèi)存是新的硬盤，硬盤是新的磁帶”此話出自圖靈獎(jiǎng)得主Jim Gray。
一、前言
我理解這句話的意思是，我們應(yīng)該把隨機(jī)IO都放到內(nèi)存中去，而把像磁帶一樣的順序IO留給硬盤（這里不包括SSD）。
如果應(yīng)用沒(méi)有達(dá)到一定的級(jí)別，可能我們看上面兩句話都會(huì)覺(jué)得太geek，然而在應(yīng)用數(shù)據(jù)量日益龐大，動(dòng)態(tài)內(nèi)容比例日益增大的今天，再忽視這個(gè)基本準(zhǔn)則將會(huì)是一個(gè)災(zāi)難。
今天我們談一下這一理論在NoSQL產(chǎn)品中的展現(xiàn)。
二、實(shí)現(xiàn)
問(wèn)題一：宕機(jī)數(shù)據(jù)丟失
我們先看一下幾個(gè)杰出的NoSQL代表，Cassandra，MongoDB，Redis。他們幾乎都使用了同一種存儲(chǔ)模式，就是將寫(xiě)操作在內(nèi)存中進(jìn)行，定時(shí)或按某一條件將內(nèi)存中的數(shù)據(jù)直接寫(xiě)到磁盤上。這樣做的好處是我們可以充分利用內(nèi)存在隨機(jī)IO上的優(yōu)勢(shì)，而避免了直接寫(xiě)磁盤帶來(lái)的隨機(jī)IO瓶頸：磁盤尋道時(shí)間。當(dāng)然，壞處就是如果遭遇宕機(jī)等問(wèn)題時(shí)，可能會(huì)丟失一些數(shù)據(jù)。
解決宕機(jī)丟數(shù)據(jù)的問(wèn)題有兩個(gè)方法：
1.實(shí)時(shí)記錄操作日志
這時(shí)通常的做法是當(dāng)一個(gè)寫(xiě)操作到達(dá)，系統(tǒng)首先會(huì)往日志文件里追加一條寫(xiě)記錄，成功后再操作內(nèi)存進(jìn)行寫(xiě)數(shù)據(jù)操作。而由于日志文件是不斷追加的，因此也就保證了不會(huì)有大量的隨機(jī)IO產(chǎn)生。
2.Quorum NRW
這一理論是基于集群式存儲(chǔ)的，其原理是如果集群有N個(gè)結(jié)點(diǎn)，那么如果我們每次寫(xiě)操作需要至少同步到W個(gè)結(jié)點(diǎn)才算成功，而每次讀操作只要從R個(gè)結(jié)點(diǎn)讀數(shù)據(jù)就一定能保證其得到正確結(jié)果（如果某一結(jié)點(diǎn)有此數(shù)據(jù)，既成功，如果所有R個(gè)結(jié)點(diǎn)都無(wú)數(shù)據(jù)，則說(shuō)明無(wú)此數(shù)據(jù)）。而NRW之間的關(guān)系必須滿足N < R + W 。其實(shí)這一理論并不難理解，我們可以將這個(gè)不等式做一下移項(xiàng)：R > N – W ，我們有N個(gè)結(jié)點(diǎn)，寫(xiě)的時(shí)候最少寫(xiě)W個(gè)才算成功，也就是W個(gè)結(jié)點(diǎn)有這份數(shù)據(jù)，那么N-W就是說(shuō)可能沒(méi)有某一份數(shù)據(jù)的最大結(jié)點(diǎn)數(shù)。最多可能有N-W個(gè)結(jié)點(diǎn)沒(méi)有某一數(shù)據(jù)，那如果我們進(jìn)行數(shù)據(jù)讀取操作時(shí)，讀到大于N-W個(gè)結(jié)點(diǎn)，那么必然有一個(gè)以上的結(jié)點(diǎn)是有這份數(shù)據(jù)的。所以要求R > N-W。
所以可能你已經(jīng)想明白了，為了防止數(shù)據(jù)丟失，我們采用的實(shí)際是簡(jiǎn)單的冗余備份的方法。數(shù)據(jù)寫(xiě)到多臺(tái)機(jī)器會(huì)比寫(xiě)單臺(tái)機(jī)器的磁盤快嗎？對(duì)。相對(duì)于直接的磁盤操作，跨網(wǎng)絡(luò)進(jìn)行內(nèi)存操作可以更快。其最簡(jiǎn)單的例子就是改進(jìn)的一致性hash：
上圖摘自Amazon的Dynamo文檔，key的hash值位于A，B結(jié)點(diǎn)間的數(shù)據(jù)，并不是只存在B結(jié)點(diǎn)上，而是順著環(huán)的方向分別在C和D結(jié)點(diǎn)進(jìn)行備份。當(dāng)然這樣做的好處并不完全在于上面說(shuō)的冗余備份。
當(dāng)然，很多時(shí)候是上面兩種解決方法同時(shí)使用以保證數(shù)據(jù)的高可用性。
問(wèn)題二：內(nèi)存容量的限制
當(dāng)我們將內(nèi)存當(dāng)作硬盤來(lái)用的時(shí)候，我們必然會(huì)面臨容量問(wèn)題。這也是我們上面說(shuō)到的數(shù)據(jù)會(huì)定時(shí)flush到磁盤的原因，當(dāng)內(nèi)存中的數(shù)據(jù)已經(jīng)超出可用內(nèi)存的大小，那么我們就需要將其進(jìn)行落地操作，對(duì)swap的過(guò)度使用是不符合我們初衷的，也是達(dá)不到高效隨機(jī)IO的效果的。這里也有兩種解決方案：
1.應(yīng)用層swap
采用這種方法的有TokyoCabinet和Redis兩個(gè)產(chǎn)品。TokyoCabinet主要是通過(guò)mmap提高IO效率，而其mmap到的只有數(shù)據(jù)文件頭部的一部分內(nèi)容。一旦數(shù)據(jù)文件大于其設(shè)置的最大mmap長(zhǎng)度（由參數(shù)xmsize控制），那剩下的部分就是純粹的低效磁盤操作了。于是它提供了一種類似于Memcached的緩存機(jī)制，通過(guò)參數(shù)rcnum配置，將一些通過(guò)LRU機(jī)制篩選出來(lái)的熱數(shù)據(jù)進(jìn)行key—value式的緩存，這一部分內(nèi)存是和mmap占用的內(nèi)存完全獨(dú)立的。同樣的，Redis在2.0版本之后增加了對(duì)磁盤存儲(chǔ)的支持，其機(jī)制與TokyoCabinet類似，也是通過(guò)數(shù)據(jù)操作來(lái)判斷數(shù)據(jù)的熱度，并將熱數(shù)據(jù)盡量放到內(nèi)存中。
2.多版本的數(shù)據(jù)合并
什么叫多版本的數(shù)據(jù)合并呢？我們上面講Bigtable，或其開(kāi)源版本Cassandra，都是通過(guò)定時(shí)將內(nèi)存中的數(shù)據(jù)塊flush到磁盤中，那么我們會(huì)想，如果這次是一個(gè)update操作，比如keyA的值從ValueA變成了ValueB，那么我們?cè)趂lush到磁盤的時(shí)候就得執(zhí)行對(duì)老數(shù)據(jù)ValueA的清除工作了。而這樣，是否就達(dá)不到我們希望進(jìn)行順序的磁盤IO的目的呢？沒(méi)錯(cuò)，這樣是達(dá)不到的，所以Bigtable類型的系統(tǒng)確實(shí)也并不是這樣做的，在flush磁盤的時(shí)候，并不會(huì)執(zhí)行合并操作，而是直接將內(nèi)存數(shù)據(jù)寫(xiě)入磁盤。這樣寫(xiě)是方便很多，那讀的時(shí)候可能會(huì)存在一個(gè)值有多個(gè)版本的情況，這時(shí)就需要我們來(lái)進(jìn)行多版本合并了。所以第二種方法就是將一段時(shí)間的寫(xiě)操作寫(xiě)成一個(gè)塊（可能并非一個(gè)文件），保證內(nèi)存的使用不會(huì)無(wú)限膨脹。在讀取時(shí)通過(guò)讀多個(gè)文件塊進(jìn)行數(shù)據(jù)版本合并來(lái)完成。
那如果存儲(chǔ)在磁盤的數(shù)據(jù)量是內(nèi)存容量的很多倍，我們可能會(huì)產(chǎn)生許多個(gè)數(shù)據(jù)塊，那么我們?cè)讷@取數(shù)據(jù)版本時(shí)，是否需要全部遍歷所有數(shù)據(jù)塊呢？當(dāng)然不用，如果你看過(guò)BigTable論文，相信你還記得它其中用到了bloom-filter算法。bloom-filter算法最廣泛的應(yīng)用是在搜索引擎爬蟲(chóng)中，它用于判斷一個(gè)URL是否存在于已抓取集合中，這一算法并不百分之百精準(zhǔn)（可能將不在集合中的數(shù)據(jù)誤判為在集合中，但不會(huì)出現(xiàn)相反的誤差），但其在時(shí)間復(fù)雜度上僅是幾次hash計(jì)算，而空間復(fù)雜度也非常低。Bigtable實(shí)現(xiàn)中也用到了bloom-filter算法，用它來(lái)判斷一個(gè)值是否在某一個(gè)集合中。而由于bloom-filter算法的特點(diǎn)，我們只會(huì)多讀（幾率很?。?，不會(huì)少讀數(shù)據(jù)塊。于是我們就實(shí)現(xiàn)對(duì)遠(yuǎn)遠(yuǎn)大于物理內(nèi)存容量的數(shù)據(jù)的存儲(chǔ)。
三、結(jié)尾
好了，就寫(xiě)到這里，關(guān)于NoSQL中對(duì)此原理的應(yīng)用還有更多理解和認(rèn)識(shí)的同學(xué)，歡迎交流。
原文鏈接：http://lgone.com/html/y2010/801.html
【編輯推薦】
