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