LevelDB

"The Node.js of Databases"—@dominictarr

Presentation by Rod Vagg / tw:@rvagg / gh:rvagg

What?

  • Open-source, dependency-free, embedded key/value datastore
  • Developed in 2011 by Jeff Dean and Sanjay Ghemawat from Google
  • Based on ideas in Google's BigTable
  • Initially designed for Chrome

Features

  • Arbitrary byte arrays
  • Sorted by keys
  • Values are compressed with Snappy
  • Basic perations: Get(), Put(), Del(), Batch()
  • Bi-directional iterators
  • Snapshots

Basic architecture

LSM-tree

  • Writes go straight into a log
  • Log is flushed to sorted table files (SST)
  • Reads merge the log and the table files
  • Cache speeds up common reads

Basic architecture

Sorted table files (SST)

  • Limited to ~2MB each
  • Divided into 4K blocks
  • Final block is an index
  • Bloom filter used for lookups
  • Keys can have shared prefixes within blocks

Table file hierarchy

The "Level" in LevelDB

Log: Max size of 4MB then flushed into a set of Level 0 SST files
Level 0: Max of 4 SST files then one file compacted into Level 1
Level 1: Max total size of 10MB then one file compacted into Level 2
Level 2: Max total size of 100MB then one file compacted into Level 3
Level 3+: Max total size of 10 x previous level then one file compacted into next level

0 ↠ 4 SST, 1 ↠ 10M, 2 ↠ 100M, 3 ↠ 1G, 4 ↠ 10G, 5 ↠ 100G, 6 ↠ 1T, 7 ↠ 10T

Advanced features

Batch: Put and/or Del, are atomic.

Iterator: navigate forward and backward, starting and ending at any key.

Snapshot: consistent view of the whole data store. Iterators create an implicit snapshot.

LevelUP & LevelDOWN

LevelDOWN

C++ interface between Node.js and LevelDB:

  • Limited sugar
  • Async

LevelUP & LevelDOWN

LevelUP

Wrap LevelDOWN to provide a Node.js-style interface:

  • Sugar: optional args, deferred-till-open
  • Safety: less foot-gun
  • Streams!
  • JSON & other encoding types

LevelUP: Simple example

var levelup = require('levelup')

levelup('/tmp/dprk.db', function (err, db) {
  db.put('name', 'Kim Jong-un', function (err) {
    db.batch([
        { type: 'put', key: 'spouse', value: 'Ri Sol-ju' }
      , { type: 'put', key: 'dob', value: '8 January 1983' }
      , { type: 'put', key: 'occupation', value: 'Clown' }
    ], function (err) {
      db.createReadStream()
        .on('data', console.log)
        .on('close', function () {
          db.close()
        })
    })
  })
})

LevelUP: basic operations

create / open / close

levelup('/path/to/database', function (err, db) {
  /* use `db` */
})

// or

var db = levelup('/path/to/database')
// use `db`, operations are queued till `open` is complete

// close to clean up

db.close(function (err) { /* ... */ })

LevelUP: basic operations

put / delete / get

db.put('key', 'value', function (err) { /* ... */ })

db.del('key', function (err) { /* ... */ })

db.get('key', function (err, value) { /* ... */ })

LevelUP: basic operations

batch

var operations = [
    { type: 'put', key: 'Franciscus', value: 'Jorge Mario Bergoglio' }
  , { type: 'del', key: 'Benedictus XVI' }
]

db.batch(operations, function (err) { /* ... */ })

LevelUP: Streams

var rs = db.createReadStream()
rs.on('error', function (err) { /* handle err */ })
rs.on('data' , function (data) { /* data.key & data.value */ })
rs.on('close', function () { /* stream finished */ })

Options! Oh my!

db.createReadStream({
    start     : 'somewheretostart'
  , end       : 'endkey'
  , limit     : 100
  , reverse   : true
  , keys      : true // see db.createKeyStream()
  , values    : true // see db.createValueStream()
  , fillCache : false
})

LevelUP: Streams

Standard readable stream operations are also supported:

function copy (srcdb, destdb, callback) {
  srcdb.createReadStream()
    .pipe(destdb.createWriteStream())
    .on('error', callback)
    .on('close', callback)
}

Encoding

var db = levelup('/path/to/db', { valueEncoding: 'json' })

db.put(
    'dprk'
  , {
        name       : 'Kim Jong-un'
      , spouse     : 'Ri Sol-ju'
      , dob        : '8 January 1983'
      , occupation : 'Clown'
    }
  , function (err) {
      db.get('dprk', function (err, value) {
        console.log('dprk:', value)
        db.close()
      })
    }
)

keyEncoding and valueEncoding: utf8 (default), JSON, Buffer encoding types.

The End. Questions?

function variance (db, prefix, callback) {
  var n = 0, m2 = 0

  db.createReadStream({
        start : prefix + ':'
      , end   : prefix + ':\xFF'
    })
    .on('data', function (data) {
      var delta = data.value - mean
      mean += delta / ++n
      m2 = m2 + delta * delta
    })
    .on('error', callback)
    .on('close', function () {
      callback(null, m2 / (n - 1))
    })
}

Rod Vagg / tw:@rvagg / gh:rvagg

LevelUPgithub.com/rvagg/node-levelup
LevelDOWNgithub.com/rvagg/node-leveldown
Modulesgithub.com/rvagg/node-levelup/wiki/Modules
Applicationsgithub.com/rvagg/node-levelup/wiki/Applications