LevelDB 代碼擼起來！

LevelDB 的大致原理已經(jīng)講完了，本節(jié)我們要親自使用 Java 語言第三方庫 leveldbjni 來實(shí)踐一下 LevelDB 的各種特性。這個(gè)庫使用了 Java Native Interface 計(jì)數(shù)將 C++ 實(shí)現(xiàn)的 LevelDB 包裝成了 Java 平臺(tái) 的 API。其它語言同樣也是采用了類似 JNI 的技術(shù)來包裝的 LevelDB。

Maven 依賴

下載下面的依賴包地址，你就可以得到一個(gè)支持全平臺(tái)的 jar 包。LevelDB 在不同的操作系統(tǒng)平臺(tái)會(huì)編譯出不同的動(dòng)態(tài)鏈接庫形式，這個(gè) jar 包將所有平臺(tái)的動(dòng)態(tài)鏈接庫都包含進(jìn)來了。

<dependencies>
  <dependency>
    <groupId>org.fusesource.leveldbjni</groupId>
    <artifactId>leveldbjni-linux64</artifactId>
    <version>1.8</version>
  </dependency>
</dependencies>

增查刪 API

這個(gè)例子中我們將自動(dòng)創(chuàng)建一個(gè) LevelDB 數(shù)據(jù)庫，然后往里面塞入 100w 條數(shù)據(jù)，再取出來，再刪掉所有數(shù)據(jù)。這個(gè)例子在我的 Mac 上會(huì)運(yùn)行了大約 10s 的時(shí)間。也就是說讀寫平均 QPS 高達(dá) 30w/s，完全可以媲美 Redis，不過這大概也是因?yàn)殒I值對(duì)都比較小，在實(shí)際生產(chǎn)環(huán)境中性能應(yīng)該沒有這么高，它至少應(yīng)該比 Redis 稍慢一些。

import static org.fusesource.leveldbjni.JniDBFactory.factory;

import java.io.File;
import java.io.IOException;

import org.iq80.leveldb.DB;
import org.iq80.leveldb.Options;

public class Sample {

    public static void main(String[] args) throws IOException {
        Options options = new Options();
        options.createIfMissing(true);
        DB db = factory.open(new File("/tmp/lvltest"), options);
        try {
            for (int i = 0; i < 1000000; i++) {
                byte[] key = new String("key" + i).getBytes();
                byte[] value = new String("value" + i).getBytes();
                db.put(key, value);
            }
            for (int i = 0; i < 1000000; i++) {
                byte[] key = new String("key" + i).getBytes();
                byte[] value = db.get(key);
                String targetValue = "value" + i;
                if (!new String(value).equals(targetValue)) {
                    System.out.println("something wrong!");
                }
            }
            for (int i = 0; i < 1000000; i++) {
                byte[] key = new String("key" + i).getBytes();
                db.delete(key);
            }
        } finally {
            db.close();
        }
    }
}

我們?cè)儆^察數(shù)據(jù)庫的目錄中，LevelDB 都創(chuàng)建了那些東西

這個(gè)目錄里我們看到了有很多 sst 擴(kuò)展名的文件，它就是 LevelDB 的磁盤數(shù)據(jù)文件，有些 LevelDB 的版本數(shù)據(jù)文件的擴(kuò)展名是 ldb，不過內(nèi)部格式一樣，僅僅是擴(kuò)展名不同而已。其中還有一個(gè) log 擴(kuò)展名的文件，這就是操作日志文件，記錄了最近一段時(shí)間的操作日志。其它幾個(gè)大些名稱文件我們先不必去了解，后續(xù)我們?cè)僮屑?xì)解釋。

將這個(gè)目錄里面的文件全部刪掉，這個(gè)庫就徹底清空了。

也許你會(huì)想到上面的例子中不是所有的數(shù)據(jù)最終都被刪除了么，怎么還會(huì)有如此多的 sst 數(shù)據(jù)文件呢？這是因?yàn)?LevelDB 的刪除操作并不是真的立即刪除鍵值對(duì)，而是將刪除操作轉(zhuǎn)換成了更新操作寫進(jìn)去了一個(gè)特殊的鍵值對(duì)，這個(gè)鍵值對(duì)的值部分是一個(gè)特殊的刪除標(biāo)記。

待 LevelDB 在某種條件下觸發(fā)數(shù)據(jù)合并（compact）時(shí)才會(huì)真的刪除相應(yīng)的鍵值對(duì)。

數(shù)據(jù)合并

LevelDB 提供了數(shù)據(jù)合并的手動(dòng)調(diào)用 API，下面我們手動(dòng)整理一下，看看整理后會(huì)發(fā)生什么

public void compactRange(byte[] begin, byte[] end)

這個(gè) API 可以選擇范圍進(jìn)行整理，如果 begin 參數(shù)為 null，那就表示從頭開始，如果 end 參數(shù)為 null，那就表示一直到尾部。

public static void main(String[] args) throws IOException {
    Options options = new Options();
    options.createIfMissing(true);
    DB db = factory.open(new File("/tmp/lvltest"), options);
    try {
        db.compactRange(null, null);
    } finally {
        db.close();
    }
}

運(yùn)行了大約 1s 多點(diǎn)時(shí)間，完畢后我們看到目錄中 sst 文件沒有了

如果我們沒有手工調(diào)用數(shù)據(jù)整理 API，LevelDB 內(nèi)部也有一定的策略來定期整理。

讀性能

如果我們將上面的代碼加上時(shí)間打點(diǎn)，觀察讀寫性能差異，你會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象，那就是寫性能比讀性能還要好，雖然本例中所有的讀操作都是命中的。

put: 3150ms
get: 4128ms
delete: 1983ms

這是因?yàn)閷懖僮饔浲瓴僮魅罩緦?shù)據(jù)寫進(jìn)內(nèi)存后就返回了，而讀操作有可能內(nèi)存讀 miss，然后要去磁盤讀。之所以讀寫性能差距不是非常明顯，是因?yàn)?LevelDB 會(huì)緩存最近一次讀取的數(shù)據(jù)塊，而且我的個(gè)人電腦的磁盤是 SSD 磁盤，讀性能都好。如果是普通磁盤，就會(huì)看出明顯的性能差異了。

下面我們將讀操作改成隨機(jī)讀，就會(huì)發(fā)現(xiàn)讀寫性能發(fā)生很大的差別

for (int i = 0; i < 1000000; i++) {
    int index = ThreadLocalRandom.current().nextInt(1000000);
    byte[] key = new String("key" + index).getBytes();
    db.get(key);
}

--------
put: 3094ms
get: 9781ms
delete: 1969ms

這時(shí)要改善讀性能就可以借助塊緩存了

// 設(shè)置 100M 的塊緩存
options.cacheSize(100 * 1024 * 1024);

------------
put: 2877ms
get: 4758ms
delete: 1981ms

同步 vs 異步

上一節(jié)我們提到 LevelDB 還提供了同步寫的 API，確保操作日志落地后才 put 方法才返回。它的性能會(huì)明顯弱于普通寫操作，下面我們來對(duì)比一下兩者的性能差異。

public static void main(String[] args) throws IOException {
    long start = System.currentTimeMillis();
    Options options = new Options();
    options.createIfMissing(true);
    DB db = factory.open(new File("/tmp/lvltest"), options);
    try {
        for (int i = 0; i < 1000000; i++) {
            byte[] key = new String("key" + i).getBytes();
            byte[] value = new String("value" + i).getBytes();
            WriteOptions wo = new WriteOptions();
            wo.sync(true);
            db.put(key, value, wo);
        }
    } finally {
        db.close();
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);
}

上面這個(gè)同步寫操作足足花了 90s 多的時(shí)間。將 sync 選項(xiàng)去掉后，只需要 3s 多點(diǎn)。性能差距高達(dá) 30 倍。下面我們來簡單改造一下上面的代碼，讓它變成間隔同步寫，也就是每隔 N 個(gè)寫操作同步一次，取 N = 100。

WriteOptions wo = new WriteOptions();
wo.sync(i % 100 == 0);

運(yùn)行時(shí)間變成了不到 5s。再將 N 改成 10，運(yùn)行時(shí)間變成了不到 12s。即使是 12s，寫的平均 QPS 也高達(dá) 8w/s，這還是很客觀的。

普通寫 VS 批量寫

LevelDB 提供了批量寫操作，它會(huì)不會(huì)類似于 Redis 的管道可以加快指令的運(yùn)行呢，下面我們來嘗試使用 WriteBatch，對(duì)比一下普通的寫操作，看看性能差距有多大。

public static void main(String[] args) throws IOException {
    long start = System.currentTimeMillis();
    Options options = new Options();
    options.createIfMissing(true);
    DB db = factory.open(new File("/tmp/lvltest"), options);
    try {
        WriteBatch batch = db.createWriteBatch();
        for (int i = 0; i < 1000000; i++) {
            byte[] key = new String("key" + i).getBytes();
            byte[] value = new String("value" + i).getBytes();
            batch.put(key, value);
            if (i % 100 == 0) {
                db.write(batch);
                batch.close();
                batch = db.createWriteBatch();
            }
        }
        db.write(batch);
        batch.close();
    } finally {
        db.close();
    }

 long end = System.currentTimeMillis();
    System.out.println(end - start);
}

將批次數(shù)量 N 分別改成 10、100、1000，運(yùn)行后可以發(fā)現(xiàn)耗時(shí)差不多，大約都是 2s 多點(diǎn)。這意味著批量寫并不會(huì)大幅提升寫操作的吞吐量。但是將 N 改成 1 后你會(huì)發(fā)現(xiàn)耗時(shí)和普通寫操作相差無幾，大約是 3s 多，再將 N 改成 2、5 等，耗時(shí)還是會(huì)有所降低，到 2s 多 左右就穩(wěn)定了，此時(shí)提升 N 值不再有明顯效果。這意味著批量寫操作確實(shí)會(huì)比普通寫快一點(diǎn)，但是相差也不會(huì)過大。它不同于 Redis 的管道可以大幅減少網(wǎng)絡(luò)開銷帶來的明顯性能提升，LevelDB 是純內(nèi)存數(shù)據(jù)庫，根本談不上網(wǎng)絡(luò)開銷。

那為什么批量寫還是會(huì)比普通寫快一點(diǎn)呢？要回答這個(gè)問題就需要追蹤 LevelDB 的源碼，還在這部分邏輯比較簡單，大家應(yīng)該都可以理解，所以這里就直接貼出來了。

Status DB::Put(WriteOptions& opt, Slice& key, Slice& value) {
  WriteBatch batch;
  batch.Put(key, value);
  return Write(opt, &batch);
}

很明顯，每一個(gè)普通寫操作最終都會(huì)被轉(zhuǎn)換成一個(gè)批量寫操作，只不過 N=1 。這正好解釋了為什么當(dāng) N=1 時(shí)批量寫操作和普通寫操作相差無幾。

我們?cè)倮^續(xù)追蹤 WriteBatch 的源碼我發(fā)現(xiàn)每一個(gè)批量寫操作都需要使用互斥鎖。當(dāng)批次 N 值比較大時(shí)，相當(dāng)于加鎖的平均次數(shù)減少了，于是整體性能就提升了。但是也不會(huì)提升太多，因?yàn)榧渔i本身的損耗占比開銷也不是特別大。這也意味著在多線程場合，寫操作性能會(huì)下降，因?yàn)殒i之間的競爭將導(dǎo)致內(nèi)耗增加。

為什么說批量寫可以保證內(nèi)部一系列操作的原子性呢，就是因?yàn)檫@個(gè)互斥鎖的保護(hù)讓寫操作單線程化了。因?yàn)檫@個(gè)粗粒度鎖的存在，LevelDB 寫操作的性能被大大限制了。這也成了后來居上的 RocksDB 重點(diǎn)優(yōu)化的方向。

快照和遍歷

LevelDB 提供了快照讀功能可以保證同一個(gè)快照內(nèi)同一個(gè) Key 讀到的數(shù)據(jù)保持一致，避免「不可重復(fù)讀」的發(fā)生。下面我們使用快照來嘗試一下遍歷操作，在遍歷的過程中順便還修改對(duì)應(yīng) Key 的值，看看快照讀是否可以隔離寫操作。

public static void main(String[] args) throws IOException {
    Options options = new Options();
    options.createIfMissing(true);
    DB db = factory.open(new File("/tmp/lvltest"), options);
    try {
        for (int i = 0; i < 10000; i++) {
            String padding = String.format("%04d", i);
            byte[] key = new String("key" + padding).getBytes();
            byte[] value = new String("value" + padding).getBytes();
            db.put(key, value);
        }

        Snapshot ss = db.getSnapshot();
        // 掃描
        scan(db, ss);
        // 修改
        for (int i = 0; i < 10000; i++) {
            String padding = String.format("%04d", i);
            byte[] key = new String("key" + padding).getBytes();
            byte[] value = new String("!value" + padding).getBytes(); // 修改
            db.put(key, value);
        }
        // 再掃描
        scan(db, ss);
        ss.close();
    } finally {
        db.close();
    }
}

private static void scan(DB db, Snapshot ss) throws IOException {
    ReadOptions ro = new ReadOptions();
    ro.snapshot(ss);
    DBIterator it = db.iterator(ro);
    int k = 0;
    // it.seek(someKey); // 從指定位置開始遍歷
    it.seekToFirst(); // 從頭開始遍歷
    while (it.hasNext()) {
        Entry<byte[], byte[]> entry = it.next();
        String key = new String(entry.getKey());
        String value = new String(entry.getValue());
        String padding = String.format("%04d", k);
        String targetKey = new String("key" + padding);
        String targetVal = new String("value" + padding);
        if (!targetKey.equals(key) || !targetVal.equals(value)) {
            System.out.printf("something wrong");
        }
        k++;
    }

    System.out.printf("total %d\n", k);
    it.close();
}
--------------------
total 10000
total 10000

前后兩次遍歷從快照中獲取到的數(shù)據(jù)還是一致的，也就是說中間的寫操作根本沒有影響到快照的狀態(tài)，這就是我們想要的結(jié)果。那快照的原理是什么呢？

快照的原理其實(shí)非常簡單，簡單到讓人懷疑人生。對(duì)于庫中的每一個(gè)鍵值對(duì)，它會(huì)因?yàn)樾薷牟僮鞫嬖诙鄠€(gè)值的版本。在數(shù)據(jù)庫文件內(nèi)容合并之前，同一個(gè) Key 可能會(huì)存在于多個(gè)文件中，每個(gè)文件中的值版本不一樣。這個(gè)版本號(hào)是由數(shù)據(jù)庫唯一的全局自增計(jì)數(shù)值標(biāo)記的。快照會(huì)記錄當(dāng)前的計(jì)數(shù)值，在當(dāng)前快照里讀取的數(shù)據(jù)都需要和快照的計(jì)數(shù)值比對(duì)，只有小于這個(gè)計(jì)數(shù)值才是有效的數(shù)據(jù)版本。

既然同一個(gè) Key 存在多個(gè)版本的數(shù)據(jù)，對(duì)于同一個(gè) Key，遍歷操作是如何避免重復(fù)的呢？關(guān)于這個(gè)問題我們后續(xù)再深入探討。

布隆過濾器

leveldbjni 沒有封裝 LevelDB 提供的布隆過濾器功能。所以為了嘗試布隆過濾器的效果，我們需要試試其它語言，這里我使用 Go 語言的 levigo 庫。

// 安裝 leveldb和snappy庫
$ brew install leveldb
// 再安裝 levigo
$ go get github.com/jmhodges/levigo

這個(gè)例子中我們將寫入更多的數(shù)據(jù) —— 1000w 條，當(dāng)數(shù)據(jù)量增多時(shí)，LevelDB 將形成更深的層級(jí)。同時(shí)為了構(gòu)造出讀 miss 的效果，我們寫入偶數(shù)的鍵值對(duì)，然后再隨機(jī)讀取奇數(shù)的鍵值對(duì)。再對(duì)比增加布隆過濾器前后的讀性能差異。

package main

import (
    "fmt"
    "math/rand"
    "time"

    "github.com/jmhodges/levigo"
)

func main() {
    options := levigo.NewOptions()
    options.SetCreateIfMissing(true)
    // 每個(gè) key 占用 10個(gè)bit
    // options.SetFilterPolicy(levigo.NewBloomFilter(10))

    db, _ := levigo.Open("/tmp/lvltest", options)
    start := time.Now().UnixNano()
    for i := 0; i < 10000000; i++ {
        key := []byte(fmt.Sprintf("key%d", i*2))
        value := []byte(fmt.Sprintf("value%d", i*2))
        wo := levigo.NewWriteOptions()
        db.Put(wo, key, value)
    }
    duration := time.Now().UnixNano() - start
    fmt.Println("put:", duration/1e6, "ms")
    start = time.Now().UnixNano()
    for i := 0; i < 10000000; i++ {
        index := rand.Intn(10000000)
        key := []byte(fmt.Sprintf("key%d", index*2+1))
        ro := levigo.NewReadOptions()
        db.Get(ro, key)
    }
    duration = time.Now().UnixNano() - start
    fmt.Println("get:", duration/1e6, "ms")
    start = time.Now().UnixNano()
    for i := 0; i < 10000000; i++ {
        key := []byte(fmt.Sprintf("key%d", i*2))
        wo := levigo.NewWriteOptions()
        db.Delete(wo, key)
    }
    duration = time.Now().UnixNano() - start
    fmt.Println("get:", duration/1e6, "ms")
}

-----------
put: 61054ms
get: 104942ms
get: 47269ms

再去掉注釋，打開布隆過濾器，觀察結(jié)果

put: 57653ms
get: 36895ms
get: 57554ms

可以明顯看出，讀性能提升了 3 倍，這是一個(gè)非常了不起的性能提升。在讀 miss 開啟了布隆過濾器的情況下，我們?cè)僭囋嚧蜷_塊緩存，看看是否還能再繼續(xù)提升讀性能

put: 57022ms
get: 37475ms
get: 58999ms

結(jié)論是在讀 miss 開啟了布隆過濾器場景下塊緩存幾乎不起作用。但是這并不是說塊緩存沒有用，在讀命中的情況下，塊緩存的作用還是很大的。

布隆過濾器在顯著提升性能的同時(shí)，也是需要浪費(fèi)一定的磁盤空間。LevelDB 需要將布隆過濾器的二進(jìn)制數(shù)據(jù)存儲(chǔ)到數(shù)據(jù)塊中，不過布隆過濾器的空間占比相對(duì)而言不是很高，完全在可接受范圍之內(nèi)。

壓縮

LevelDB 的壓縮算法采用 Snappy，這個(gè)算法解壓縮效率很高，在壓縮比相差不大的情況下 CPU 消耗很低。官方不建議關(guān)閉壓縮算法，不過經(jīng)過我的測試發(fā)現(xiàn)，關(guān)閉壓縮確實(shí)可以顯著提升讀性能。不過關(guān)閉了壓縮，這也意味著你的磁盤空間要浪費(fèi)好幾倍，這代價(jià)也不低。

public static void main(String[] args) throws IOException {
    Options options = new Options();
    options.createIfMissing(true);
    options.compressionType(CompressionType.None);
    DB db = factory.open(new File("/tmp/lvltest"), options);
    try {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            byte[] key = new String("key" + 2 * i).getBytes();
            byte[] value = new String("value" + 2 * i).getBytes();
            db.put(key, value);
        }
        long duration = System.currentTimeMillis() - start;
        System.out.printf("put:%dms\n", duration);
        start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            int index = ThreadLocalRandom.current().nextInt(1000000);
            byte[] key = new String("key" + (2 * index + 1)).getBytes();
            db.get(key);
        }
        duration = System.currentTimeMillis() - start;
        System.out.printf("get:%dms\n", duration);
        start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            byte[] key = new String("key" + 2 * i).getBytes();
            db.delete(key);
        }
        duration = System.currentTimeMillis() - start;
        System.out.printf("delete:%dms\n", duration);
    } finally {
        db.close();
    }
}

----------------
put:3785ms
get:6475ms
delete:1935ms

下面我們?cè)俅蜷_壓縮，對(duì)比一下結(jié)果，讀性能差距接近 1 倍

options.compressionType(CompressionType.SNAPPY);

---------------
put:3804ms
get:11644ms
delete:2750m

下一節(jié)將開始深入 LevelDB 實(shí)現(xiàn)原理，先從 LevelDB 的宏觀結(jié)構(gòu)開