SILT's multi-store design
The most common approach to build a hign performence key-value storage system uses two components:logstore and sortedstore. But in the implementation of SILT, it add a HashStore for sloving the high write amlication problem when merge logstore into sortedstore by traditional way. how to manage the sortedstore isn't key to performance, i think, just a little infulence.
In fact, SILT isn't a generic key-value store because of its keys are uniformly distributed 160bit hash value(e.g., pre-hashed key with SHA-1), but doing it fixed length as SILT have done here is so much convenient for compressing in-memory-index data, we will see later.
Append only, all data updates and inserts are written to the end of sortedstore file, and the same to delete, instead of performing a real delete operation. SILT design a new hash algorithm base on _cuckoo hashing_, make it more efficient
- Partial-Key, to make it compact, the hash table does not store the entire key in memory, but only a "tab" of the actual key. lose some accuracy and get more performance.
- move a key to its alternative bucket requires knowing its other hash value, but it is too expensive to read the key from disk, even worse, the butterfly effect. to solve this problem, the hash algorithm store the index of alternative bucket in tab, without any disk reads.
- the standar cuckoo hashing just only allows 50% occupancy, SILT improves it by increasing the associativity of the cuckoo hashing table, each bucket can use for 4 entries at the same time.
Once a LogStore is full, SILT freezes the LogStore and converts it into a more memory-efficient data structure called HashStore. HashStore is thus an on-disk cuckoo hash table which recording the key-value entries from insertion order to hash order, so the in-memory index filter isn't needed any more.
thanks to the design, merge HashStore into SortedStore is so fast, just reads HashStore in random and writes SortedStore in sequence.
SortedStore is a static key-value store on disk with very low memory overhead, is the main optimization of SILT. I have mentioned previously that the key in SILT is limited to 160bit length. considering the expensive memory overhead of position pointer of each node when representing a prefix-tree in typical way, SILT uses a compact recursive representation to elimitnate pointers
the basic idea and what the figure above illustrate may be has a little difference, because SILT have done some optimization for it. each internal node save the numbers of leaf node in its left. so the representation for a prefix-tree T having L and R as its left and right subtrees is defined as follows:
*_Repr( T ) := | L | Repr( L ) Repr( R )_*
if the current subtree is a leaf-node, Repr() retuen -1, so after recursion the figure 6(a) part must be: 3 2 1 -1 -1 -1 3 1 -1 1 -1 -1 1 -1 -1. it is easy for you to know left or right subtree from this string because the first number is the root. but how to locate the root of right subtree in this string?
define an operation, discard_subtree(T), which return the right subtree of T, at first, it work may like as follows:
def discard_subtree(T): (thead, ttail) = (T, T[1:]) if thead == -1: return ttail else: ttail = discard_subtree(ttail) * return ttail
in practice, it just return the green part and the red part was kicked out.
it attempt to get rid of the left subtree recursively, and this is wrong(focus on * mark line), once end the recursion(e.g., the first number is -1 which represents a leaf node), the discard_subtree(T) just return and do nothing any more.
we should get rid of the right subtree of the left subtree when the recursion return. so, the right way like this
def discard_subtree(T): (thead, ttail) = (T, T[1:]) if thead == -1: return ttail else: ttail = discard_subtree(ttail) ttail = discard_subtree(ttail) return ttail
Now we get the right result