SILT存儲系統通過使用多個基本的鍵值存儲結構，每個針對不同的操作進行相應的優化：(1)鍵值的更新操作通過寫優化的存儲結構上進行。(2)大多數鍵值對存儲在存儲高效的結構中。雖然在存儲結構之外的數據很少使用高效的存儲索引，但是每個鍵的平均索引的代價是很低的。(3)SILT可以調整以應對極端情況，即查詢在***、最近的存儲結構中。SILT通過使用內存的過濾器，允許所有的查詢在1+（nbcl）flash讀取時間內完成。

[[217614]]

SILT的結構和基本存儲結構(LogStore, HashStore, SortedStore)如圖 1所示。

圖1 SILT存儲結構

LogStore對于寫操作有很高的效率，其主要用來進行PUT和DELETE操作。為了達到很高的系統性能，寫數據的結果直接添加到flash上log文件的末尾。因為這些記錄是按照相應的時間進行排序的，LogStore通過內存中的hash表以鍵和相應在log文件中的偏移對其進行映射。SILT使用cuckoo hash從而在最小內存消耗的情況下，達到很高的性能。本文中提出的部分鍵的cuckoo hash在較低的計算代價和內存消耗的情況下，占用93%的空間。相比其他兩個只讀的存儲結構，其數據存儲緊湊，LogStore必須要存儲4字節的指針。SILT因此只使用一個LogStore。

當LogStore中存儲飽和之后，LogStore將轉換成固定不變的HashStore。HashStore數據以hash表的形式存儲在flash上，其不需要內存的索引對記錄或數據進行檢索。SILT在將其合并到SortedStore之前可以使用多個HashStore。每個HashStore使用一個高效的內存過濾器過濾掉不存在的鍵。

SortedStore在flash上按一個指定的順序維護鍵值對數據，其使用一個非常簡潔的形式對索引進行變化。因為對于排序的數據進行單個更新時，其代價是非常高的，因此SILT周期性的將HashStore表的內容合并的到SortedStore中。

LogStore順序講PUT和DELETE操作寫入flash中，從而達到高的寫吞吐量。其內存的部分鍵cuckoo hash索引可以高效的實現鍵到相應log文件中位置的映射（如圖 2所示）。

LogStore使用一個基于cuckoo hash的hash表。其使用兩個函數和實現鍵值到相應的位置的映射。在新的鍵加入hash表中是，如果兩個位置中有一個是空的，則將其加入這個空的位置；否則新的鍵替換兩個位置的一個，被替換的鍵按上述過程進行迭代，直到找到其可選的位置中。

圖2 LogStore設計方案

為了使其盡可能的簡潔，hash表并不存儲整個鍵，而只是存儲鍵的一個tag。只有當查詢于相應的tag符合才繼續進行后續操作，這樣可以實現對不存在的鍵進行過濾。

雖然存儲tag可以在一定程度上節約內存的空間，但是同樣出現問題：將鍵移動到其可選的另一個位置需要事先知道其另一個hash值。但是，相應的鍵值存儲在flash中，因此在這種情況下需要進行flash讀取操作。為了解決這個問題，在相應的hash表中將其可選位置的索引作為tag。例如，如果鍵被放在位置，其另一個hash值將作為其tag存儲在位置中，反之亦然。

當LogStore中內容達到飽和時，SILT將其轉化成對于內存利用率更高的數據結構。直接對LogStore進行排序，并將其合并到SortedStore需要重寫大量的數據。另外，保留大量的LogStore會造成很高的內存消耗。因此，為了解決這個問題，SILT首先將LogStore轉化為一個不可變的HashStore。當HashStore的數量達到指定數值時，其被合并到SortedStore中(如圖 3所示)。

HashStore通過修改索引的結構，對于flash上的(key, value)進行按hash順序進行排序，可以節省大量的內存。

HashStore的過濾器非常簡單，只是將LogStore中hash表中的tag復制，并去掉相應的指針。

圖3 LogStore轉換為HashStore

SortedStore是一個靜態的鍵值存儲結構。其存儲按照flash上key的順序進行排序的鍵值(key, value)，使用基于熵編碼的trie樹進行索引，平均每個鍵消耗0.4字節進行存儲。

此外，SILT使用Flash上的排序數據(Using Sorted Data on Flash)，將大多數的鍵值保存在單個的SortedStore，但是其基于熵編碼的trie樹不允許進行插入和刪除。因此，為了將HashStore合并到SortedStore中，SILT必須重新生成SortedStore。因此，SortedStore的構建速度成為SILT整體性能的一個重要的因素。

通過排序可以很快完成的構建工作：(1)排序允許新數據的加入：新的數據通過排序，按順序合并到已排序的數據中。(2)排序的相關技術非常成熟：SILT可以使用高度優化的排序系統，如Nsort等