What Is LevelDB


Introduction

This article will describe the most commonly used database in blockchain technology; LevelDB which is an example of a NoSQL database and stores data as key-value. It keeps the data in the different levels that's why it is named LevelDB. LevelDB was developed by Jeff Dean and Sanjay Ghemawat at Google as an open source database inspired by the design scheme of BigTable tablet.

What is LevelDB?

Heavyweight applications need stand-alone databases such as Oracle, MS SQL, MariaDB, Postgres, and so on. However, small apps which are portable and don’t need to host a server-side API to store their state is benefited by using a file-based database for instance SQLite. LevelDB is a light database and file-based database system as well as it is an example of a NoSQL database. NoSQL database doesn’t store data in a common relational database. It stores data in files in a different format, for example, key-value, structured markup document, etc.

According to Wikipedia LevelDB is described as “an open-source on-disk key-value store”. LevelDB fast stores the data in key-value on disk. LevelDB uses keys and values for users based on which you can store and retrieve data. So, it is a type of NoSQL database. LevelDB was built by two googlers Jeff Dean and Sanjay Ghemawat who were inspired by the BigTable.

  • Supports mapping from key to the corresponding value. Key and value are managed as adjacent string sequences in SSTable.
  • The key values are not just string it can be any byte array with arbitrary length. So, you can use encoded and non-encoded data.
  • It supports fundamental operation, Get (), Put (), and Delete () as like others.
  • We can run multiple operations at a time in a single call without any interruption.

Data Storage

It temporarily keeps the data into MemTable and periodically transfers data from MemTable to SSTable (Sorted String Table). SSTable is immutable so, the LevelDB data are immutable. Most of the blockchain technology uses a LevelDB database so blockchain transactions are immutable for example Stratis, Etherum, Neo, and so on. Additionally, LevelDB compacts to minimize the invalid data in each level and then generates one new block at the next level.

In LevelDB, immutable data are stored in a disk, and this can be shared by different clustered nodes. Overall, there are a total of 7 levels to keep data as well as at most two in-memory tables. Firstly, the system buffer writes the data into an in-memory table called MemTable when this MemTable becomes full it flushes data to disk. Every 7 levels contain multiple tables called as SSTable. In LevelDb, the down-level maintains a larger capacity than the upper level. When the upper level becomes full, the system pushes the data to the down level, down level reads and writes data into multiple SSTable.

SSTable

Sorted String Table is a file of key-value string pairs which is sorted by keys. SSTable provides an immutable mapping of keys to values where operations are provided to lookup value associated with a specific key and the operation iterate over all key-value pairs in a specific key range. SSTable contains a sequence of blocks where each block is 64 KB; however, this is configurable.

Sample Query of LevelDB

Creating LevelDB Database

When you create a new leveldb database, the database name corresponds to a directory on the system and stores all files inside this particular directory.

var options = new Options { CreateIfMissing = true };
var db = new DB(options, @"C:\temp\tempsampleleveldb");

The above code creates the database if not found in the folder location: “C:\temp\tempsampleleveldb” and opens a connection to a new DB.

Database close

db.Close();// Close the connection

LevelDB supports Get, Put and Delete methods to read, update and delete data. Below are examples of those methods.

const string key=”London”;
// Put the value in the key to update the key value
keyValue.Put(key, "Kathmandu");

// Read and Print out the value
var keyValue = db.Get(key);
Console.WriteLine(keyValue); 

// Delete the key
db.Delete(key);

Similarly, we can perform atomic updates, synchronous writes, forward and backward iteration. LevelDB is open source you can check for details in the git repository and documentation which is in C++. For .NET you can check  leveldb.net as well.

Limitations

LevelDB doesn’t support,

  • SQL query
  • Indexes
  • Store procedure
  • Joins
  • Views

LevelDB Attributes

Here are some more attributes of LevelDB from official documentation.

Checkpoints Blocking - When operation logging file exceeds over the limit, it will do checkpoints. Data will be flushed to the disk. And compaction scheme will be called. So data will go down levels. Aside from that, leveldb will generate new logging file and memtable for new use.

Compression: Naïve (Record-Level)

Concurrency Control: Two-Phase Locking (Deadlock Prevention)

Leveldb only allow one process to open at one time. The operation system will use the locking scheme to prevent concurrent access. Within one process, Leveldb can be accessed by multiple threads. For multi-writers, it will only allow the first writer to write to database and other writers will be blocked. For read-write conflicts, readers can retrieve data from immutable which is seperated from writing process. The updated version will come into effect in compaction process.

Indexes: Skip List Log-Structured Merge Tree

It uses skip list in MemTable. Aside from that, LSM-tree is one type of write-optimized B-tree variants consisting of key-value pairs. The LSM-tree is a persistent key-value store optimized for insertions and deletions. LevelDB is an open source LSM-tree implementation.

Isolation Levels: Snapshot Isolation

It saves the state of database at a given point and supports reference to it. Users can retrieve data from specific snapshot at the time the snapshot was created.

Logging: Logical Logging

Before every insertion, update or delete, system need to add the message to log. In case of node's failure, uncommited messages can be retrieved and do operation again for recovery.

Query Interface: Custom API

Keys and values in leveldb are byte arrays with arbitrary length. It supports basic operations like Put(), Get(), Delete(). It also support Batch operations: Batch(). The whole process of operations will run together and return result in a single Batch operation. However, it does not support SQL queries because this is not a SQL type database. Aside from that, it has no support for indexing.

Storage Architecture: Disk-oriented

It puts temporarily accessed data into MemTable and periodically moves data from MemTable into Immutable SSTable. Aside from that, it adopts compaction to reduce the invalid data in each level and then generates one new block at the next level. It uses mmap or native read syscall to read SSTable for querying. The OS caches SSTable for LevelDB. As LevelDB supports using snappy to compress the value, to avoid uncompress data for each query, it introduces Cache.

Storage Model: N-ary Storage Model (Row/Record)

SSTable uses NSM to arrange data. It contains a set of arbitrary, sorted key-value pairs. At the end of the block, it provides the start offset and key value for each block. So bloom filter can be used to search for target block.

System Architecture: Embedded

In leveldb immutable are stored on the disk which can be shared by different cluster nodes. There are totally 7 levels plus at most two in-memory tables. The procedure can be described as firstly the system buffers write operations in an in-memory table called MEMTable and flushes data to disk when it becomes full. On the disk, tables are organized into levels. Each level contains multiple tables called SSTable. The down level maintains larger capacity than the upper level. When the upper level is full, the system needs to push data to the down level, which might need to read and write multiple SSTables.

Summary

In short, the article described an immutable filesystem database; LevelDB which is a kind of NoSQL database. Moreover, in this article, we have learned how does LevelDB store the data and its limitations.

References


Similar Articles