skydb/sky — pull request #157 by benbjohnson (2013-11-19 15:15:17+00:00)
Title: DUPSORT

## LMDB DUPSORT Support

### Overview

This pull request converts the existing object format from a single, long, msgpack-encoded array of events to individual msgpack-encoded events by using LMDB's DUPSORT feature. Currently, the time complexity to insert new events is `O(n²)` since the entire timeline has to be retrieved, updated and reinserted whenever a new event comes in. The DUPSORT feature allows us to store each event as an individual value so we no longer need to get the entire timeline. The insertion time complexity has improved to be `O(log n)`.

Another important change is that permanent properties are not deduped on insert. This can be added as a later compaction step but the overhead to do it on every insert is too high.

### Storage Format

To be explicit, here are the changes in file format. The format is shown in JSON for clarity in these diagrams but it's stored as MessagePack internally.

Current object format (single value):

```
STATE ARRAY OF EVENTS
|-------------| |-------------------------------------------------------------------------------------|
{"name":"John"} [[1384873400, {"name":"Jane"}], [1384873477, {"age":20}, [1384875933, {"name":"John"}]]
```

New object format (multi-value):

```
TS (8b) Event Data (Msgpack)
|--------| |------------------|
1384873400 {"name":"Jane"}
1384873477 {"age":20}
1384875933 {"name":"John"}
```

Timestamps in the new format are 64-bit big endian integers stored using Sky's time format (upper 46-bits=seconds, lower 20-bits=µsec). LMDB DUPSORT sorts keys lexicographically so events automatically get sorted by timestamp since they are fixed length.

If an event is inserted with a timestamp that already exists, the existing event is retrieved from the database, the new event data merged on top, and then the event is reinserted.

/cc: @boourns @orenmazor @mkobetic @matthelm