存儲效率優化實戰：從50PB到32PB

對電子郵件服務的用戶來說，郵箱容量早已不是值得關心的問題，幾乎所有主流郵件服務商都提供了容量大到很少有人能用完的服務。然而對服務商來說，盡可能降低成本，提升系統，尤其是存儲系統的使用效率總是很好的。考慮到很多用戶會收到大量包含相同內容的郵件，如相同的郵件附件，或郵件內相同的圖片，一些郵件服務商開始考慮采用去重技術將相同文件只保存一份，借此提高存儲效率。

俄羅斯最受歡迎的郵件服務商之一Mail.Ru，自行設計實現了一套郵件存儲去重系統，在不影響性能的前提下，將包含120億個郵件內嵌文件的存儲系統占用量從原本的50PB縮減至32PB。一起來看看他們的這套系統是如何實現的。

兩年前，隨著俄羅斯盧布匯率下跌，我們開始考慮縮減Mail.Ru郵件服務的硬件和托管成本。為了設法省錢，先來看看我們的郵件是由什么組成的。

索引和正文只占到總存儲量的15%，另外85%都是各種文件。因此有必要對文件（其實也就是郵件附件）進行進一步分析，并找出優化的方法。當時我們并沒有使用文件去重技術，但是估計這種技術可將存儲總量減少36%，因為很多用戶會收到相同的郵件，如網店的報價單，包含圖像等內容的社交網絡新聞郵件等。本文將介紹我們在 Albert Galimov 的監管下實現去重系統的方法。

元數據存儲

文件總量越來越多，我們需要能快速識別重復內容。一種簡單的做法是根據內容為文件生成名稱。為此我們使用了SHA-1算法，文件的原始名稱存儲在郵件內容中，因此無須擔心原始名稱的問題。

收到新郵件后，系統會先獲取該文件，計算出哈希值，然后將結果加入到郵件信息中。這是為了在發送郵件時輕松確定以后的存儲系統中，每個文件對應著具體哪封郵件而必須采取的步驟。

試試看上傳一個文件到存儲系統，然后看看相同哈希值的文件是否已經存在。這就意味著我們必須將所有文件哈希都存儲起來。就把這個存儲叫做哈希FileDB吧。

同樣的文件可以附加到不同郵件中，因此我們需要通過計數器記錄包含同一份文件的郵件數量。

每當上傳新文件，該計數器的數字會遞增。所有文件中約有40%的文件會被刪除，因此如果用戶刪除的郵件中包含已經上傳至云端的文件，計數器的數字還必須遞減。如果計數器歸零，對應的文件才會被真正刪除。

接下來我們遇到了第一個問題：有關郵件的信息（索引）存儲在一個系統中，有關文件的信息則存儲在另一個系統中。這可能會造成一個問題，例如請考慮下面的流程：

1. 系統接到刪除某封郵件的請求。
2. 系統檢查郵件索引。
3. 系統容可以看到郵件有一個附件（SHA-1）。
4. 系統發送刪除該文件的請求。
5. 因為程序崩潰，這封郵件并未實際刪除。

此時郵件依然位于系統中，但計數器的數字已經減小了“1”。當系統收到刪除該郵件的第二個請求，計數器的數字繼續減小，因此可能面臨這樣的局面：文件依然附加在某封郵件中，但計數器已經歸零了。

避免數據丟失是最基本的要求。我們不能讓用戶打開一封郵件后發現自己的附件丟了。也就是說，在磁盤上存儲一些冗余的文件也沒什么大不了的。我們只需要一種算法，能夠明確地決定計數器的“歸零”是否為正確的結果。所以我們額外建立了一個名為Magic的字段。

該算法很簡單。除了文件哈希，我們還會在郵件中存儲一個隨機生成的數字。所有上傳湖哦刪除文件的請求都需要考慮這個隨機數：對于上傳請求，會將該數字添加至Magic數的當前值中；對于刪除請求，則會從Magic數的當前值中減去這個隨機數。

因此如果所有郵件增加或減少計數器數值的操作次數是正確的，Magic數將等于“零”。否則文件不會被刪除。

用一個例子來看看。有個名為sha1的文件，被上傳了一次，郵件生成了一個隨機（Magic）數，假設等于345。

隨后收到一封包含相同文件的新郵件。該郵件生成了自己的Magic數（123）并上傳了文件。新的Magic數會與Magic數的當前值（345）相加，計數器的數字增加1。因此現在FileDB中的Magic數值為468，計數器數字為2。

用戶刪除第二封郵件后，將從Magic數的當前值（468）中減去第二封郵件的Magic數，計數器數字也減1。

先看看正常過程。用戶刪除了第一封郵件，Magic數和計數器數字都歸零。這意味著數據是一致的，可以刪除文件。

接下來，假設出錯了：第二封郵件發送了兩個刪除請求。計數器歸零意味著已經沒有郵件鏈接至該文件，但Magic數此時等于222，意味著出問題了：數據變得一致之前，文件不會被刪除。

把這種情況進一步延展一下。假設第一封郵件也被刪除了，此時Magic數（-123）依然意味著不一致。

作為一項安全措施，一旦計數器歸零但Magic數沒有歸零（本例中計數器歸零時Magic數值為222），文件將會添加“不要刪除”標簽。通過這種方法，就算在處理了一系列刪除和上傳操作，Magic數和計數器都歸零后，我們依然可以知道該文件有問題，不應刪除。

重新回到FileDB。每個項都有一組標志。無論用戶是否主動使用，實際上都用得上（例如要將文件標記為不可刪除）。

除了物理位置外，我們可以掌握文件的所有特性。物理位置是由服務器（IP）和磁盤決定的。服務器和磁盤可能個有兩組。

但每塊磁盤會存儲大量文件（我們的實例中，大約存儲了1,000,000個文件），這也意味著這些記錄可以通過FileDB中同一個磁盤對加以區分，那么也就沒必要將其存儲在FileDB中了。可以把它們放在一個單獨的表：PairDB中，隨后通過磁盤對ID鏈接至FileDB。

不言而喻，除了磁盤對ID，我們還需要一個標志字段。先提起說一下，這個字段意味著磁盤是否被鎖定（例如一個磁盤崩潰，需要從另一個進行復制，這樣新數據才不會寫入到這兩個磁盤中）。

此外還需要知道每個磁盤有多少可用空間，因此也需要相應的字段。

為了讓一切盡可能快速運行，FileDB和PairDB都必須位于內存中。我們原本使用了Tarantool 1.5，但現在應該已經在使用最新版了。FileDB有五個字段（長度分別為20、4、4、4、4字節），總長度36字節。此外每條記錄都有一個16字節的頭部，外加每字段1字節長度的指針，因此每條記錄的總長度為57字節。

Tarantool允許指定最小分配大小，因此與內存有關的開銷可以接近于零。我們會為每條記錄嚴格分配剛好夠用的內存數量。我們共有12,000,000,000個文件，因此：

(57 * 12 * 10?) / (10243) = 637 GB

但這還沒完，還需要為sha1字段提供索引，因此每條記錄的總長度需要額外增加12字節，因此：

(12 * 12 * 10?) / (10243) = 179 GB

所以我們一共需要800GB內存。但是別忘了還要復制，因此所需內存數量需要翻倍。

如果使用裝備256GB內存的服務器，這樣的機器一共需要八臺。

我們還可以評估PairDB的大小。文件的平均大小為1MB，磁盤容量平均為1TB，因此一塊硬盤平均可存儲大約1,000,000個文件，那么我們需要28,000塊硬盤。每條PairDB記錄描述了兩塊磁盤，因此PairDB包含14,000條記錄，相比FileDB實在是微不足道。

文件上傳

確定了數據庫結構后，需要考慮與系統交互的API了。首先，我們需要確定Upload和Delete方法。但是別忘了還要去重：有一定概率打算上傳的文件已經位于存儲系統中，此時就沒必要重新上傳了。因此需要具備下列方法：

• inc(sha1, magic) — 負責計數器的遞增。如果文件不存在則返回錯誤。別忘了我們還需要一個防止文件被錯誤刪除的Magic數。
• upload(sha1, magic) —將可在inc返回錯誤后調用。意味著該文件不存在，需要上傳。
• dec(sha1, magic) — 將在用戶刪除一封郵件后調用，并首先減小計數器的數字。
• GET /sha1 — 通過HTTP下載文件。

一起來深入看看上傳過程中會發生什么事。在實現該接口的守護進程中，我們選擇了IProto協議。守護進程必須能靈活縮放至任意數量的服務器，因此不能存儲狀態。假設通過Socket收到了一個請求：

通過命令名稱可以了解頭部的長度，因此我們首先讀取頭部。隨后我們需要知道origin-len文件的長度，并據此選擇要將文件上傳到的服務器。通過PairDB獲取所有記錄（幾千條）并使用標準算法查找需要的對：選擇長度與所有對的可用空間總量相等的片段，在這個片段中隨機選取一點，并選擇該點所屬的對。

然而用這種方式選擇對有一定的風險。假設所有磁盤均90%滿載，隨后添加了幾塊新磁盤。有很大可能性所有新文件會被上傳至新增的磁盤。為避免這種情況，我們不應計算磁盤對的可用空間總和，而要計算該可用空間的方根。

至此已經選擇了一個對，但我們的守護進程是流式的，如果開始將文件上傳至存儲，將沒有回頭路。也就是說，在實際開始上傳文件之前，我們會首先上傳一個很小的測試文件。如果測試文件成功上傳，則會從Socket中讀取文件內容，并將其上傳至存儲。否則會選擇另一個對。SHA-1哈希可以即時讀取，因此可在上傳的同時進行計算。

再看看從加載程序（Loader）將文件上傳至所選磁盤對的情況。在包含該這些磁盤的機器上，我們設置了Nginx并使用了WebDAV協議。郵件抵達后，FileDB還沒有相應的文件，因此需要通過加載程序上傳至磁盤對。

但這并不會妨礙到其他用戶收到相同郵件：假設有兩個收件人，需要注意，此時FileDB還沒有拿到這個文件，因此將由另一個加載程序上傳這個文件，并可能選擇上傳至同一個磁盤對。

Nginx通常會正確解決這種問題，但我們需要對整個過程進行控制，因此使用一個復雜的名稱保存該文件。

文件名中紅色部分是每個加載程序放入的隨機數。借此可確保兩個PUT方法不會重疊，進而導致上傳兩個不同的文件。一旦Nginx響應了201 (OK)信息，第一個加載程序會執行一個原子級的MOVE操作，并指定文件的最終名稱。

第二個加載程序完成文件上傳操作并執行MOVE后，文件會被覆寫，但這算不得什么大問題，因為文件始終都是那一個。文件位于磁盤上之后，會向FileDB加入一條新記錄。我們所用的Tarantool版本被分為兩個空間，我們目前只使用了space0。

然而我們并不是簡單地向FileDB新增一條記錄，而是會使用存儲過程讓文件計數器數字增加，或向FileDB添加新記錄。為什么這樣做？當加載程序確定FileDB中不存在該文件，隨后上傳文件內容并通過處理給FileDB中新增加一條記錄的全過程中，其他人可能已經上傳了該文件并添加了對應的記錄。上文的例子曾經考慮過這種問題：兩個收件人收到了同一封郵件，因此兩個加載程序開始上傳文件，一旦第二個加載程序先行上傳完成，將會通過處理向FileDB中添加新記錄。

此時第二個加載程序會讓文件計數器的數字增加。

然后再來看看dec方法。我們的系統有兩個高優先級任務：可靠地將文件寫入磁盤，以及從磁盤快速交付給客戶端。文件的物理刪除會產生一定的工作負載，導致這兩個任務變慢。因此刪除操作實際上是脫機進行的。Dec方法本身可以讓計數器減小。如果隨后計數器和Magic數都歸零，意味著已經沒人需要該文件了，因此我們會在Tarantool中將相應的記錄從space0移動至space1。

decrement (sha1, magic){
 counter--
 current_magic –= magic
 if (counter == 0 && current_magic == 0){
   move(sha1, space1)
 }
}

Valkyrie

每個存儲都使用一個Valkyrie守護進程監視數據完整性和一致性，這些工作會針對space1進行。每個磁盤有一個守護進程實例，該守護進程會對磁盤上的所有文件進行迭代，并檢查space1是否包含與特定文件對應的記錄，如果有則意味著該文件需要刪除。

但在調用dec方法并將文件移動至space1之后，Valkyrie可能需要花一些時間才能找到該文件。這意味著在兩個事件之間的時段內，文件有可能被重新上傳并重新移動回space0。

因此Valkyrie還會檢查文件是否位于space0中。如果找到了，并且對應記錄的pair_id指向運行了Valkyrie實例的磁盤對，記錄會從space1中刪除。

如果space0中未找到記錄，那么即可考慮將文件刪除。然而在向space0發送請求直到文件被物理刪除，這期間依然有一定概率遇到該文件對應的新記錄重新出現在space0的情況。此時我們會將文件隔離。

此時并不刪除文件，而是在文件名中加入“已刪除”標記和時間戳。這意味著我們會在時間戳對應的時間延后一個時間量（延后多久可由配置文件決定）后物理刪除該文件。如果程序崩潰文件被誤刪除，用戶還有機會找回文件。我們可以在不丟失任何數據的情況下恢復文件并解決這些問題。

還記得嗎，上文提到共有兩塊磁盤，每塊都運行一個Valkyrie實例。這兩個實例并不同步，因此問題來了：什么時候把記錄從space1中刪除？

我們會做兩件事。首先，對于有問題的文件，首先將一個Valkyrie實例設置為主，通過文件名的第一比特很容易做到：如果等于0，disk0是主，否則disk1是主。

然后再引入一個延遲處理。上文提到過，當記錄位于space0時，其中包含了用于檢查一致性的Magic字段。當記錄移動至space1后，并未使用該字段，因此我們用帶包記錄出現在space1中的時間設置了一個時間戳。借此主Valkyrie實例將立刻處理space1中的記錄，從實例則會根據時間戳添加一定的延遲，等待片刻再處理并刪除space1中的記錄。

這種方法帶來了另一個好處：如果主實例中的文件被錯誤地放入隔離區，只要查詢主實例的日志就能確認。同時請求該文件的客戶端可以回退（Fall Back）至從實例，用戶依然可以獲得所需的文件。

至此已經考慮過Valkyrie守護進程找到名為sha1的文件，并且該文件（可以考慮將其刪除）在space1中有對應的記錄。是否還存在其他可能的情況？

假設某個文件位于磁盤上，但FileDB中沒有相應的記錄。如果按照上述情況，主Valkyrie實例出于某種原因停止工作較長時間，就意味著從實例已經有足夠的時間將文件放入隔離區并從space1中刪除對應的記錄。此時我們也會使用sha1.deleted.timestamp將該文件放入隔離區。

另一種情況：存在一條記錄，但指向的是不同的磁盤對。這種情況可能出現在兩個收件人收到同一封郵件并進行上傳的過程中。請回憶一下上文提到的規劃。

如果第二個加載程序將該文件上傳到與第一個加載程序不同的磁盤對會怎樣？space0中計數器的數字會變大，但文件上傳到的磁盤對會包含一些垃圾文件。我們需要確保這些文件可讀取并且與sha1匹配。如果一切正常，此類文件可立刻刪除。

另外Valkyrie可能會遇到某些被放入隔離區的文件。如果隔離時間已到，該文件依然會被刪除。

接下來假設Valkyrie遇到一個正常的文件。它需要從磁盤讀取，檢查完整性并與sha1對比。隨后Valkyrie需要查詢第二個磁盤，看看是否存在相同文件。這里使用最簡單的HEAD方法就夠了：第二個磁盤運行的守護進程本身就能檢查完整性。如果第一個磁盤上的文件損壞，則會立刻從第二個磁盤上復制。如果第二個磁盤不包含該文件，則可以從第一個磁盤上復制。

還有最后一種與磁盤問題有關的情況。如果系統監視過程中發現任何磁盤出現問題，有問題的磁盤會被置于維護（只讀）模式，此時將通過第二個磁盤執行UNMOVE操作。借此可以有效地將所有文件分散在其他磁盤對的第二塊磁盤上。

結果

回到開頭處提到的問題，我們的郵件存儲系統以前是這樣的：

通過實現新的系統，存儲占用總量縮減了18PB：

現在郵件占用32PB（25%為索引，75%為文件）。由于大幅縮減了18TB，將來很長時間里都不用買新硬件了。

注：有關SHA-1

目前在SHA-1碰撞方面有幾個已知的范例。不過現有的這些碰撞范例僅針對內部的壓縮函數（SHA-1 freestart碰撞）。考慮到我們有120億個文件，出現哈希碰撞的幾率小于10^-38。

但假設真的遇到這種情況。此時在通過哈希值請求文件時，我們會檢查文件的大小和CRC32校驗值與相應郵件上傳時保存在索引中的值是否相同。毫無疑問，只有所請求的確實是當時伴隨郵件上傳的文件時，用戶才能獲得所請求的文件。

 

 

來自：http://www.infoq.com/cn/news/2017/01/Efficient-Storage-50-32-PB