Hackage :: [Package]

liszt: Append only key-list database

[ bsd3, database, library, program ] [ Propose Tags ] [ Report a vulnerability ]

Please see the README on GitHub at https://github.com/fumieval/liszt#readme

[Skip to Readme]

Modules

[Last Documentation]

  • Database
    • Database.Liszt
      • Database.Liszt.Internal
      • Database.Liszt.Network
      • Database.Liszt.Tracker

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1, 0.2
Change log ChangeLog.md
Dependencies base (>=4.7 && <5), binary, bytestring, cereal, containers, cpu, deepseq, directory, exceptions, filepath, fsnotify, liszt, network, reflection, scientific, sendfile, stm, stm-delay, text, transformers, unordered-containers, vector, vector-th-unbox, winery [details]
License BSD-3-Clause
Copyright Copyright (c) 2018 Fumiaki Kinoshita
Author Fumiaki Kinoshita
Maintainer fumiexcel@gmail.com
Category Database
Home page https://github.com/fumieval/liszt#readme
Bug tracker https://github.com/fumieval/liszt/issues
Source repo head: git clone https://github.com/fumieval/liszt
Uploaded by FumiakiKinoshita at 2018-09-11T06:21:26Z
Distributions
Executables lisztd, liszt
Downloads 1134 total (5 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs not available [build log]
All reported builds failed as of 2018-09-11 [all 3 reports]

Readme for liszt-0.2

[back to package description]

Liszt

Liszt is an append-only key-list database.

Insertion

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)

Query

lisztd starts a server. The first argument is the root directory to find liszt files.

$ 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

Representation

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.

Keys, Tags, and Payloads are bytestrings with arbitrary length.

A pointer to a content with type t is denoted by P t. 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: 0x00
  • 1-leaf: 0x01 (P Key) Spine
  • 2-leaf: 0x02 (P Key) Spine (P Key) Spine
  • 2-node: 0x12 (P Node) (P Key) Spine (P Node)
  • 3-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.

  • Spine: Int [Int (P Tree)]

Tree is either

  • Tip: 0x80 Int Tag (P Payload)
  • Bin: 0x81 Int Tag (P Payload) (P Node) (P Node)

where the Int represents the length of the Tag.

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).