4 ms·

I've read the WisKey paper. 1. Wasn't it simpler to just store the Key/Pointer(Offset) in RocksDB and put the values in the value log? Then the whole database

I've read the WisKey paper. 1. Wasn't it simpler to just store the Key/Pointer(Offset) in RocksDB and put the values in the value log? Then the whole database just becomes a simple wrapper on top of RockDB(or whatever K/V database) with bunch of files as value log. 2. Why 16 bytes for value pointer? 8 bytes is sufficient. 3. If LSM size is around 5GB, screw LSM. I would rather use a simple immutable HashTable which gives you consistent snapshot out of the box for persisting to disk. Every 15 minutes launch a thread to serialize the index to disk. Am I missing something or there is some more detail missing? I mean the reasoning to write a whole database from scratch isn't convincing.

tyingq 8y ago
1. They start off with why they don't want to use Cgo. Not a go expert, so I don't have an opinion on whether that makes sense or not. If the goal is to not use Cgo, they can't use RocksDB. 2. It appears to be 12 bytes. ID, length, offset, all as 4 byte uint32 values: https://github.com/dgraph-io/badger/blob/5242a997f5101ee00c433d5fc96432ec8f111ef5/structs.go#L12 https://github.com/dgraph-io/badger/blob/5242a997f5101ee00c4...
- mutatio 8y ago
  2. I still believe the 16 bytes stands on x64 (8 byte aligned, thus 4 bytes padding).
- majidazimi 8y ago
  Then any other database written in pure Go would be sufficient to keep the index.
  - tyingq 8y ago
    Sure. Searching a bit, they did benchmark against BoltDB, but didn't try what you're suggesting. The benchmark I found is also prior to them adding transactions to Badger. Edit: Actually, the benchmarks turn off sync writes, which makes them silly to me. If you're okay with losing data, you probably wouldn't have chosen a disk based kv store. https://github.com/dgraph-io/badger-bench/blob/master/rw-bench/bench.go#L76 https://github.com/dgraph-io/badger-bench/blob/master/rw-ben... The default install has sync writes turned on, so why benchmark it differently?
    - mrjn 8y ago
      As mentioned in my top comment, we have run benchmarks again. SyncWrites on or off, Badger outperforms BoltDB. There's a nice ASCIIrema link that you can see, which is a recording of me running Ethereum 2.0 store benchmarks.
gregwebs 8y ago
They use go for their database and didn't want to use cgo due to performance and debugging concerns, so they wrote their own storage engine in go. There is some experimental work going on at PingCAP (makers of TiDB) to bring this concept to RocksDB.
- mrjn 8y ago
  I've been thinking of writing a paper about Badger in general and in particular, our experiments with perfecting the value log GC while keeping the 3-dimensional access provided by Badger (RocksDB doesn't provide direct iteration over versions).
  - gregwebs 8y ago
    More information on practical implementation would definitely be helpful. Maybe give a talk if that is a lower bar? The RocksDB conference just happened [1], but there might be a different appropriate meetup. TiDB has versions in its RocksDB keys [2] [1] https://www.meetup.com/RocksDB/photos/29331158/475279758/ https://www.meetup.com/RocksDB/photos/29331158/475279758/ [2] https://pingcap.com/blog/2016-11-15-Travelling-Back-in-Time-and-Reclaiming-the-Lost-Treasures/ https://pingcap.com/blog/2016-11-15-Travelling-Back-in-Time-...
    - mrjn 8y ago
      Ah.. didn't know about the effort at TiDB to put this in RocksDB. They surely can learn from our efforts.
mrjn 8y ago
1. (author) That's how WiscKey did it. But, they omitted a lot of details around how an online value log garbage collection would work. Offline GC doesn't work for most users. On top of that, Badger supports 3-dimensional data access, i.e. key-value-versions. The version axis is supported natively, not overlaid on top of an internal versioning. Supporting versioning while also doing value log GC is a very tough challenge, something that has taken us many iterations to get right. And there're still improvements that we can make, and users ask us for. 2. Skipping, another comment tackles that. 3. Using a hashtable would not give you sorted iterations, something that many users use very heavily. A 15 min thread idea would work a lot worse than LSM tree, just by definition.
- mrjn 8y ago
  Follow on 3. Or, at the very least, it is no better than using skiplists in memtables for key insertion (LSM design), and then compacting them away in the tree levels.

tyingq 8y ago

1. They start off with why they don't want to use Cgo. Not a go expert, so I don't have an opinion on whether that makes sense or not. If the goal is to not use Cgo, they can't use RocksDB. 2. It appears to be 12 bytes. ID, length, offset, all as 4 byte uint32 values: https://github.com/dgraph-io/badger/blob/5242a997f5101ee00c433d5fc96432ec8f111ef5/structs.go#L12 https://github.com/dgraph-io/badger/blob/5242a997f5101ee00c4...

mutatio 8y ago
2. I still believe the 16 bytes stands on x64 (8 byte aligned, thus 4 bytes padding).
majidazimi 8y ago
Then any other database written in pure Go would be sufficient to keep the index.
- tyingq 8y ago
  Sure. Searching a bit, they did benchmark against BoltDB, but didn't try what you're suggesting. The benchmark I found is also prior to them adding transactions to Badger. Edit: Actually, the benchmarks turn off sync writes, which makes them silly to me. If you're okay with losing data, you probably wouldn't have chosen a disk based kv store. https://github.com/dgraph-io/badger-bench/blob/master/rw-bench/bench.go#L76 https://github.com/dgraph-io/badger-bench/blob/master/rw-ben... The default install has sync writes turned on, so why benchmark it differently?
  - mrjn 8y ago
    As mentioned in my top comment, we have run benchmarks again. SyncWrites on or off, Badger outperforms BoltDB. There's a nice ASCIIrema link that you can see, which is a recording of me running Ethereum 2.0 store benchmarks.

gregwebs 8y ago

They use go for their database and didn't want to use cgo due to performance and debugging concerns, so they wrote their own storage engine in go. There is some experimental work going on at PingCAP (makers of TiDB) to bring this concept to RocksDB.

mrjn 8y ago
I've been thinking of writing a paper about Badger in general and in particular, our experiments with perfecting the value log GC while keeping the 3-dimensional access provided by Badger (RocksDB doesn't provide direct iteration over versions).
- gregwebs 8y ago
  More information on practical implementation would definitely be helpful. Maybe give a talk if that is a lower bar? The RocksDB conference just happened [1], but there might be a different appropriate meetup. TiDB has versions in its RocksDB keys [2] [1] https://www.meetup.com/RocksDB/photos/29331158/475279758/ https://www.meetup.com/RocksDB/photos/29331158/475279758/ [2] https://pingcap.com/blog/2016-11-15-Travelling-Back-in-Time-and-Reclaiming-the-Lost-Treasures/ https://pingcap.com/blog/2016-11-15-Travelling-Back-in-Time-...
  - mrjn 8y ago
    Ah.. didn't know about the effort at TiDB to put this in RocksDB. They surely can learn from our efforts.

mrjn 8y ago

1. (author) That's how WiscKey did it. But, they omitted a lot of details around how an online value log garbage collection would work. Offline GC doesn't work for most users. On top of that, Badger supports 3-dimensional data access, i.e. key-value-versions. The version axis is supported natively, not overlaid on top of an internal versioning. Supporting versioning while also doing value log GC is a very tough challenge, something that has taken us many iterations to get right. And there're still improvements that we can make, and users ask us for. 2. Skipping, another comment tackles that. 3. Using a hashtable would not give you sorted iterations, something that many users use very heavily. A 15 min thread idea would work a lot worse than LSM tree, just by definition.

mrjn 8y ago
Follow on 3. Or, at the very least, it is no better than using skiplists in memtables for key insertion (LSM design), and then compacting them away in the tree levels.