5 ms·

Does this mean that it's now safe for folks to write their own versions of the data structures that tokutek has patents on? They hold patents on some of the mo

Does this mean that it's now safe for folks to write their own versions of the data structures that tokutek has patents on? They hold patents on some of the more natural choices In cache oblivious b trees (admittedly they also invented those retrospectively natural choices).

SwellJoe 14y ago
I'm unfamiliar with this particular implementation, but it sounds (from your one sentence description) kinda like Dancing Trees, created by Hans Reiser, for ReiserFS. Would this be prior art, or would this be different approaches to similar problems? http://en.wikipedia.org/wiki/Dancing_tree http://en.wikipedia.org/wiki/Dancing_tree
- carterschonwald 14y ago
  Yes and no. I think they're doing a variant of cache oblivious buffered B epsilon trees. Ill have to go code spelunking (now that the source is available. Boy am I glad it's gplv2 and not some (a)gplv3 variant). Thanks for the interesting reference!
  - mjn 14y ago
    For the patent side of things, it being GPLv2 is sort of unfortunate compared to GPLv3, because v3 contains a patent grant, whereas v2 doesn't. It's possible some kind of implicit patent grant could be read into it by a court, e.g. that by open-sourcing some software, a company is making an open offer to use/modify the software, and then if they turned around and sued you for doing so, some equitable doctrine like estoppel would stand in the way. But an explicit patent grant is a lot clearer. For companies wary of v3 for other reasons, I wonder if there's an easy/semi-standardized way to tack on a patent grant? I'd feel much safer using open-source software licensed under some kind of "MIT + patent grant" or "GPLv2 + patent grant" license than the vanilla versions.
    - carterschonwald 14y ago
      Eeek. Didn't realize there was that delta on patents on v2 vs v3. Was aware of that problem with MIT/bsd though. Apache2 kinda is the MIT/bsd with explicit patent grants I guess. I suppose that idemnification from code patent issues is probably part of the commercial license / product then?
    - bradleykuszmaul 14y ago
      If you are interested in this, you should look at our source distribution's license file. We have done the work to get a patent license from MIT, Stony Brook, and Rutgers so that the users of the GPL'd code can use the fractal tree patents. Indemnification is a completely different issue: no open source software that I know of provides any kind of indemnification which would protect you from a lawsuit by a third party. -Bradley (bradley@tokutek.com)
      - mjn 14y ago
        Ah excellent, sorry for missing that. Yeah, I was just looking for a patent grant, not indemnification. I saw the notice of GPLv2, but hadn't seen the additional terms. If anyone else is looking for those, they're located here (possibly among other places): https://github.com/Tokutek/ft-index/blob/master/README-TOKUDB https://github.com/Tokutek/ft-index/blob/master/README-TOKUD... (ctrl+f "PATENT RIGHTS GRANT").
      - carterschonwald 14y ago
        Could you elaborate on the meaning of the phrase "this implementation"? Eg if I write some apache2 Haskell code that can interact seamlessly with the rest of the storage engine implementation, and I swap that part In, is that still the same implementation?
- leif 14y ago
  Fractal Tree indexes are very different from Dancing Trees. See http://tokutek.com/what-is-a-fractal-tree http://tokutek.com/what-is-a-fractal-tree for an overview, and I'd be happy to answer questions if you have them.
  - SwellJoe 14y ago
    Hmmm, after reading the simple explanation PDF of Fractal Trees, they sound more like Dancing Trees than I'd assumed, but I am a poorly informed outsider. The key feature, from a performance perspective, is that writes are minimized by making each write do more, though both also help with SSD wear as a side effect. So, from the outside, it looks like both accomplish many of the same goals, and they do it by fundamentally altering B-tree implementation with modern hardware in mind. But, this isn't my area. I only have a passing understanding of Dancing Trees (my previous business led me to following ReiserFS closely, but I haven't paid any attention to filesystem or database performance in 7+ years), and no real understanding of Fractal Trees. I'm glad it's Open Source, however, and thanks for the pointers.
    - leif 14y ago
      Dancing Trees are algorithmically the same as B+ trees, if I understand the wikipedia article correctly. With just a uniformly random workload with a large enough working set, one would behave pretty much exactly the same as a B+ tree.
andrewljohnson 14y ago
Oh what a world. A data structure should never be patentable - what's the difference between a data structure and a math formula? Both are just notations for reality, and can spring up in the minds of many disparate inventors. I'd really like to see TokuDB discuss its patents, why they have them, and what they intend to do with them. I'd like to see a page like that from every corporation on their website actually.
- leif 14y ago
  IANAL, but the patents are owned by the universities where the founders work, not by the company. I don't know if this makes you feel any better though.
- reinhardt 14y ago
  "A data structure should never be patentable - what's the difference between a data structure and a math formula? Both are just notations for reality, and can spring up in the minds of many disparate inventors." Can we please let this disingenuous argument die already? Yes, in theory they can spring up in many minds independently. In practice they rarely do unless they are trivial. If the alleged disparate inventors can prove they came up with it independently, fine; the onus is on them.
  - andrewljohnson 14y ago
    In practice, independent invention happens all the time, and we end up with absurd patent lawsuits as a result.
    - reinhardt 14y ago
      AFAIK none of these ludicrous patents are about data structures, algorithms or math formulas.
      - Kalium 14y ago
        I find that somewhat difficult to accept, given that pretty much every single patent that touches software is ludicrous.

SwellJoe 14y ago

I'm unfamiliar with this particular implementation, but it sounds (from your one sentence description) kinda like Dancing Trees, created by Hans Reiser, for ReiserFS. Would this be prior art, or would this be different approaches to similar problems? http://en.wikipedia.org/wiki/Dancing_tree http://en.wikipedia.org/wiki/Dancing_tree

carterschonwald 14y ago
Yes and no. I think they're doing a variant of cache oblivious buffered B epsilon trees. Ill have to go code spelunking (now that the source is available. Boy am I glad it's gplv2 and not some (a)gplv3 variant). Thanks for the interesting reference!
- mjn 14y ago
  For the patent side of things, it being GPLv2 is sort of unfortunate compared to GPLv3, because v3 contains a patent grant, whereas v2 doesn't. It's possible some kind of implicit patent grant could be read into it by a court, e.g. that by open-sourcing some software, a company is making an open offer to use/modify the software, and then if they turned around and sued you for doing so, some equitable doctrine like estoppel would stand in the way. But an explicit patent grant is a lot clearer. For companies wary of v3 for other reasons, I wonder if there's an easy/semi-standardized way to tack on a patent grant? I'd feel much safer using open-source software licensed under some kind of "MIT + patent grant" or "GPLv2 + patent grant" license than the vanilla versions.
  - carterschonwald 14y ago
    Eeek. Didn't realize there was that delta on patents on v2 vs v3. Was aware of that problem with MIT/bsd though. Apache2 kinda is the MIT/bsd with explicit patent grants I guess. I suppose that idemnification from code patent issues is probably part of the commercial license / product then?
  - bradleykuszmaul 14y ago
    If you are interested in this, you should look at our source distribution's license file. We have done the work to get a patent license from MIT, Stony Brook, and Rutgers so that the users of the GPL'd code can use the fractal tree patents. Indemnification is a completely different issue: no open source software that I know of provides any kind of indemnification which would protect you from a lawsuit by a third party. -Bradley (bradley@tokutek.com)
    - mjn 14y ago
      Ah excellent, sorry for missing that. Yeah, I was just looking for a patent grant, not indemnification. I saw the notice of GPLv2, but hadn't seen the additional terms. If anyone else is looking for those, they're located here (possibly among other places): https://github.com/Tokutek/ft-index/blob/master/README-TOKUDB https://github.com/Tokutek/ft-index/blob/master/README-TOKUD... (ctrl+f "PATENT RIGHTS GRANT").
    - carterschonwald 14y ago
      Could you elaborate on the meaning of the phrase "this implementation"? Eg if I write some apache2 Haskell code that can interact seamlessly with the rest of the storage engine implementation, and I swap that part In, is that still the same implementation?
leif 14y ago
Fractal Tree indexes are very different from Dancing Trees. See http://tokutek.com/what-is-a-fractal-tree http://tokutek.com/what-is-a-fractal-tree for an overview, and I'd be happy to answer questions if you have them.
- SwellJoe 14y ago
  Hmmm, after reading the simple explanation PDF of Fractal Trees, they sound more like Dancing Trees than I'd assumed, but I am a poorly informed outsider. The key feature, from a performance perspective, is that writes are minimized by making each write do more, though both also help with SSD wear as a side effect. So, from the outside, it looks like both accomplish many of the same goals, and they do it by fundamentally altering B-tree implementation with modern hardware in mind. But, this isn't my area. I only have a passing understanding of Dancing Trees (my previous business led me to following ReiserFS closely, but I haven't paid any attention to filesystem or database performance in 7+ years), and no real understanding of Fractal Trees. I'm glad it's Open Source, however, and thanks for the pointers.
  - leif 14y ago
    Dancing Trees are algorithmically the same as B+ trees, if I understand the wikipedia article correctly. With just a uniformly random workload with a large enough working set, one would behave pretty much exactly the same as a B+ tree.

andrewljohnson 14y ago

Oh what a world. A data structure should never be patentable - what's the difference between a data structure and a math formula? Both are just notations for reality, and can spring up in the minds of many disparate inventors. I'd really like to see TokuDB discuss its patents, why they have them, and what they intend to do with them. I'd like to see a page like that from every corporation on their website actually.

leif 14y ago
IANAL, but the patents are owned by the universities where the founders work, not by the company. I don't know if this makes you feel any better though.
reinhardt 14y ago
"A data structure should never be patentable - what's the difference between a data structure and a math formula? Both are just notations for reality, and can spring up in the minds of many disparate inventors." Can we please let this disingenuous argument die already? Yes, in theory they can spring up in many minds independently. In practice they rarely do unless they are trivial. If the alleged disparate inventors can prove they came up with it independently, fine; the onus is on them.
- andrewljohnson 14y ago
  In practice, independent invention happens all the time, and we end up with absurd patent lawsuits as a result.
  - reinhardt 14y ago
    AFAIK none of these ludicrous patents are about data structures, algorithms or math formulas.
    - Kalium 14y ago
      I find that somewhat difficult to accept, given that pretty much every single patent that touches software is ludicrous.