Append only key-list database https://github.com/fumieval/liszt#readme
|Latest on Hackage:||0.2|
This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.
Liszt is an append-only key-list database.
For the sake of reliability, insertion is performed locally. Insertions can be batched up to one commit in order to reduce overheads.
commitFile :: FilePath -> Transaction a -> IO a insert :: Serialise a => Key -> a -> Transaction () > commitFile "foo.liszt" $ insert "message" ("hello, world" :: Text)
lisztd starts a server. The first argument is the root directory to find liszt
$ lisztd .
You can use the command line utility to watch a stream.
-b 0 follows a stream
from offset 0.
-f "%p\n" prints payloads with newlines.
$ liszt foo.liszt message -b 0 -f "%p\n" hello, world
Liszt employs a 2-3 tree (special case of B tree) of skew binary random access lists as its on-disk format.
A liszt file consists of six types of contents: keys, payloads, tags, nodes, trees, and a footer.
Payloads are bytestrings with arbitrary length.
A pointer to a content with type
t is denoted by
It’s a pair of the byte offset and the length of the content, encoded in unsigned VLQ.
A node is one of the following:
- Empty node:
0x01 (P Key) Spine
0x02 (P Key) Spine (P Key) Spine
0x12 (P Node) (P Key) Spine (P Node)
0x13 (P Node) (P Key) Spine (P Node) (P Key) Spine (P Node)
Spine is a list of pairs of:
- Rank: the number of payloads in a tree
- Pointer to a tree
Spine prefixed by the length of the list.
Int [Int (P Tree)]
Tree is either
0x80 Int Tag (P Payload)
0x81 Int Tag (P Payload) (P Node) (P Node)
where the Int represents the length of the
A footer is a root node padded to 256 bytes long, and the padding must end with the following byte sequence:
8df4 c865 fa3d 300a f3f8 9962 e049 e379 489c e4cd 2b52 a630 5584 004c 4953 5a54
(last 5 bytes is LISZT)
Committing is performed in the following steps. This append-only scheme grants robustness to some extent.
- Read the root node from the file.
- Append payloads.
- Append a new footer.
When an exception occurs in the middle, it will put the original footer to prevent corruption (TODO: find the last footer in case of corrupted file).