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

[[217614]]

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

圖1 SILT存儲結(jié)構(gòu)

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

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

SortedStore在flash上按一個指定的順序維護(hù)鍵值對數(shù)據(jù)，其使用一個非常簡潔的形式對索引進(jìn)行變化。因?yàn)閷τ谂判虻臄?shù)據(jù)進(jìn)行單個更新時，其代價是非常高的，因此SILT周期性的將HashStore表的內(nèi)容合并的到SortedStore中。

LogStore順序講PUT和DELETE操作寫入flash中，從而達(dá)到高的寫吞吐量。其內(nèi)存的部分鍵cuckoo hash索引可以高效的實(shí)現(xiàn)鍵到相應(yīng)log文件中位置的映射（如圖 2所示）。

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

圖2 LogStore設(shè)計方案

為了使其盡可能的簡潔，hash表并不存儲整個鍵，而只是存儲鍵的一個tag。只有當(dāng)查詢于相應(yīng)的tag符合才繼續(xù)進(jìn)行后續(xù)操作，這樣可以實(shí)現(xiàn)對不存在的鍵進(jìn)行過濾。

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

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

HashStore通過修改索引的結(jié)構(gòu)，對于flash上的(key, value)進(jìn)行按hash順序進(jìn)行排序，可以節(jié)省大量的內(nèi)存。

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

圖3 LogStore轉(zhuǎn)換為HashStore

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

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

通過排序可以很快完成的構(gòu)建工作：(1)排序允許新數(shù)據(jù)的加入：新的數(shù)據(jù)通過排序，按順序合并到已排序的數(shù)據(jù)中。(2)排序的相關(guān)技術(shù)非常成熟：SILT可以使用高度優(yōu)化的排序系統(tǒng)，如Nsort等