java - BerkeleyDB JE随机访问时间呈非线性增长

我正在测试BerkeleyDB Java Edition，以了解我是否可以在项目中使用它。

我创建了一个非常简单的程序，可与com.sleepycat.je.Database类的对象一起使用：


写入N条记录，每条记录5-15kb，并生成类似Integer.toString（random.nextInt（））的键；
读取这些记录，并以与创建时相同的顺序使用Database＃get方法获取它们；
用方法Database＃get随机读取相同数量的记录。


现在我看到了奇怪的事情。第三次测试的执行时间随着记录数量的增加而非常非线性地增长。


N = 80000，写入= 55秒，顺序提取= 17秒，随机提取= 3秒
N = 100000，写入= 60秒，顺序提取= 20秒，随机提取= 7秒
N = 120000，写= 68sec，顺序提取= 27sec，随机提取= 11sec
N = 140000，写= 82秒，顺序提取= 32秒，随机提取= 47秒


（当然，我已经运行了几次测试。）

我想我做错了什么。这是参考源（抱歉，它有点长），以相同的顺序调用方法：

private Environment env;
private Database db;
private Random random = new Random();
private List<String> keys = new ArrayList<String>();
private int seed = 113;


public boolean dbOpen() {
    EnvironmentConfig ec = new EnvironmentConfig();
    DatabaseConfig dc = new DatabaseConfig();
    ec.setAllowCreate(true);
    dc.setAllowCreate(true);
    env = new Environment(new File("mydbenv"), ec);
    db = env.openDatabase(null, "moe", dc);
    return true;
}

public int storeRecords(int i) {
    int j;
    long size = 0;
    DatabaseEntry key = new DatabaseEntry();
    DatabaseEntry val = new DatabaseEntry();

    random.setSeed(seed);

    for (j = 0; j < i; j++) {
        String k = Long.toString(random.nextLong());
        byte[] data = new byte[5000 + random.nextInt(10000)];
        keys.add(k);

        size += data.length;

        random.nextBytes(data);
        key.setData(k.getBytes());
        val.setData(data);
        db.put(null, key, val);
    }

    System.out.println("GENERATED SIZE: " + size);

    return j;
}

public int fetchRecords(int i) {
    int j, res;
    DatabaseEntry key = new DatabaseEntry();
    DatabaseEntry val = new DatabaseEntry();

    random.setSeed(seed);
    res = 0;

    for (j = 0; j < i; j++) {
        String k = Long.toString(random.nextLong());
        byte[] data = new byte[5000 + random.nextInt(10000)];
        random.nextBytes(data);
        key.setData(k.getBytes());
        db.get(null, key, val, null);
        if (Arrays.equals(data, val.getData())) {
            res++;
        } else {
            System.err.println("FETCH differs: " + j);
            System.err.println(data.length + " " + val.getData().length);
        }
    }

    return res;
}

public int fetchRandom(int i) {
    DatabaseEntry key = new DatabaseEntry();
    DatabaseEntry val = new DatabaseEntry();

    for (int j = 0; j < i; j++) {
        String k = keys.get(random.nextInt(keys.size()));
        key.setData(k.getBytes());
        db.get(null, key, val, null);
    }

    return i;
}

最佳答案

性能下降是非线性的，原因有两个：


BDB-JE数据结构是一个b树，具有O（log（n））性能，可检索一条记录。通过get方法检索所有数据为O（n * log（n））。
大数据集不适合RAM，因此磁盘访问会减慢一切。随机访问的缓存位置非常差。


请注意，您可以通过放弃一些持久性来提高写入性能：ec.setTxnWriteNoSync（true）;

您可能还想尝试Tupl，这是我一直在努力的开源BerkeleyDB替代品。它仍然处于Alpha阶段，但是您可以在SourceForge上找到它。

为了公平地比较BDB-JE和Tupl，我将缓存大小设置为500M，并在存储方法的末尾执行了一个明确的检查点。

使用BDB-JE：


N = 80000，写入= 11.0秒，提取= 5.3秒
N = 100000，写入= 13.6sec，提取= 7.0sec
N = 120000，写入= 16.4秒，提取= 29.5秒
N = 140000，写入= 18.8sec，提取= 35.9sec
N = 160000，写入= 21.5sec，提取= 41.3sec
N = 180000，写入= 23.9秒，提取= 46.4秒


使用Tupl：


N = 80000，写入= 21.7秒，提取= 4.4秒
N = 100000，写入= 27.6sec，提取= 6.3sec
N = 120000，写入= 30.2秒，提取= 8.4秒
N = 140000，写入= 35.4秒，提取= 12.2秒
N = 160000，写入= 39.9sec，提取= 17.4sec
N = 180000，写入= 45.4秒，提取= 22.8秒


由于BDB-JE基于日志的格式，因此其写入条目的速度更快。 Tupl的阅读速度更快。这是Tupl测试的来源：

导入java.io .;
导入java.util .;

导入org.cojen.tupl。*;

公共课程TuplTest {
公共静态void main（final String [] args）引发异常{
最终的RandTupl rt =新的RandTupl（）;
rt.dbOpen（args [0]）;

    {
        long start = System.currentTimeMillis();
        rt.storeRecords(Integer.parseInt(args[1]));
        long end = System.currentTimeMillis();
        System.out.println("store duration: " + (end - start));
    }

    {
        long start = System.currentTimeMillis();
        rt.fetchRecords(Integer.parseInt(args[1]));
        long end = System.currentTimeMillis();
        System.out.println("fetch duration: " + (end - start));
    }
}

private Database db;
private Index ix;
private Random random = new Random();
private List<String> keys = new ArrayList<String>();
private int seed = 113;

public boolean dbOpen(String home) throws Exception {
    DatabaseConfig config = new DatabaseConfig();
    config.baseFile(new File(home));
    config.durabilityMode(DurabilityMode.NO_FLUSH);
    config.minCacheSize(500000000);
    db = Database.open(config);
    ix = db.openIndex("moe");
    return true;
}

public int storeRecords(int i) throws Exception {
    int j;
    long size = 0;

    random.setSeed(seed);

    for (j = 0; j < i; j++) {
        String k = Long.toString(random.nextLong());
        byte[] data = new byte[5000 + random.nextInt(10000)];
        keys.add(k);

        size += data.length;

        random.nextBytes(data);
        ix.store(null, k.getBytes(), data);
    }

    System.out.println("GENERATED SIZE: " + size);

    db.checkpoint();
    return j;
}

public int fetchRecords(int i) throws Exception {
    int j, res;

    random.setSeed(seed);
    res = 0;

    for (j = 0; j < i; j++) {
        String k = Long.toString(random.nextLong());
        byte[] data = new byte[5000 + random.nextInt(10000)];
        random.nextBytes(data);
        byte[] val = ix.load(null, k.getBytes());
        if (Arrays.equals(data, val)) {
            res++;
        } else {
            System.err.println("FETCH differs: " + j);
            System.err.println(data.length + " " + val.length);
        }
    }

    return res;
}

public int fetchRandom(int i) throws Exception {
    for (int j = 0; j < i; j++) {
        String k = keys.get(random.nextInt(keys.size()));
        ix.load(null, k.getBytes());
    }

    return i;
}

}