Understand leveldb write operation

Preface

leveldb It has always been civilized for its excellent writing performance , In this article, we will analyze leveldb The process of writing . To understand why its write performance is so good

Organize the process

leveldb A write is divided into two parts ：

1. The first step is to write the write operation to the log .
2. The second step is to apply the write operation to the in memory database .
   The purpose of writing the log first here is to ensure that the write operation is not lost .

Write type

There are two write types . The first is Put, The second is Delete. In fact, these two operations are essentially one type , because delete The operation is actually value Empty Put operation .

batch

Whether it's Put operation 、Delete Operation or batch operation , In the bottom layer, a batch Instance is the smallest execution storage unit for database operations . Let's take a look first batch The architecture of .

stay batch Each data item in is encoded in the above format . The first bit after each data item code is the type of the data item . Types include update and delete operations . After is key The length of , Data item key The content of . If it is not a delete operation , Then add value The length of ,value The content of .

Besides ,batch It also maintains a size value , This value is used to indicate the size of the data volume . This value is for all key and value The accumulation of lengths . And the extra 8 Bytes are used to store additional information about a piece of data .

key Value code

When a data item changes from batch When writing to an in memory database , Need to put key Value conversion . therefore , stay leveldb Of all internal data items key Values are specially encoded internally . This format is called internal key.

ineternal key In user key On the basis of , The tail is added 8 Bytes . Used to store the... Corresponding to this operation sequence number And type .

among , Each operation is assigned a sequence number. Every time you do it ,sequence number Add up 1.leveldb Both the update and delete operations of the are performed by append The way , Instead of directly updating the original data . So it corresponds to the same key, There will be multiple versions of data records .sequence number The maximum value represents the latest record .

Besides ,leveldb Of snapshort Is based on sequence number Realized , That is, a sequence number Represents a database version .

Merge write

leveldb An optimization is made in the face of concurrent writes . At the same time , Only one write operation is allowed to write the contents to the log and memory database . In order to reduce the log files and increase the write performance when there are many write processes “ Small write ” Merge into “ Large write ”.

The specific process is as follows ：

The first write operation to obtain the write lock

1、 The first write operation obtains the write lock .

2、 The amount of data currently written does not reach the maximum consolidation limit, and there are other write operations pending Under the circumstances . Merge other writes into itself .

3、 If the write operation has reached the upper limit or no other write operation is required pengding Under the circumstances , Write everything to the file and to the database file .

4、 Notify each merged write operation of the final write result , Release or transfer the write lock .

The flow is shown in the following figure ：

Other write operations

1、 Wait for the lock to be written or wait for the merge

2、 If it is merged, judge whether the merge is successful , If successful, wait for the write result . Otherwise, it indicates that the write operation to obtain the write lock has oversize 了 , here , Take the write lock directly from the last write operation that held the write lock and write

3、 If not merged , Continue to wait for the merge or write lock .

Atomicity

levledb Atomicity of any write operation is implemented based on logs . All contents of any write operation will be written to the log file as a record of the log .

Generally, there are two abnormal situations ：

1、 The log is not started or half written , Process exited abnormally . In this case, it is possible to store a partial write of a write operation that has been recorded in the log file , But there is still some writing that has not been recorded . In this case, after the server restarts, if you read this log and find an exception, you will choose to discard or exit directly , This ensures the atomicity of the database

2、 Log writing completed , Process exited abnormally . In this case, the log is written successfully , But the data is not persistent . After the server restarts, it passes redo The log implements data writing, thus ensuring the atomicity of the database .