Skip to content

krestenkrab/hanoidb

master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
June 14, 2012 18:04
src
March 23, 2016 15:25
March 23, 2016 15:25
July 17, 2012 16:57
July 24, 2012 10:40
March 23, 2016 15:25
April 24, 2012 10:37
November 28, 2014 16:22
May 11, 2012 12:33
March 23, 2016 15:25

HanoiDB Indexed Key/Value Storage

Build Status

HanoiDB implements an indexed, key/value storage engine. The primary index is a log-structured merge tree (LSM-BTree) implemented using "doubling sizes" persistent ordered sets of key/value pairs, similar is some regards to LevelDB. HanoiDB includes a visualizer which when used to watch a living database resembles the "Towers of Hanoi" puzzle game, which inspired the name of this database.

Features

  • Insert, Delete and Read all have worst case O(log2(N)) latency.
  • Incremental space reclaimation: The cost of evicting stale key/values is amortized into insertion
    • you don't need a separate eviction thread to keep memory use low
    • you don't need to schedule merges to happen at off-peak hours
  • Operations-friendly "append-only" storage
    • allows you to backup live system
    • crash-recovery is very fast and the logic is straight forward
    • all data subject to CRC32 checksums
    • data can be compressed on disk to save space
  • Efficient range queries
    • Riak secondary indexing
    • Fast key and bucket listing
  • Uses bloom filters to avoid unnecessary lookups on disk
  • Time-based expiry of data
    • configure the database to expire data older than n seconds
    • specify a lifetime in seconds for any particular key/value pair
  • Efficient resource utilization
    • doesn't store all keys in memory
    • uses a modest number of file descriptors proportional to the number of levels
    • I/O is generally balanced between random and sequential
    • low CPU overhead
  • ~2000 lines of pure Erlang code in src/*.erl

HanoiDB is developed by Trifork, a Riak expert solutions provider, and Basho Technologies, makers of Riak. HanoiDB can be used in Riak via the riak_kv_tower_backend repository.

Configuration options

Put these values in your app.config in the hanoidb section

 {hanoidb, [
          {data_root, "./data/hanoidb"},

          %% Enable/disable on-disk compression.
          %%
          {compress, none | gzip},

          %% Expire (automatically delete) entries after N seconds.
          %% When this value is 0 (zero), entries never expire.
          %%
          {expiry_secs, 0},

          %% Sync strategy `none' only syncs every time the
          %% nursery runs full, which is currently hard coded
          %% to be evert 256 inserts or deletes.
          %%
          %% Sync strategy `sync' will sync the nursery log
          %% for every insert or delete operation.
          %%
          {sync_strategy, none | sync | {seconds, N}},

          %% The page size is a minimum page size, when a page fills
          %% up to beyond this size, it is written to disk.
          %% Compression applies to such units of page size.
          %%
          {page_size, 8192},

          %% Read/write buffer sizes apply to merge processes.
          %% A merge process has two read buffers and a write
          %% buffer, and there is a merge process *per level* in
          %% the database.
          %%
          {write_buffer_size, 524288},  % 512kB
          {read_buffer_size, 524288},  % 512kB

          %% The merge strategy is one of `fast' or `predictable'.
          %% Both have same log2(N) worst case, but `fast' is
          %% sometimes faster; yielding latency fluctuations.
          %%
          {merge_strategy, fast | predictable},

          %% "Level0" files has 2^N KVs in it, defaulting to 1024.
          %% If the database is to contain very small KVs, this is
          %% likely too small, and will result in many unnecessary
          %% file operations.  (Subsequent levels double in size).
          {top_level, 10}  % 1024 Key/Values
         ]},

Contributors

  • Kresten Krab Thorup @krestenkrab
  • Greg Burd @gburd
  • Jesper Louis Andersen @jlouis
  • Steve Vinoski @vinoski
  • Erik Søe Sørensen, @eriksoe
  • Yamamoto Takashi @yamt
  • Joseph Wayne Norton @norton

About

Erlang LSM BTree Storage

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published