Key-Value存儲(chǔ)
為了實(shí)現(xiàn)高性能和高可用性，我們只允許非常簡單的鍵值數(shù)據(jù)存取。key和value可以是list和map的復(fù)雜類型，但美中不足的是只有以下的查詢是有效的：
value = store.get(key)
store.put(key, value)
store.delete(key)
這可不是解決了所有的問題，其實(shí)做了許多的取舍：
缺點(diǎn)
沒有復(fù)雜的查詢過濾器
所有的聯(lián)合查詢必須在代碼實(shí)現(xiàn)
沒有外鍵的結(jié)構(gòu)
沒有觸發(fā)器和視圖
優(yōu)點(diǎn)
只有高效的查詢可用，性能是可想像的
容易分布到集群
不管怎樣，面向服務(wù)常常不允許外鍵的結(jié)構(gòu)，并且強(qiáng)制在代碼中實(shí)現(xiàn)聯(lián)合（因?yàn)楹蛿?shù)據(jù)相關(guān)的key這個(gè)關(guān)系 在另一個(gè)服務(wù)中維護(hù)著）
使用關(guān)系型數(shù)據(jù)庫你必須要有一個(gè)緩存層用來擴(kuò)展讀操作，不過這個(gè)緩存層很典型地強(qiáng)制你使用了key-value的存儲(chǔ)系統(tǒng)
為了性能，最后不得不使用xml或者是其他不夠正規(guī)的一砣文本
使邏輯和存儲(chǔ)分離清晰（出于性能原因，SQL鼓勵(lì)將商業(yè)邏輯和存儲(chǔ)操作混在一起）
沒有對(duì)象-關(guān)系數(shù)據(jù)的丟失匹配問題
數(shù)據(jù)模型的詳細(xì)的討論將在下面給出。
系統(tǒng)架構(gòu)
代碼中的每層實(shí)現(xiàn)了簡單的put get和delete操作的接口。每一層都會(huì)負(fù)責(zé)一個(gè)方法，諸如tcp/ip網(wǎng)絡(luò)通信、序列化、版本沖突解決、內(nèi)部結(jié)點(diǎn)路由等等。例如路由層負(fù)責(zé)發(fā)起一個(gè)操作，比方說是Put，并且分發(fā)給N個(gè)存儲(chǔ)并行執(zhí)行復(fù)制，同是要捕獲所有的失敗。
圖1
保持每一層獨(dú)立意味著可以混合和匹配使用以滿足運(yùn)行中不同的需求。例如，我們可以增加一個(gè)壓縮層，將字節(jié)值的壓縮水平降低到序列化之下。同樣，在將
數(shù)據(jù)路由到分區(qū)的時(shí)候我們可以做靈活的智能路由。硬件負(fù)載均衡的http客戶端（用ruby寫的）這項(xiàng)工作可以在客戶端做（smart的客戶端），也可以
在服務(wù)端做成傻瓜式的使用。要把網(wǎng)絡(luò)層放在路由層的上面還是下面，我們需要做的是一件簡單的事情。
圖2
在上圖中“Load Bal.”是指負(fù)載均衡的硬件或者是輪循軟件負(fù)載均衡器，“Partition-aware
routing”是存儲(chǔ)的內(nèi)部路由。從傳延遲角度來看，越少的跳是件好事（因?yàn)椋牛@樣就跳得少了），從吞吐量的角度來說也是件好事（因?yàn)榭深A(yù)見的瓶頸
更少了），但是需要把路由信息放到棧頂（例如，客戶端必須是java的而且還要使用我們的庫）。最后，最右的圖中，http-rpc發(fā)送到服務(wù)的請(qǐng)求被路
由到了包含正確數(shù)據(jù)的機(jī)器（如果有的話），因此，在一個(gè)單獨(dú)的復(fù)制讀的簡單的情況下，機(jī)器必須能夠直接從本地bdb線程內(nèi)部獲取數(shù)據(jù)。
這一靈活性使得高性能的配置成為可能。在存儲(chǔ)中，磁盤的訪問是一個(gè)獨(dú)立的最大的性能沖擊，第二個(gè)是網(wǎng)絡(luò)的跳數(shù)。靠分區(qū)數(shù)據(jù)和盡可能緩存數(shù)據(jù)，可以避
免磁盤訪問。網(wǎng)絡(luò)跳數(shù)需要架構(gòu)的靈活性來消除。請(qǐng)注意在上圖中，我們可以用不同的配置文件來執(zhí)行3跳2跳和1跳的遠(yuǎn)程服務(wù)。要獲得非常高的性能，就必須路
由服務(wù)直接找到正確的服務(wù)器。
數(shù)據(jù)分區(qū)和復(fù)制
數(shù)據(jù)必須分區(qū)到一個(gè)集群的所有服務(wù)器上，使沒有任何一臺(tái)單一的服務(wù)器需要保存所有的數(shù)據(jù)集。即便數(shù)據(jù)可以在一個(gè)單獨(dú)的磁盤上存下，磁盤訪問小值數(shù)據(jù)
的時(shí)候是受尋找時(shí)候所控制，因此分區(qū)有改善緩存性能的作用，它依靠把熱的數(shù)據(jù)集分成更小的塊，能夠（希望能夠）整個(gè)地放到那個(gè)存有整個(gè)分區(qū)的服務(wù)器內(nèi)存
里。這就意味著，在集群里的機(jī)器是不可以互換的，請(qǐng)求必須被路由到保存有所請(qǐng)求的數(shù)據(jù)的機(jī)器，而不只是隨便地到某一臺(tái)可用的機(jī)器上。
同樣，因?yàn)樨?fù)載過重或者是維護(hù)原因的停機(jī)，服務(wù)器經(jīng)常會(huì)不可用。如果有S臺(tái)機(jī)器并且每臺(tái)機(jī)器一天有p的概率會(huì)獨(dú)自掛掉，因此一天里一臺(tái)機(jī)器丟失數(shù)據(jù)的概率為1 - (1 - p)s，顯然，鑒于這一事實(shí)，我們不能將數(shù)據(jù)只保存在一臺(tái)機(jī)器上，或者說，數(shù)據(jù)丟失的概率與群集中的數(shù)量成反比。
最簡單的方式來完成這件事是，將數(shù)據(jù)分成S個(gè)分區(qū)（每個(gè)機(jī)器一個(gè)），并且在R臺(tái)機(jī)器上面保存鍵為K的值的拷貝。用K這個(gè)鍵來關(guān)聯(lián)R臺(tái)機(jī)器的一種方法
是，設(shè)a=K%S，然后將這個(gè)值保存在機(jī)器a，a+1，a+2，…a+r。因此，對(duì)于任何的概率p，你都可以選擇一個(gè)合適的復(fù)制因子R，來達(dá)到一個(gè)可接受
的夠低的數(shù)據(jù)丟失的概率。
這個(gè)系統(tǒng)有個(gè)非常漂亮的特性，那就是任何人只要知道數(shù)據(jù)的key就可以計(jì)算到數(shù)據(jù)所處的位置，系統(tǒng)允許我們以peer-to-peer的方式做數(shù)據(jù)尋找，而不需要聯(lián)系一個(gè)裝有所有的key到服務(wù)器的映射信息的中央元數(shù)據(jù)服務(wù)器。
當(dāng)從集群中添加、刪除機(jī)器時(shí)（這樣說是因?yàn)槲覀冑徺I新的硬件或服務(wù)器臨時(shí)關(guān)閉），上述方法會(huì)導(dǎo)致缺點(diǎn)。在這種情況下，d會(huì)被改變，數(shù)據(jù)會(huì)在機(jī)器之間遷移。假如d不變，那負(fù)載不會(huì)平均地從原來刪除的或者是壞了的機(jī)器分布到集群中剩余的部分。
一致性哈希是一種避免這種問題的技術(shù)，我們用它來計(jì)算每個(gè)key在集群中所處的位置。使用這種技術(shù)，伏地魔有了這樣的特性，當(dāng)一臺(tái)機(jī)器掛了的時(shí)候，負(fù)載可以平均地分布到集群中剩余的機(jī)器。同樣，當(dāng)增加一臺(tái)機(jī)器給一個(gè)有S臺(tái)機(jī)器的集群時(shí)，只有1/(S+1)的機(jī)器上的值需要遷移到新機(jī)器。
為了形象化一致性哈希方法，我們可以看到，用可能出現(xiàn)的整數(shù)哈希值，這樣，環(huán)就從0開始，順著環(huán)旋轉(zhuǎn)到2^31-1。這個(gè)環(huán)被平均分成Q個(gè)分
區(qū)，Q>>S，這樣S個(gè)機(jī)器中的每個(gè)，都能分到Q/S個(gè)分區(qū)。一個(gè)key用任何一種哈希算法映射到環(huán)上，然后我們順時(shí)針看分區(qū)找到第一個(gè)唯一
的R節(jié)點(diǎn)，計(jì)算出一個(gè)負(fù)責(zé)這個(gè)key的R個(gè)所有機(jī)器的列表。下面這個(gè)圖畫出了ABCD四個(gè)機(jī)器的一個(gè)哈希環(huán)。箭頭表示key映射到哈希環(huán)，結(jié)果給出當(dāng)R為
3時(shí)對(duì)應(yīng)的保存了那個(gè)key的值的所有機(jī)器的列表。
圖3
數(shù)據(jù)格式化和查詢
在關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)被分成二維表。在這里它的等價(jià)物是“存儲(chǔ)”，如果數(shù)據(jù)不是必須成表，我們不使用字表結(jié)構(gòu)（一個(gè)值可以包括列表，以及不需要考慮嚴(yán)格的關(guān)系型的映射）。每個(gè)key都有一個(gè)唯一的存儲(chǔ)，并且每個(gè)key都最多只能有一個(gè)值。
查詢
伏地魔系統(tǒng)支持哈希表的語義，因此一個(gè)單獨(dú)的值可以一次進(jìn)行修改，同時(shí)可以按照主鍵查詢。因?yàn)榭梢酝ㄟ^主鍵來切分，這使得通過機(jī)器做分布式非常簡單。
請(qǐng)注意，雖然我們不支持一對(duì)多的關(guān)系，但我們支持把列表做為值，這樣也就完成了同樣的事情，因此存儲(chǔ)一個(gè)合理數(shù)量的有關(guān)聯(lián)的值成為可能。這相當(dāng)于一
個(gè)java.util.Map的值是一個(gè)java.util.List。在大多數(shù)情況下，這樣不規(guī)范來做是一個(gè)巨大的性能改善，因?yàn)橹恍枰粋€(gè)單獨(dú)的磁盤
尋址過程。但對(duì)于非常大的一個(gè)一對(duì)多關(guān)系（例如，而一個(gè)key映射到數(shù)千萬的value），必須保存在機(jī)器上，再通過游標(biāo)慢吞吞地過一遍，這樣子是不實(shí)際
的。這（很少見），必須將他們分成子查詢或以其他方式在應(yīng)用層處理。
查詢簡單可能是一種優(yōu)勢，因?yàn)槊總€(gè)查詢都有非常可預(yù)測的性能，很容易將服務(wù)的性能拆分成存儲(chǔ)操作的數(shù)量份，它執(zhí)行并迅速估計(jì)負(fù)載。相反，SQL查詢
往往不透明，而且執(zhí)行計(jì)劃是數(shù)據(jù)依賴的，因此很難估計(jì)一條給定的SQL在實(shí)際負(fù)載下的數(shù)據(jù)中還能很好地執(zhí)行（特別是對(duì)于一項(xiàng)新的功能，既沒有數(shù)據(jù)也沒有負(fù)
載的情況下）。
此外，有三個(gè)操作接口，使得在整個(gè)存儲(chǔ)層之上的透明層成為可能，并且在單元測試中使用模擬存儲(chǔ)，它的實(shí)現(xiàn)不過是一個(gè)HashMap的模擬。這樣可使得單元測試在特殊的容器或者是環(huán)境之外，會(huì)更加實(shí)用。
數(shù)據(jù)模型和序列化
在伏地魔系統(tǒng)中，序列化是可插拔的，因此你可以使用一個(gè)弄好的序列化方法同時(shí)也可以簡單也寫自己的。在伏地魔系統(tǒng)的最底層，數(shù)據(jù)格式是只包括key
和value的字節(jié)數(shù)組。高層次的數(shù)據(jù)格式化是每個(gè)存儲(chǔ)都設(shè)置的配置選項(xiàng)，處理字節(jié)到對(duì)象的轉(zhuǎn)變時(shí)，依靠實(shí)現(xiàn)序列化類，所有格式的數(shù)據(jù)都可支持。這樣做要
確保客戶端的字節(jié)序列正確。
通過輸入在存儲(chǔ)上的配置文件，我們可以廣泛地支持以下各種類型:
json–二進(jìn)制，類型的JSON數(shù)據(jù)模型，支持列表，地圖，日期，布爾值和各種精度數(shù)字。這是唯一的一種可以從字節(jié)<->對(duì)象和字符
串<->對(duì)象映射的序列化的類型。這就意味著，它可以和SQL相互作用（例如通過命令行客戶端）。我們當(dāng)前的產(chǎn)品設(shè)計(jì)中使用了一種有類型的、
壓縮的、結(jié)構(gòu)檢查的類Json格式；但這并沒有特殊的狀態(tài)，對(duì)于其他的應(yīng)用軟件來說，其他的序列化機(jī)制可能會(huì)更好。
字符串–只保存原生的字條串類型。對(duì)xml數(shù)據(jù)塊比較有用。
java序列化–我們的老朋友java序列化。當(dāng)你保存許多的java對(duì)象之前，請(qǐng)確認(rèn)了解java序列化所提供的兼容性保證。
protobuf–Protocol buffers是來自google的代碼生成的序列化格式，這可能是條不錯(cuò)的道，如果你不需要命令行訪問的話。
identity–這個(gè)類型有效地禁止了序列化，將返回給你確切的byte[]
字符串和identity的序列化都是相當(dāng)?shù)牟谎宰悦鳌rotocol Buffers最好的說明應(yīng)該是google來說。因此本節(jié)的剩余部分講述json背后的機(jī)制。
json序列化類型詳解
可能會(huì)有三種狀態(tài)的數(shù)據(jù)會(huì)駐留，我們希望能夠在它們之間進(jìn)行轉(zhuǎn)換：
在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，例如一個(gè)User對(duì)象；
持久性和網(wǎng)絡(luò)傳輸?shù)淖止?jié)；
文本表示：DBA在檢查特定的值和在線升級(jí)時(shí)不需要寫新的代碼是非常重要的。
SQL基本上就通過文本查詢格式化來達(dá)到標(biāo)準(zhǔn)化，程序來處理這些字符串和程序所使用的內(nèi)部數(shù)據(jù)結(jié)構(gòu)的映射關(guān)系。這是傳統(tǒng)的對(duì)象關(guān)系映射的問題。
對(duì)于存儲(chǔ)來說，json是一個(gè)優(yōu)秀的數(shù)據(jù)模型，因?yàn)樗С至怂芯幊陶Z言中的數(shù)據(jù)類型（字符串，數(shù)字，列表/數(shù)組，以及對(duì)象/哈希表）。問題在于，
它是本質(zhì)上是少結(jié)構(gòu)的。對(duì)于任何存儲(chǔ)問題最常見的情況，是有使用完全相同的格式保存的N行數(shù)據(jù)（包括有相同的列），在這種情況下，用json是一種浪費(fèi)，
因?yàn)樗恳恍卸紟в袛?shù)據(jù)的格式。同樣，我們希望能夠數(shù)據(jù)的表單聲明，避免錯(cuò)拼了列保存了臟數(shù)據(jù)。為了避免這種情況，我們要給每個(gè)存儲(chǔ)上的key和
value都分配一個(gè)結(jié)構(gòu)，這個(gè)結(jié)構(gòu)要能描述什么允許保存，以及怎么樣轉(zhuǎn)成字節(jié)和從字節(jié)轉(zhuǎn)成數(shù)據(jù)。使用如下的類型，json本身就可以指定結(jié)構(gòu)：
int8, int16, int32, int64, float32, float64,string, date, object, bytes, boolean, object, array
例如，如果我希望一個(gè)存儲(chǔ)包含字符串，我指定那個(gè)表的類型為：
"string"
請(qǐng)注意，此類型的定義本身就是有效的JSON。
JAVA代碼取到數(shù)據(jù)的時(shí)候就是字符串類型的。
如果我期望存儲(chǔ)包含一個(gè)整數(shù)列表，例如，會(huì)員ID，我可以指定類型：
["int32"]
JAVA代碼將會(huì)返回List<Integer>。
如果我期望存儲(chǔ)包含一個(gè)簡單的用戶對(duì)象，可以定義的類型：
{"fname":"string", "lname":"string", "id":"int32", "emails":["string"]}
這里JAVA代碼將返回 Map<String,Object> ，包含了每個(gè)給出的key，以及對(duì)應(yīng)的值。
下面是所有允許的類型：
| type |
storable substyles |
bytes used |
Java type |
example JSON |
example type definition |
| number |
int8, int16, int32, int64, float32, float64, date |
8, 16, 32, 64, 32, 64, 32 |
Byte, Short, Integer, Long Float, Double, Date |
1 |
“int32″ |
| string |
string, bytes |
2 + length of string or bytes |
String, byte[] |
“hello” |
“string” |
| boolean |
boolean |
1 |
Boolean |
true |
“boolean” |
| object |
object |
1 + size of contents |
Map<String,Object> |
{”key1″: 1, “key2″:”2″, “key3″:false} |
{”name”:”string”, “height”:”int16″} |
| array |
array |
size * sizeof(type) |
List<?> |
[1, 2, 3] |
["int32"] |
從這個(gè)意義上來說，類型定義是一套在標(biāo)準(zhǔn)json上的限制集，這樣能使序列化高效執(zhí)行（通過分段重復(fù)的字段，并且壓縮數(shù)字），并且允許基礎(chǔ)數(shù)據(jù)正確性檢測。
請(qǐng)注意，即使一個(gè)值可能有不同的字段，但只支持依賴存儲(chǔ)時(shí)定義的key來查詢。
為了幫助結(jié)構(gòu)的發(fā)展，這JSON實(shí)現(xiàn)了版本，允許數(shù)據(jù)的逐步遷移的結(jié)構(gòu)。數(shù)據(jù)總是以最新的結(jié)構(gòu)來寫，但是，讀的時(shí)候要可以用任何一種寫的時(shí)候用的結(jié)構(gòu)。這樣做可以在結(jié)構(gòu)遷移的時(shí)候不需要停下服務(wù)來取數(shù)據(jù)。
一致性和版本化
當(dāng)多個(gè)同步的寫到多個(gè)分布的機(jī)器（甚至是多個(gè)數(shù)據(jù)中心），數(shù)據(jù)的一致性成了一個(gè)難題。傳統(tǒng)的解決這個(gè)問題是分布式事務(wù)，但這些都是緩慢（由于很多
跳）和脆弱的，因?yàn)樗麄円笏蟹?wù)器將可用于處理。如果應(yīng)用程序運(yùn)行在多個(gè)數(shù)據(jù)中心，而跨數(shù)據(jù)中心操作的延遲將會(huì)非常地高，特別地，任何一個(gè)算法要提及
大于百分之五十的機(jī)器都能保證一致性將會(huì)非常困難。
其他的解決辦法是容忍不一致的可能性，并在讀取時(shí)解決不一致。這就是這里所探討的。
應(yīng)用程序通常只讀、修改、更新序列時(shí)，修改數(shù)據(jù)。例如，一個(gè)用戶往他的賬號(hào)里增加一個(gè)email，我們必須先搞到用戶對(duì)象，增加email，然后把
新的值寫回到db。數(shù)據(jù)庫的事務(wù)是這個(gè)問題的解決方案，但當(dāng)事務(wù)跨越多個(gè)頁面的加載時(shí)（有可能加載完也可能沒完，并且可能在指定的時(shí)間片里完成），這并不
是一個(gè)真正的選項(xiàng)。
當(dāng)所有的update不存在時(shí)，給定的key的值是一致的，所有的讀操作都將會(huì)返回一個(gè)相同的值。在只讀世界中，數(shù)據(jù)被以一致性的方法創(chuàng)建并且永不
改變。當(dāng)我們?cè)黾恿藢懖僮鳌?fù)制，會(huì)遇到問題：現(xiàn)在我們需要更新在多個(gè)機(jī)器上的多份數(shù)據(jù)，并且要讓所有的東東都保持一致。在機(jī)器故障面前，這樣做很困難，
在網(wǎng)絡(luò)分區(qū)的面前，這樣做被證明是不可能的（例如分區(qū)的情況，A和B可以互通，C和D可以互通，但是A、B與C、D并不能互通 ）。
下面有些方法，靠不同的保證和折衷性能來達(dá)到一致性：
兩步提交–這是一個(gè)鎖協(xié)議，包括在機(jī)器之間兩輪的協(xié)作。它是完全一致的，但不能兼容出錯(cuò)，而且很慢。
Paxos式的共識(shí)–這是一個(gè)在一個(gè)值上達(dá)成共識(shí)的協(xié)議，能夠更多地兼容出錯(cuò)。
讀修復(fù)–前兩種方法防止永久不一致。這種方法在寫的時(shí)候?qū)懭胨械牟灰恢掳姹荆谧x的時(shí)候檢測所有的沖突并且解決問題。這不涉及協(xié)調(diào)工作，是完全兼容出錯(cuò)的，但可能需要額外的應(yīng)用程序邏輯來解決沖突。
我們使用版本和讀修復(fù)。這有一個(gè)最好的可用性保證，和最高的性能（N次復(fù)制只需要W次的網(wǎng)絡(luò)往返寫，W可以配置成小于N的值）。兩步提交需要2N次的阻塞網(wǎng)絡(luò)往返。Paxos變化有很大不同，但相比兩步提交也差不多。
許多的細(xì)節(jié)，以下文件借自亞馬遜
這里有一些很好的寫關(guān)于這個(gè)問題的東東：
分布式系統(tǒng)中的版本
一個(gè)簡單的版本控制系統(tǒng)只是樂觀鎖定–我們保存一個(gè)唯一的計(jì)數(shù)器或者是時(shí)鐘值在每一片數(shù)據(jù)上，并且只允許更新數(shù)據(jù)的時(shí)候才能更新這個(gè)值。
在集中式的數(shù)據(jù)庫中這運(yùn)行良好，但在一個(gè)機(jī)器時(shí)好時(shí)壞、復(fù)制需要時(shí)間的分布式系統(tǒng)中，它就掛了。對(duì)于這種用法，一個(gè)單一的值不能保存足夠的寫入歷史，以便我們丟棄老的版本。考慮下面的一系列指令：
#兩個(gè)機(jī)器同時(shí)取一個(gè)相同的值
[client 1] get(1234) => {"name":"jay", "email":"jay.kreps@linkedin.com"}
[client 2] get(1234) => {"name":"jay", "email":"jay.kreps@linkedin.com"}
#1客戶端作了一次對(duì)name的修改并且put了一下
[client 1] put(1234, {"name":"jay kreps", "email":"jay.kreps@linkedin.com"})
#2客戶端作了一次對(duì)email的修改也put了一下
[client 2] put(1234, {"name":"jay", "email":"jay.kreps@yahoo.com"})
#現(xiàn)在我們有了以下的沖突版本
{"name":"jay", "email":"jay.kreps@linkedin.com"}
{"name":"jay kreps", "email":"jay.kreps@linkedin.com"}
{"name":"jay", "email":"jay.kreps@yahoo.com"}
在這個(gè)模型中，后面兩次的寫入使原值不再可用（因?yàn)槭腔谠档男薷模１M管如此，我們沒有規(guī)則來告訴服務(wù)器是要拋棄對(duì)name的修改，還是對(duì)email的修改。因此我們需要一個(gè)版本系統(tǒng)來允許我們檢測重寫和拋棄老版本內(nèi)容，同時(shí)也要能檢測沖突并且讓客戶去解決。
解決這個(gè)問題的一個(gè)答案是靠傳說中的向量時(shí)鐘版本。一個(gè)向量時(shí)鐘在每次寫機(jī)器的時(shí)候都保持一個(gè)計(jì)數(shù)器，在兩個(gè)版本沖突和一個(gè)版本成功或者是比另一個(gè)新的時(shí)候，我們能計(jì)算它。
向量時(shí)鐘是一個(gè)服務(wù)器和版本對(duì)的列表：
[1:45,2:3,5:55]
從這個(gè)版本能夠看出對(duì)那個(gè)寫的數(shù)字來說這是一臺(tái)主服務(wù)器。
對(duì)i來說v1繼承自v2，v1i > v2i。如果 v1 > v2和v1 < v2都不滿足，那么v1和v2同現(xiàn)，也就是沖突了。下面是兩個(gè)沖突的版本的例子：
[1:2,2:1]
[1:1,2:2]
我們的版本結(jié)構(gòu)定義了一個(gè)偏序，而簡單的樂觀鎖是一個(gè)全序。
路由參數(shù)
任何持久存儲(chǔ)的系統(tǒng)都需要回答的一個(gè)問題就是“我的東西存在哪里”。如果我們有一個(gè)集中的數(shù)據(jù)庫，這是一個(gè)簡單的問題，因?yàn)榇鸢缚偸?#8220;它們?cè)跀?shù)據(jù)庫
里的某個(gè)地方”。在一個(gè)鍵分離的系統(tǒng)中，可能在在多臺(tái)機(jī)器有所需要的數(shù)據(jù)。當(dāng)我們執(zhí)行讀操作的時(shí)候，我們至少需要從一臺(tái)機(jī)器去取數(shù)據(jù)，當(dāng)我們寫的時(shí)候，我
們需要寫到N個(gè)復(fù)制去。
因此，有三個(gè)參數(shù)的問題：
- N - 復(fù)制的次數(shù)
- R - 讀數(shù)據(jù)的節(jié)點(diǎn)數(shù)
- W -寫成功的分區(qū)數(shù)
請(qǐng)注意，如果R + W > N能夠保證我們“讀我們所寫”。如果w=0，那么寫操
作是不阻塞的，寫成功是沒有保障的。取操作和刪除操作既不是立即一致的，也不是孤立的。這意思是說：如果一個(gè)put/delete操作要成功，需要W個(gè)節(jié)
點(diǎn)都進(jìn)行了同樣的操作；然而，如果寫失敗了（這樣說是因?yàn)闃O少數(shù)的節(jié)點(diǎn)能夠馬上完成操作），那狀態(tài)就是不確定的了。如果一個(gè)put/delete操作成功
了，那最后這個(gè)值都會(huì)變成最終的值，但如果沒有成功的這個(gè)值將會(huì)失效。如果客戶端要確保這個(gè)狀態(tài)，必須在一次寫操作失敗后再發(fā)起一次寫操作。
持久層
持久存儲(chǔ)我們默認(rèn)使用JAVA版的BDB。MYSQL和內(nèi)存存儲(chǔ)也同樣支持。要添加一個(gè)新的持久化實(shí)現(xiàn)，你需要實(shí)現(xiàn)put\get\delete，并且要提供一個(gè)本地存儲(chǔ)的值的迭代程序。
批量計(jì)算數(shù)據(jù)支持
數(shù)據(jù)最密集的存儲(chǔ)需求之一是在我們的系統(tǒng)批量計(jì)算關(guān)于成員和內(nèi)容的數(shù)據(jù)。這份工作常常涉及到實(shí)體之間的關(guān)系（比如說有關(guān)系的用戶、相關(guān)的新聞文章等），那這樣N個(gè)實(shí)體就會(huì)增長出N2個(gè)
關(guān)系來。在LinkIn的一個(gè)實(shí)例是用戶網(wǎng)絡(luò)，如果要為所有用戶準(zhǔn)確保存會(huì)在12TB的范圍。批量數(shù)據(jù)處理通常比隨機(jī)訪問更有效率，也就意味著批量處理的
數(shù)據(jù)可以被實(shí)際系統(tǒng)簡單地訪問。Hadoop極大地?cái)U(kuò)充了這一點(diǎn)。我們正在開源伏地魔的后端持久化的東東，它支持非常高效的只讀訪，還能解建立、發(fā)布以及
管理大量的、只讀地指計(jì)算數(shù)據(jù)集等許多痛苦的事情。
處理批量計(jì)算的大多數(shù)痛苦來自于從數(shù)據(jù)倉庫或者是hadoop傳輸數(shù)據(jù)到線上系統(tǒng)的“推送”的過程。在傳統(tǒng)DB這意味著在線上機(jī)器重建新數(shù)據(jù)的索
引。做數(shù)以百萬計(jì)的insert和update操作一般不會(huì)所有都很高效地執(zhí)行，通常在一個(gè)sql數(shù)據(jù)庫里數(shù)據(jù)需要被布到一個(gè)新的表中，當(dāng)新表建立完畢，
再交換回來替換當(dāng)前數(shù)據(jù)。比數(shù)百萬計(jì)的單獨(dú)的update操作來說這樣做更好，但是，當(dāng)同時(shí)服務(wù)于真實(shí)環(huán)境時(shí)，這仍然意味著線上系統(tǒng)現(xiàn)正為新的數(shù)據(jù)集（或
者是performa）興建許多GB的索引。僅此一點(diǎn)可能需要數(shù)小時(shí)或數(shù)天，并可能會(huì)毀了實(shí)時(shí)查詢的性能。有人想搞定這個(gè)問題，通過將數(shù)據(jù)庫級(jí)別的
swap換出（比如說，有一個(gè)在線的DB和一個(gè)離線的DB，進(jìn)行交換），但這要求做許多事并且意味著你將只有一半的硬件正在使用。伏地魔依靠盡可能的離線
重建自身的索引（在hadoop之上或者其他），然后簡單地推送給線上機(jī)器并且透明地進(jìn)行交換。
參考文獻(xiàn)