Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

TokuDB open sourced

tokutek.com

Post reply on HN
Print view View original

31–40 of 55 posts

Re: TokuDB open sourced

#31

Post by leif »

SwellJoe wrote: post #25
carterschonwald wrote: post #22

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).

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

Fractal Tree indexes are very different from Dancing Trees. See http://tokutek.com/what-is-a-fractal-tree for an overview, and I'd be happy to answer questions if you have them.

Re: TokuDB open sourced

#32

Post by leif »

mjn wrote: post #18
ritonlajoie wrote: post #12

Earlier quoted context omitted.

The site is down. What is great in this technology ?

The main technical underpinning (though note this isn't my area) seems to be basing indices on a particular improvement to B-trees, Cache-Oblivious Streaming B-Trees, which have some nice performance characteristics. I think what TokuDB calls "fractal trees" are just a catchier synonym. Here's an academic paper from a few years ago from some of the people involved: http://supertech.csail.mit.edu/papers/sbtree.pdf And…

We have some more descriptions of Fractal Tree Indexes at http://tokutek.com/what-is-a-fractal-tree, and I'm always happy to answer questions about it.

Re: TokuDB open sourced

#33

Post by bradleykuszmaul »

mjn wrote: post #28
carterschonwald wrote: post #26

Earlier quoted context omitted.

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!

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 es…

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)

Re: TokuDB open sourced

#34

Post by andrewljohnson »

carterschonwald wrote: post #22

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).

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.

Re: TokuDB open sourced

#36

Post by mjn »

bradleykuszmaul wrote: post #33
mjn wrote: post #28

Earlier quoted context omitted.

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 es…

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 part…

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-TOKUD... (ctrl+f "PATENT RIGHTS GRANT").

Re: TokuDB open sourced

#37

Post by leif »

andrewljohnson wrote: post #34
carterschonwald wrote: post #22

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).

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.

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.

Re: TokuDB open sourced

#38

Post by carterschonwald »

bradleykuszmaul wrote: post #33
mjn wrote: post #28

Earlier quoted context omitted.

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 es…

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 part…

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?

Re: TokuDB open sourced

#39

Post by SwellJoe »

leif wrote: post #31
SwellJoe wrote: post #25

Earlier quoted context omitted.

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

Fractal Tree indexes are very different from Dancing Trees. See http://tokutek.com/what-is-a-fractal-tree for an overview, and I'd be happy to answer questions if you have them.

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.

Re: TokuDB open sourced

#40

Post by reinhardt »

andrewljohnson wrote: post #34
carterschonwald wrote: post #22

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).

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.

"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.

Post reply on HN