LevelDB Source Reading (4): Concurrent Access

In this thread, we come to the issue of concurrent access of LevelDB. As a database, it can be concurrently accessed by users. But, it wouldn’t be easy to provide high throughput under product load. What effort does LevelDB make to achieve this goal both in design and implementation?

Goal of Design

From this github issue, we can see LevelDB is designed for not allowing multi-process access.

this (supporting multiple processes) doesn’t seem like a good feature for LevelDB to implement.

They believe let multiple process running would be impossible to share memory/buffer/cache, which may affect the performance of LevelDB.

In the case of multiple read-only readers without altering the code base, you could simply copy the file for each reader. Yes, it will be inefficient (though not on file systems that dedupe data), but then again, so would having multiple leveldb processes running as they wouldn’t be able to share their memory/buffer/etc.

They achieve it by adding a locking file when opening the database:

// db_impl.cc DB::Open -> DBImpl::Recover
  Status s = env_->LockFile(LockFileName(dbname_), &db_lock_);
  if (!s.ok()) {
    return s;
  }

// env_posix.cc LockFile

int fd = open(fname.c_str(), O_RDWR | O_CREAT, 0644);
if (fd < 0) {
  result = IOError(fname, errno);
} else if (!locks_.Insert(fname)) {
  // check whether this db is already opened by this process
  close(fd);
  result = Status::IOError("lock " + fname, "already held by process");
} else if (LockOrUnlock(fd, true) == -1) {
  // check whether this db is already opened by other process
  result = IOError("lock " + fname, errno);
  close(fd);
  locks_.Remove(fname);
}

Implementation

Now, we understand we can only access LevelDB in multi-thread form (not in multi-process). So, we will dive into three different spheres to see how LevelDB handles multi-thread access.

Multi-thread Writers

In the LevelDB Source Reading (2): Read/Write, we have already pointed out that LevelDB will only let the first writer continue and block other if multiple thread want to write at the same time.

  MutexLock l(&mutex_);
  writers_.push_back(&w);
  while (!w.done && &w != writers_.front()) {
    w.cv.Wait();
  }

It is a common practice to use a blocking queue to handle the consumer-producer problem like this. The special part LevelDB do is use merged writer batch to accelerate the consumption of writer job.

WriteBatch* updates = BuildBatchGroup(&last_writer);

Multi-thread Readers&Writers

As Java Concurrency in Practice has said, concurrency problem arises when multiple thread share mutable resources. In order to solve concurrency problem, we can either make resources private so as to not share them – for example, copy on write technique, or make resources immutable – immutable design pattern.

Back to our LevelDB, what reader and writer share is actually only the memory table.

Immutability

LevelDB used many immutable resources to avoid using lock: Using immutable memory table (back up of memory table), immutable sorted table file to read, so no writer will change and no need of locking.

For the memory table of LevelDB, it also has some kind of immutability. This table is very much like a log, you can only append to it and read from it, but not update old value. In this way, every key/value is immutable and doesn’t need a giant lock even there exists writer trying to change this pair.

// Unlock while reading from files and memtables
{
  mutex_.Unlock();
  // First look in the memtable, then in the immutable memtable (if any).
  LookupKey lkey(key, snapshot);
  if (mem->Get(lkey, value, &s)) {
    // Done
  } else if (imm != NULL && imm->Get(lkey, value, &s)) {
    // Done
  } else {
    s = current->Get(options, lkey, value, &stats);
    have_stat_update = true;
  }
  mutex_.Lock();
}

// DBImpl::Write
mutex_.Unlock();
status = log_->AddRecord( 
        WriteBatchInternal::Contents(updates));
bool sync_error = false;
if (status.ok() && options.sync) {
  status = logfile_->Sync();
  if (!status.ok()) {
    sync_error = true;
  }
}
if (status.ok()) {
  // extract sequence and kType to insert memtable
  status = WriteBatchInternal::InsertInto(updates, mem_);
}
mutex_.Lock();

Atomic Operation

Yes, we don’t need an giant lock to lock all writing when we are trying to read from memory table, we still need some sync operations (see memory barrier for detail) to make sure reader thread seeing the latest value. Here, LevelDB use atomic operation which is always implemented by CAS primitives, which is very efficient compared with traditional lock.

The following is the code snippet that use atomic operation when reader iterates the memory table to find the key and writer updates skiplist:

Node* Next(int n) {
  assert(n >= 0);
  // Use an 'acquire load' so that we observe a fully initialized
  // version of the returned Node.
  return reinterpret_cast<Node*>(next_[n].Acquire_Load());
}

void SetNext(int n, Node* x) {
  assert(n >= 0);
  // Use a 'release store' so that anybody who reads through this
  // pointer observes a fully initialized version of the inserted node.
  next_[n].Release_Store(x);
}

Question

Does this design make it possible that one writer thread is writing a value and at the same time another reader thread can read it because part of skiplist nodes are already updated:

for (int i = 0; i < height; i++) {
  // NoBarrier_SetNext() suffices since we will add a barrier when
  // we publish a pointer to "x" in prev[i].
  x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
  prev[i]->SetNext(i, x);
}

More

• LevelDB doesn’t support traditional transaction, if you need one, you have to add one layer for it.
• LevelDB have limited support for and ACID: Writes (including batches) are atomic. Consistency is up to you. There is limited isolation support. And durability is a configurable option.

Ref

• Wikipedia: ACID
• Wikipedia: MVCC

Written with StackEdit.