Hi Folks,
Today let's look into Key-Value storage library called "
LevelDB".
LevelDB is a fast key-value storage library written at Google that
provides an ordered mapping from string keys to string values. Leveldb
is based on LSM (Log-Structured Merge-Tree) and uses SSTable and
MemTable for the database implementation. It's written in C++ and
availabe under BSD license. LevelDB treats key and value as arbitrary
byte arrays and stores keys in ordered fashion. It uses snappy
compression for the data compression. Write and Read are concurrent for
the db, but write performs best with single thread whereas Read scales
with number of cores
Java package built with
JNI wrapper available for LevelDB - Stable version (Forked for further development, updates may not be reflected on public GIT, because of security Issues).
Features:
- Keys and values are arbitrary byte arrays.
- Data is stored sorted by key.
- Callers can provide a custom comparison function to override the sort order.
- The basic operations are Put(key,value), Get(key), Delete(key).
- Multiple changes can be made in one atomic batch.
- Users can create a transient snapshot to get a consistent view of data.
- Forward and backward iteration is supported over the data.
- Data is automatically compressed using the Snappy compression library.
- External
activity (file system operations etc.) is relayed through a virtual
interface so users can customize the operating system interactions.
- Detailed documentation about how to use the library is included with the source code.
Limitations:
- This is not a SQL database. It does not have a relational data
model, it does not support SQL queries, and it has no support for
indexes.
- Only a single process (possibly multi-threaded) can access a particular database at a time.
- There
is no client-server support builtin to the library. An application
that needs such support will have to wrap their own server around the
library.
Performance:
Here is a performance report (with explanations) from the run of the
included db_bench program. The results are somewhat noisy, but should
be enough to get a ballpark performance estimate.
Setup
We
use a database with a million entries. Each entry has a 16 byte key,
and a 100 byte value. Values used by the benchmark compress to about
half their original size.
LevelDB: version 1.1
Date: Sun May 1 12:11:26 2011
CPU: 4 x Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
CPUCache: 4096 KB
Keys: 16 bytes each
Values: 100 bytes each (50 bytes after compression)
Entries: 1000000
Raw Size: 110.6 MB (estimated)
File Size: 62.9 MB (estimated)
Write performance
The
"fill" benchmarks create a brand new database, in either sequential, or
random order. The "fillsync" benchmark flushes data from the operating
system to the disk after every operation; the other write operations
leave the data sitting in the operating system buffer cache for a while.
The "overwrite" benchmark does random writes that update existing keys
in the database.
fillseq : 1.765 micros/op; 62.7 MB/s
fillsync : 268.409 micros/op; 0.4 MB/s (10000 ops)
fillrandom : 2.460 micros/op; 45.0 MB/s
overwrite : 2.380 micros/op; 46.5 MB/s
Each "op" above corresponds to a write of a single
key/value pair. I.e., a random write benchmark goes at approximately
400,000 writes per second.
Each "fillsync" operation costs much
less (0.3 millisecond) than a disk seek (typically 10 milliseconds). We
suspect that this is because the hard disk itself is buffering the
update in its memory and responding before the data has been written to
the platter. This may or may not be safe based on whether or not the
hard disk has enough power to save its memory in the event of a power
failure.
Read performance
We
list the performance of reading sequentially in both the forward and
reverse direction, and also the performance of a random lookup. Note
that the database created by the benchmark is quite small. Therefore the
report characterizes the performance of leveldb when the working set
fits in memory. The cost of reading a piece of data that is not present
in the operating system buffer cache will be dominated by the one or
two disk seeks needed to fetch the data from disk. Write performance
will be mostly unaffected by whether or not the working set fits in
memory.
readrandom : 16.677 micros/op; (approximately 60,000 reads per second)
readseq : 0.476 micros/op; 232.3 MB/s
readreverse : 0.724 micros/op; 152.9 MB/s
LevelDB compacts its underlying storage data in the
background to improve read performance. The results listed above were
done immediately after a lot of random writes. The results after
compactions (which are usually triggered automatically) are better.
readrandom : 11.602 micros/op; (approximately 85,000 reads per second)
readseq : 0.423 micros/op; 261.8 MB/s
readreverse : 0.663 micros/op; 166.9 MB/s
Some of the high cost of reads comes from repeated
decompression of blocks read from disk. If we supply enough cache to
the leveldb so it can hold the uncompressed blocks in memory, the read
performance improves again:
readrandom : 9.775 micros/op; (approximately 100,000 reads per second before compaction)
readrandom : 5.215 micros/op; (approximately 190,000 reads per second after compaction)
This Article may help someone in the future.
Cheers!
Courtesy goes to "LevelDB" wikis
