I have selected TreeDB as Kyoto Cabinet backend in hope that it will scale to huge values. Unfortunately, there's a problem:
# ./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
I open a TreeDB, generate 2 random string of random length (0<len<1024) and use them as key and value, respectively. The code:
What's the reason for this?
UPDATE:
I should have clarified before that I'm not after precise measurement of KyotoDB throughput, but tried to test the scalability of KDB, that is, how r/w throughput behaves with growing number of keys in the db, that is the amortized cost of adding/reading a record.
Creation of 1 random string is amortized O(1), creation of N random strings is amortized O(N). As long as there's constant number of random string creations per 1 DB operation, the penalty it imposes is constant in terms of combined operations per second, and so it has no amortized impact on number of DB operations per second.
I have measured the throughput of random string creation:
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
Code: http://pastebin.com/yfVXYbSt
As it could be expected, the cost is O(n). Compare the times as well, e.g. ~8min for 8192000 records when creating random strings and 5h5m when writing them to db.
UPDATE #2:
This seems to have something to do with unique/colliding keys. In this code: http://pastie.org/8906676 I have used keys and values in a manner analogous to the approach used here: http://blog.creapptives.com/post/8330476086/leveldb-vs-kyoto-cabinet-my-findings (http://www.pastie.org/2295228), i.e. generate "key" with linearly incrementing integer suffix ("key1", "key2", etc).
(the updated code also uses transactions every 50,000 writes, this seems to have some impact)
Now the throughput degradation is slow (if actually present at all):
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
Once again, pls look at the trend in throughput, not at absolute values.
Theoretically TreeDB is B+ tree so writing a record to it should be ~O(log n).
But it's not. It looks as if there were hash collisions in there somewhere.
You are benchmarking RandStrings, which, not surprisingly, is very slow. For example, how long does this take to run?
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
}
}
Adapted from http://pastebin.com/0HwHPXFq.
Prepare your random strings outside of the benchmark, before starting to measure the time.
Also, you count the file opening, db opening, db closing and file deletion as part of the benchmark. All this means that you're very unlikely to measure the performance of db.Set(k, v) with any precision.
Retry your benchmark by first generating iter random strings, then using those within your benchmark loop.
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),
}
}
}
Then in your benchmark code:
setupRandomPairs()
// start timing
for _, pair := range randString {
db.Set(pair.key, pair.value)
}
// stop timing
cleanup()