5 ms·

edited correct link to the actual paper http://arxiv.org/PS_cache/arxiv/pdf/1103/1103.4282v2.pdf http://arxiv.org/PS_cache/arxiv/pdf/1103/1103.4282v2.pdf

soamv 16y ago
Hmm, that looks like a different paper. Try this: http://arxiv.org/PS_cache/arxiv/pdf/1103/1103.4282v2.pdf http://arxiv.org/PS_cache/arxiv/pdf/1103/1103.4282v2.pdf
wnoise 16y ago
I strongly prefer links to the abstract: http://arxiv.org/abs/1103.4282v2 http://arxiv.org/abs/1103.4282v2 This lets you: (a) read the abstract before deciding whether or not to read the paper (b) easily find earlier (or later) versions of the paper (c) easily search for other papers the authors have on the arxiv.
jholman 16y ago
If we're replacing blog links with arXiv abstract links, note that there are actually two papers linked, both interesting. "Stratified B-trees and versioning dictionaries" http://arxiv.org/abs/1103.4282 http://arxiv.org/abs/1103.4282 This is actually the newer paper, and presents the "Stratified B-Tree" data structure itself. It also explicitly mentions SSDs and appending, by the way. "Optimal query/update tradeoffs in versioned dictionaries" http://arxiv.org/abs/1103.2566 http://arxiv.org/abs/1103.2566 This is a longer and more, shall I say, academic paper. It appears to be incompletely finished, though, because it has a TODO, and also a marginal FIXME.
- andytwigg 16y ago
  Thanks for that. The second paper you reference contains more details of the data structure. I have submitted an updated version of the second paper - it will probably appear on arxiv in 2 days. We have a much improved version of it, though, which I hope to post sometime next week. For more information about append-only B-trees and SSDs, see http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-for-each-other/ http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-...
  - leef 16y ago
    Thanks. The paper mentioned an open-source project for this. Does that exist yet?
    - andytwigg 16y ago
      The core kernel code will be released in the next few weeks, along with a community site, probably code.acunu.com. We hope to post an announcement when that happens.
  - crux_ 16y ago
    I don't suppose there's a chance of seeing the O'Caml implementation released as well, is there? It's neat to see it being used for what (IMO) is a really underutilized sweet spot for the language. (That & the fact that a code release is an invaluable road map for anyone looking to follow in your footsteps.)
    - andytwigg 16y ago
      The OCaml implementation is what we use internally to test implementations of complicated new data structures, and as such, it's quite unreadable to anyone else! We will probably talk at CUFP about our experiences of OCaml. It definitely has some upsides, but is not without some fairly major downsides (concurrency, serialization, lack of consistently-named library functions, ...) . As such, we're rewriting our basic data structures in Scala - this seems like it keeps most of the benefits but without some of the major problems. Now we know how to implement the structures, we might be able to do a clean implementation which can be released!

soamv 16y ago

Hmm, that looks like a different paper. Try this: http://arxiv.org/PS_cache/arxiv/pdf/1103/1103.4282v2.pdf http://arxiv.org/PS_cache/arxiv/pdf/1103/1103.4282v2.pdf

wnoise 16y ago

I strongly prefer links to the abstract: http://arxiv.org/abs/1103.4282v2 http://arxiv.org/abs/1103.4282v2 This lets you: (a) read the abstract before deciding whether or not to read the paper (b) easily find earlier (or later) versions of the paper (c) easily search for other papers the authors have on the arxiv.

jholman 16y ago

If we're replacing blog links with arXiv abstract links, note that there are actually two papers linked, both interesting. "Stratified B-trees and versioning dictionaries" http://arxiv.org/abs/1103.4282 http://arxiv.org/abs/1103.4282 This is actually the newer paper, and presents the "Stratified B-Tree" data structure itself. It also explicitly mentions SSDs and appending, by the way. "Optimal query/update tradeoffs in versioned dictionaries" http://arxiv.org/abs/1103.2566 http://arxiv.org/abs/1103.2566 This is a longer and more, shall I say, academic paper. It appears to be incompletely finished, though, because it has a TODO, and also a marginal FIXME.

andytwigg 16y ago
Thanks for that. The second paper you reference contains more details of the data structure. I have submitted an updated version of the second paper - it will probably appear on arxiv in 2 days. We have a much improved version of it, though, which I hope to post sometime next week. For more information about append-only B-trees and SSDs, see http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-for-each-other/ http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-...
- leef 16y ago
  Thanks. The paper mentioned an open-source project for this. Does that exist yet?
  - andytwigg 16y ago
    The core kernel code will be released in the next few weeks, along with a community site, probably code.acunu.com. We hope to post an announcement when that happens.
- crux_ 16y ago
  I don't suppose there's a chance of seeing the O'Caml implementation released as well, is there? It's neat to see it being used for what (IMO) is a really underutilized sweet spot for the language. (That & the fact that a code release is an invaluable road map for anyone looking to follow in your footsteps.)
  - andytwigg 16y ago
    The OCaml implementation is what we use internally to test implementations of complicated new data structures, and as such, it's quite unreadable to anyone else! We will probably talk at CUFP about our experiences of OCaml. It definitely has some upsides, but is not without some fairly major downsides (concurrency, serialization, lack of consistently-named library functions, ...) . As such, we're rewriting our basic data structures in Scala - this seems like it keeps most of the benefits but without some of the major problems. Now we know how to implement the structures, we might be able to do a clean implementation which can be released!