From 4ac513fc890c7c0b434b8488b608db1ce66454be Mon Sep 17 00:00:00 2001
From: PHO <pho@cielonegro.org>
Date: Sun, 10 Jul 2011 15:56:22 +0900
Subject: [PATCH] doc/format-and-operations.rst

---
 doc/format-and-operations.rst | 176 ++++++++++++++++++++++++++++++++++
 1 file changed, 176 insertions(+)
 create mode 100644 doc/format-and-operations.rst

diff --git a/doc/format-and-operations.rst b/doc/format-and-operations.rst
new file mode 100644
index 0000000..f9d171a
--- /dev/null
+++ b/doc/format-and-operations.rst
@@ -0,0 +1,176 @@
+Cocoli DB - File Format
+=======================
+
+::
+
+    cocoli = {
+      db-header
+    , db-state
+    , [record]
+    }
+    
+    db-header = { /* 8 octets */
+      db-magic
+    , db-version
+    }
+    db-magic   = "cocoli"
+    db-version = 0 :: Word16
+    
+    /* 21 octets */
+    db-state = clean-state
+             | writing-state
+             | compacting-state
+    
+    clean-state = {
+      0 :: Word8
+    , dummy 20 octets
+    }
+    
+    writing-state = {
+      1 :: Word8
+    , last-file-size-when-the-db-was-clean :: Word64
+    , dummy 12 octets
+    }
+    
+    compacting-state = { /* 21 octets */
+      2         :: Word8
+    , move-from :: Word64
+    , move-to   :: Word64
+    , amount    :: Word32
+    }
+    
+    record = hole | pair | necrology
+    
+    hole = { /* at a minimum of 9 octets */
+      0         :: Word8
+    , hole-size :: Word32
+    , content   :: [Word8]
+    , hole-size :: Word32
+    }
+    
+    pair = {
+      1            :: Word8
+    , pair-size    :: Word32
+    , key-size     :: Word32
+    , value-size   :: Word32
+    , key          :: [Word8]
+    , value        :: [Word8]
+    , padding      :: [Word8]
+    , pair-size    :: Word32
+    }
+    
+    necrology = {
+      2              :: Word8
+    , necrology-size :: Word32
+    , key            :: [Word8]
+    , necrology-size :: Word32
+    }
+
+
+----------
+Operations
+----------
+
+Creating DB
+~~~~~~~~~~~
+
+1. Create an empty file.
+2. Write a DB header and clean-state.
+
+
+Opening DB
+~~~~~~~~~~
+
+1. Open the DB file.
+2. See if the DB header is correct.
+3. See if the file is at least 29 octets long.
+4. Read the db-state and redo any interrupted operations.
+
+
+Inserting a pair
+~~~~~~~~~~~~~~~~
+
+1. Write the current file size to the writing-state.
+2. Write "1" to the beginning of db-state.
+3. Append a new pair to the end of file.
+4. Write "0" to the beginning of db-state.
+
+
+Removing a pair
+~~~~~~~~~~~~~~~
+
+1. Write the current file size to the writing-state.
+2. Write "1" to the beginning of db-state.
+3. Append a new necrology to the end of file.
+4. Write "0" to the beginning of db-state.
+
+
+Finding a pair
+~~~~~~~~~~~~~~
+
+1. Seek to the end of file.
+2. Find the first pair with the given key.
+
+
+Compaction
+~~~~~~~~~~
+
+1. Find the first contiguous holes from the beginning of file, turning
+   any inactive pairs and necrologies into holes at the same time.
+2. Find the first active pair from the beginning of file.
+3. If the contiguous holes is bigger than the active pair, move the
+   pair to the beginning of holes.
+4. If the contiguous holes is smaller than the active pair, move the
+   pair to the end of file, then move it again to the beginning of
+   holes.
+
+
+Moving a pair
+~~~~~~~~~~~~~
+
+1. Write move-from, move-to, and amount to the compacting-state.
+2. Write "2" to the db-state.
+3. Copy the pair to the new location, eliminating padding octets if
+   any. If the destination hole is at least 9 octets larger than the
+   pair, turn the surplus into a new hole. If the surplus isn't large
+   enough to be a hole, pad the pair to fill the surplus.
+4. Turn the original pair into a hole by writing "0" to the beginning
+   of pair.
+5. Write "0" to the db-state.
+6. If the original pair was at the end of file, truncate the file to
+   remove the hole.
+
+
+Recovering from a writing-state
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+1. Truncate the file to the size information in the writing-state.
+2. Write "0" to the db-state.
+
+
+Recovering from a compacting-state
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+1. Copy the pair to the new location as the same way as the move
+   operation. Be aware that the original pair might already be turned
+   into a hole.
+2. Turn the original pair into a hole.
+3. Write "0" to the db-state.
+4. If the original pair was at the end of file, truncate the file to
+   remove the hole.
+
+
+-----------
+Concurrency
+-----------
+
+Any operations involving db-state changes can not be performed
+simultaneously.
+
+It's possible to find a pair while inserting or removing another
+pair. But it's impossible to do the compaction in that situation,
+because the compaction process needs to tell active pairs from
+inactive ones.
+
+Finding a pair while doing the compaction is impossible, because the
+compaction process may move an active pair back and forth.
-- 
2.40.0