borg icon indicating copy to clipboard operation
borg copied to clipboard

replacing Hashindex with memory mapped TrieOfhash

Open RonnyPfannschmidt opened this issue 4 years ago • 0 comments

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

RonnyPfannschmidt avatar Apr 11 '21 14:04 RonnyPfannschmidt