doc/format-and-operations.rst

   1 Cocoli DB - File Format
   2 =======================
   3
   4 ::
   5
   6     cocoli = {
   7       db-header
   8     , db-state
   9     , [record]
  10     }
  11
  12     db-header = { /* 8 octets */
  13       db-magic
  14     , db-version
  15     }
  16     db-magic   = "cocoli"
  17     db-version = 0 :: Word16
  18
  19     /* 21 octets */
  20     db-state = clean-state
  21              | writing-state
  22              | compacting-state
  23
  24     clean-state = {
  25       0 :: Word8
  26     , dummy 20 octets
  27     }
  28
  29     writing-state = {
  30       1 :: Word8
  31     , last-file-size-when-the-db-was-clean :: Word64
  32     , dummy 12 octets
  33     }
  34
  35     compacting-state = { /* 21 octets */
  36       2         :: Word8
  37     , move-from :: Word64
  38     , move-to   :: Word64
  39     , amount    :: Word32
  40     }
  41
  42     record = hole | pair | necrology
  43
  44     hole = { /* at a minimum of 9 octets */
  45       0         :: Word8
  46     , hole-size :: Word32
  47     , content   :: [Word8]
  48     , hole-size :: Word32
  49     }
  50
  51     pair = {
  52       1            :: Word8
  53     , pair-size    :: Word32
  54     , key-size     :: Word32
  55     , value-size   :: Word32
  56     , key          :: [Word8]
  57     , value        :: [Word8]
  58     , padding      :: [Word8]
  59     , pair-size    :: Word32
  60     }
  61
  62     necrology = {
  63       2              :: Word8
  64     , necrology-size :: Word32
  65     , key            :: [Word8]
  66     , necrology-size :: Word32
  67     }
  68
  69
  70 ----------
  71 Operations
  72 ----------
  73
  74 Creating DB
  75 ~~~~~~~~~~~
  76
  77 1. Create an empty file.
  78 2. Write a DB header and clean-state.
  79
  80
  81 Opening DB
  82 ~~~~~~~~~~
  83
  84 1. Open the DB file.
  85 2. See if the DB header is correct.
  86 3. See if the file is at least 29 octets long.
  87 4. Read the db-state and redo any interrupted operations.
  88
  89
  90 Inserting a pair
  91 ~~~~~~~~~~~~~~~~
  92
  93 1. Write the current file size to the writing-state.
  94 2. Write "1" to the beginning of db-state.
  95 3. Append a new pair to the end of file.
  96 4. Write "0" to the beginning of db-state.
  97
  98
  99 Removing a pair
 100 ~~~~~~~~~~~~~~~
 101
 102 1. Write the current file size to the writing-state.
 103 2. Write "1" to the beginning of db-state.
 104 3. Append a new necrology to the end of file.
 105 4. Write "0" to the beginning of db-state.
 106
 107
 108 Finding a pair
 109 ~~~~~~~~~~~~~~
 110
 111 1. Seek to the end of file.
 112 2. Find the first pair with the given key.
 113
 114
 115 Compaction
 116 ~~~~~~~~~~
 117
 118 1. Find the first contiguous holes from the beginning of file, turning
 119    any inactive pairs and necrologies into holes at the same time.
 120 2. Find the first active pair from the beginning of file.
 121 3. If the contiguous holes is bigger than the active pair, move the
 122    pair to the beginning of holes.
 123 4. If the contiguous holes is smaller than the active pair, move the
 124    pair to the end of file, then move it again to the beginning of
 125    holes.
 126
 127
 128 Moving a pair
 129 ~~~~~~~~~~~~~
 130
 131 1. Write move-from, move-to, and amount to the compacting-state.
 132 2. Write "2" to the db-state.
 133 3. Copy the pair to the new location, eliminating padding octets if
 134    any. If the destination hole is at least 9 octets larger than the
 135    pair, turn the surplus into a new hole. If the surplus isn't large
 136    enough to be a hole, pad the pair to fill the surplus.
 137 4. Turn the original pair into a hole by writing "0" to the beginning
 138    of pair.
 139 5. Write "0" to the db-state.
 140 6. If the original pair was at the end of file, truncate the file to
 141    remove the hole.
 142
 143
 144 Recovering from a writing-state
 145 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 146
 147 1. Truncate the file to the size information in the writing-state.
 148 2. Write "0" to the db-state.
 149
 150
 151 Recovering from a compacting-state
 152 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 153
 154 1. Copy the pair to the new location as the same way as the move
 155    operation. Be aware that the original pair might already be turned
 156    into a hole.
 157 2. Turn the original pair into a hole.
 158 3. Write "0" to the db-state.
 159 4. If the original pair was at the end of file, truncate the file to
 160    remove the hole.
 161
 162
 163 -----------
 164 Concurrency
 165 -----------
 166
 167 Any operations involving db-state changes can not be performed
 168 simultaneously.
 169
 170 It's possible to find a pair while inserting or removing another
 171 pair. But it's impossible to do the compaction in that situation,
 172 because the compaction process needs to tell active pairs from
 173 inactive ones.
 174
 175 Finding a pair while doing the compaction is impossible, because the
 176 compaction process may move an active pair back and forth.