5 ms·

In my experience, it's not just throughput that's important, but also 99th percentile latency. If I understand fractal trees correctly, you sometimes need to re

In my experience, it's not just throughput that's important, but also 99th percentile latency. If I understand fractal trees correctly, you sometimes need to rewrite all of your elements on disk. How do you do this without causing lag?

leif 14y ago
That's happily not how fractal trees work, at all. We have a few talks online describing how they work. Zardosht has one here http://vimeo.com/m/26471692 http://vimeo.com/m/26471692 . I thought Bradley had a more detailed one at MIT but I can't find it right now. (EDIT: found it! http://video.mit.edu/watch/lecture-19-how-tokudb-fractal-tree-indexes-work-1361/ http://video.mit.edu/watch/lecture-19-how-tokudb-fractal-tre...) Basically, I think you're thinking of the COLA. What we implement does have a literal tree structure, with nodes and children and the whole thing, so at any point you're just writing out new copies of individual nodes, which are on the order of a megabyte. At no point do we have to rewrite a large portion of the tree, so there aren't any latency issues.
- DanWaterworth 14y ago
  Thank you very much for the links. Is my understanding correct? Essentially, a fractal tree is a B-Tree (or perhaps a B+Tree?) with buffers on each branch (per child). Operations get added to these buffers and when one becomes full, the operations get passed to the corresponding child node. Operations are applied when they reach the node that is responsible for the data concerned.
  - leif 14y ago
    That's about it! It's like a B+Tree in that the data resides in the leaves (well, and in the buffers), except that the fanout is a lot lower because we save room in the internal nodes for the buffers.
    - DanWaterworth 14y ago
      I'm a little confused. I thought fractal trees worked cache obliviously or am I mistaken?
      - leif 14y ago
        In theory, it is cache oblivious, and the CO-DAM model informs our decisions about the implementation, but no, the implementation itself isn't actually cache oblivious. Shh, don't tell on us. A "fractal tree" is defined by our marketing team as "whatever it is we actually implement." If you want to talk cache-oblivious data structures, we can talk about things like the COLA and cache-oblivious streaming B-trees which have rigorous definitions in the literature. At some point, if you want to achieve a certain level of detail, you have to pick one or the other in order to continue the conversation.
    - alex137 14y ago
      Hi. I thought the block size is much bigger in fractal trees (like 4MiB instead of 4KiB) than in B-trees hence the fanout would be about the same? I'm trying to experiment with these ideas on my side, but can't quite grok how large the buffers must be at each level of the tree. Let's take a concrete example like: 2^40 (1T) records with an 8-byte key and an 8-byte value. In a traditional B-tree with a 8KiB block size and assuming links take 8 bytes too and assume for a while that blocks are completely full. So, that's 1G leaf blocks, a fanout of about 1K and hence & full 4-level trees: 1 root block, 1K level-2 blocks, 1M level-3 blocks, 1G leaf blocks. In this setting, I understand that a fractal tree will attach a buffer to each internal node. How large will they be at level 1 (root), level 2, and level 3 ?
      - leif 14y ago
        The buffers have the same capacity at each level of the tree. It doesn't have to be that way, and you can find different strategies in the literature, but that's the way we do it. The degree of each internal node is way lower, because we want to use the space in internal nodes for buffers more than for keys. In a 16TB tree, we would probably have a tree of height 6 or 7. What we restrict is the size of a whole internal node, so that any one buffer in it can get much more full than the others if it needs to. We want to pick a node size that makes sense for your media. 4MB is a good compromise for spinning disks between their typical bandwidth and seek time, and it's large enough to give the garbage collector a rest on SSDs.
- stinkypete 14y ago
  Sounds like a Y-Tree to me: "A Novel Index Supporting High Volume Data Warehouse Insertions," C. Jermaine et. al, VLDB '99. How are fractal trees different?
  - leif 14y ago
    Is that the same as Willard's Y-fast tree? If so, then no they're not very similar. If not then I'm unfamiliar and I should read that paper.
    - stinkypete 14y ago
      Nope, not the same. From the descriptions you give above it is very similar (a modified B-tree with heaps of delayed insertions in internal nodes), though the analysis in the paper does not use CO techniques. This tweak to B-trees to support fast insertions works so well I am really surprised it has not become more common in practice. The only downside I can think of is that flushes down the tree when internal buffers get large may cause lower-level pages to become overfull, but if you allow more than one flush operations at each level you can avoid this problem. Of course, that's only important if you are paranoid about internal nodes actually fitting in a page; if you don't care about that, then the worst-case analysis picture looks much better since a flush operation causes at most one flush in the pages immediately below it in the tree structure.
      - leif 14y ago
        I was surprised too, when I learned this technique, that people weren't already doing it. I think it's just an age thing. B-trees are old so they have all the kinks worked out, at least in mature implementations. Fractal trees are new enough that there are still a bunch of tradeoffs to play with and evaluate. When you actually go and implement the system, you find all these behaviors that really aren't expressed in the theory. There are lots of things we're still experimenting with. Flushing isn't too hard, if a flush makes another node way too big, you can just flush that one too. We don't allow our cascading flushes to fan out, to prevent latency-style problems, but they can flush all the way down to a leaf. There are some other fun problems around query strategies and concurrency control too. It's definitely a fun structure to play with.

leif 14y ago

That's happily not how fractal trees work, at all. We have a few talks online describing how they work. Zardosht has one here http://vimeo.com/m/26471692 http://vimeo.com/m/26471692 . I thought Bradley had a more detailed one at MIT but I can't find it right now. (EDIT: found it! http://video.mit.edu/watch/lecture-19-how-tokudb-fractal-tree-indexes-work-1361/ http://video.mit.edu/watch/lecture-19-how-tokudb-fractal-tre...) Basically, I think you're thinking of the COLA. What we implement does have a literal tree structure, with nodes and children and the whole thing, so at any point you're just writing out new copies of individual nodes, which are on the order of a megabyte. At no point do we have to rewrite a large portion of the tree, so there aren't any latency issues.

DanWaterworth 14y ago
Thank you very much for the links. Is my understanding correct? Essentially, a fractal tree is a B-Tree (or perhaps a B+Tree?) with buffers on each branch (per child). Operations get added to these buffers and when one becomes full, the operations get passed to the corresponding child node. Operations are applied when they reach the node that is responsible for the data concerned.
- leif 14y ago
  That's about it! It's like a B+Tree in that the data resides in the leaves (well, and in the buffers), except that the fanout is a lot lower because we save room in the internal nodes for the buffers.
  - DanWaterworth 14y ago
    I'm a little confused. I thought fractal trees worked cache obliviously or am I mistaken?
    - leif 14y ago
      In theory, it is cache oblivious, and the CO-DAM model informs our decisions about the implementation, but no, the implementation itself isn't actually cache oblivious. Shh, don't tell on us. A "fractal tree" is defined by our marketing team as "whatever it is we actually implement." If you want to talk cache-oblivious data structures, we can talk about things like the COLA and cache-oblivious streaming B-trees which have rigorous definitions in the literature. At some point, if you want to achieve a certain level of detail, you have to pick one or the other in order to continue the conversation.
  - alex137 14y ago
    Hi. I thought the block size is much bigger in fractal trees (like 4MiB instead of 4KiB) than in B-trees hence the fanout would be about the same? I'm trying to experiment with these ideas on my side, but can't quite grok how large the buffers must be at each level of the tree. Let's take a concrete example like: 2^40 (1T) records with an 8-byte key and an 8-byte value. In a traditional B-tree with a 8KiB block size and assuming links take 8 bytes too and assume for a while that blocks are completely full. So, that's 1G leaf blocks, a fanout of about 1K and hence & full 4-level trees: 1 root block, 1K level-2 blocks, 1M level-3 blocks, 1G leaf blocks. In this setting, I understand that a fractal tree will attach a buffer to each internal node. How large will they be at level 1 (root), level 2, and level 3 ?
    - leif 14y ago
      The buffers have the same capacity at each level of the tree. It doesn't have to be that way, and you can find different strategies in the literature, but that's the way we do it. The degree of each internal node is way lower, because we want to use the space in internal nodes for buffers more than for keys. In a 16TB tree, we would probably have a tree of height 6 or 7. What we restrict is the size of a whole internal node, so that any one buffer in it can get much more full than the others if it needs to. We want to pick a node size that makes sense for your media. 4MB is a good compromise for spinning disks between their typical bandwidth and seek time, and it's large enough to give the garbage collector a rest on SSDs.
stinkypete 14y ago
Sounds like a Y-Tree to me: "A Novel Index Supporting High Volume Data Warehouse Insertions," C. Jermaine et. al, VLDB '99. How are fractal trees different?
- leif 14y ago
  Is that the same as Willard's Y-fast tree? If so, then no they're not very similar. If not then I'm unfamiliar and I should read that paper.
  - stinkypete 14y ago
    Nope, not the same. From the descriptions you give above it is very similar (a modified B-tree with heaps of delayed insertions in internal nodes), though the analysis in the paper does not use CO techniques. This tweak to B-trees to support fast insertions works so well I am really surprised it has not become more common in practice. The only downside I can think of is that flushes down the tree when internal buffers get large may cause lower-level pages to become overfull, but if you allow more than one flush operations at each level you can avoid this problem. Of course, that's only important if you are paranoid about internal nodes actually fitting in a page; if you don't care about that, then the worst-case analysis picture looks much better since a flush operation causes at most one flush in the pages immediately below it in the tree structure.
    - leif 14y ago
      I was surprised too, when I learned this technique, that people weren't already doing it. I think it's just an age thing. B-trees are old so they have all the kinks worked out, at least in mature implementations. Fractal trees are new enough that there are still a bunch of tradeoffs to play with and evaluate. When you actually go and implement the system, you find all these behaviors that really aren't expressed in the theory. There are lots of things we're still experimenting with. Flushing isn't too hard, if a flush makes another node way too big, you can just flush that one too. We don't allow our cascading flushes to fan out, to prevent latency-style problems, but they can flush all the way down to a leaf. There are some other fun problems around query strategies and concurrency control too. It's definitely a fun structure to play with.