doc/format-and-operations.rst
[cocoli.git] / 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.