KyotoCabinet (TreeDB)的严重性能退化

Question

我选择了TreeDB作为京都内阁的后台，希望它能够扩大到巨大的价值。不幸的是，有一个问题：

# ./kyotobench
Generated string length: 1024
1000 records, type t 74.008887ms throughput: 13511 /sec
2000 records, type t 145.390096ms throughput: 13756 /sec
4000 records, type t 290.13486ms throughput: 13786 /sec
8000 records, type t 584.46691ms throughput: 13687 /sec
16000 records, type t 1.150792756s throughput: 13903 /sec
32000 records, type t 2.134860729s throughput: 14989 /sec
64000 records, type t 4.378002268s throughput: 14618 /sec
128000 records, type t 9.41012632s throughput: 13602 /sec
256000 records, type t 20.457090225s throughput: 12513 /sec
512000 records, type t 45.934115353s throughput: 11146 /sec
1024000 records, type t 1m39.120917207s throughput: 10330 /sec
2048000 records, type t 3m41.720146906s throughput: 9236 /sec
4096000 records, type t 15m26.041653712s throughput: 4423 /sec
8192000 records, type t 5h5m31.431477812s throughput: 446 /sec

我打开一个TreeDB，生成两个随机长度的随机字符串(0<len<1024)，并将它们分别用作键和值。守则：

http://pastebin.com/0HwHPXFq

原因是什么？

更新：

在此之前，我应该澄清，我不是在精确测量KyotoDB吞吐量，而是尝试测试KDB的可伸缩性，即r/w吞吐量如何随db中键数的增加而变化，即添加/读取记录的摊还成本。

1随机串的产生被摊销O(1)，N个随机串的产生被摊还O(N)。只要每1DB操作有固定的随机字符串创建数，它施加的惩罚就等于每秒合并的操作，因此它对每秒DB操作的数量没有摊销的影响。

我测量了随机字符串创建的吞吐量：

1000 strings, type t 65.380289ms throughput: 15295 /sec
2000 strings, type t 130.345234ms throughput: 15343 /sec
4000 strings, type t 259.886865ms throughput: 15391 /sec
8000 strings, type t 519.380392ms throughput: 15402 /sec
16000 strings, type t 1.040323537s throughput: 15379 /sec
32000 strings, type t 1.855234924s throughput: 17248 /sec
64000 strings, type t 3.709873467s throughput: 17251 /sec
128000 strings, type t 7.371360742s throughput: 17364 /sec
256000 strings, type t 14.705493792s throughput: 17408 /sec
512000 strings, type t 29.488131398s throughput: 17362 /sec
1024000 strings, type t 59.46313568s throughput: 17220 /sec
2048000 strings, type t 1m58.688153868s throughput: 17255 /sec
4096000 strings, type t 3m57.415585291s throughput: 17252 /sec
8192000 strings, type t 7m57.054025376s throughput: 17172 /sec

代码：http://pastebin.com/yfVXYbSt

正如可以预料的那样，费用是O(n)。同时比较时间，例如，在创建随机字符串时，对8192000条记录进行8分钟的比较，在将它们写入db时使用5 h5m。

更新2：

这似乎与独特的/碰撞的键有关。在此代码：http://pastie.org/8906676中，我使用键和值的方式类似于这里使用的方法：http://blog.creapptives.com/post/8330476086/leveldb-vs-kyoto-cabinet-my-findings (http://www.pastie.org/2295228)，即生成具有线性递增整数后缀("key1“、"key2”等)的“键”。

(更新后的代码也使用每50,000次写入的事务，这似乎有一定的影响)

现在吞吐量下降很慢(如果确实存在的话)：

4000 records, type t 10.220836ms throughput: 391357 /sec
8000 records, type t 18.113652ms throughput: 441655 /sec
16000 records, type t 36.6948ms throughput: 436029 /sec
32000 records, type t 74.048029ms throughput: 432151 /sec
64000 records, type t 148.585114ms throughput: 430729 /sec
128000 records, type t 303.646709ms throughput: 421542 /sec
256000 records, type t 633.831383ms throughput: 403892 /sec
512000 records, type t 1.297555153s throughput: 394588 /sec
1024000 records, type t 2.471077696s throughput: 414394 /sec
2048000 records, type t 5.970116441s throughput: 343041 /sec
4096000 records, type t 11.449808222s throughput: 357735 /sec
8192000 records, type t 23.142591222s throughput: 353979 /sec
16384000 records, type t 46.90204795s throughput: 349323 /sec

再一次，请看吞吐量的趋势，而不是绝对值。

从理论上讲，TreeDB是B+树，因此向它写入记录应该是~O(log )。

但事实并非如此。好像在某个地方有哈希碰撞。

Answer 1

您正在对RandStrings进行基准测试，这并不奇怪，它非常慢。例如，运行多长时间？

package main

import (
    "fmt"
    "math/rand"
)

const chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890 abcdefghijklmnopqrstuvwxyz" +
    "~!@#$%^&*()-_+={}[]\\|<,>.?/\"';:`"

const Maxlen = 1024

func RandStrings(N int) []string {
    r := make([]string, N)
    ri := 0
    buf := make([]byte, Maxlen)
    known := map[string]bool{}

    for i := 0; i < N; i++ {
    retry:
        l := rand.Intn(Maxlen)
        for j := 0; j < l; j++ {
            buf[j] = chars[rand.Intn(len(chars))]
        }
        s := string(buf[0:l])
        if known[s] {
            goto retry
        }
        known[s] = true
        r[ri] = s
        ri++
    }
    return r
}

func runbench(t string, n int) {
    for i := 0; i < n; i++ {
        r := RandStrings(2)
        _ = r
    }
}

func main() {
    iter := 64000000
    incr := 1000
    for i := incr; i < iter+1; i = incr {
        runbench("t", i)
        incr = 2 * i
    }
}

改编自http://pastebin.com/0HwHPXFq。

Answer 2

在开始测量时间之前，在基准测试之外准备随机字符串。

此外，还可以将文件打开、db打开、db关闭和文件删除作为基准测试的一部分进行计算。所有这些都意味着您不太可能精确地测量db.Set(k, v)的性能。

通过首先生成iter随机字符串，然后使用基准循环中的随机字符串，重新尝试您的基准测试。

type Pair struct { key, value string }

var randString = make([]Pair, iter)

func setupRandomPairs() {
    known := make(map[string]bool)
    for i := range randString {
        randString[i] = Pair {
            key:   genRandomString(known),
            value: genRandomString(known),
        }
    }
}

然后在基准代码中：

setupRandomPairs()
// start timing
for _, pair := range randString {
    db.Set(pair.key, pair.value)
}
// stop timing
cleanup()