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

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

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

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

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

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

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

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

圖2 LogStore設(shè)計(jì)方案

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

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

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

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

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

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

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

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

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