borg
borg copied to clipboard
replacing Hashindex with memory mapped TrieOfhash
followup to #5756 with a "better" plan
this is a unstructured write-down to capture the idea for later implementation
A Trie is a prefix tree, typically used for membership testsof different lenght,
however in borg we can use them for fixed depth with a different layout
struct TrieHeader {
union {
uint32 parent_idx;
uint32 next_free_idx; // used for a free list, item 0 has the free list and
};
Struct FreeListEntry {
TrieHeader hdr;
uint32 size;
}
struct ChunkEntry {
uint32 age; uint32 size; uint32 csize;
}
struct LookupTrie {
TrieHeader hdr;
uint32 next_items[16];
};
Struct ChunkMetadataTie {
# allocates 3 blocks
# in lining those may be bad, out of band mechanism is possible
TrieHeader hdr;
Chunkentry entries[16]:
struct FileCacheTrie {
# either dynamic allocation or a better trick, needs to be determined
FileData
uint32 chunkindexes[...] # indexes of the chunk entries in the chunk trie
}
all 32 bit integers will be network byteorder