Hacker News Reader

Comment by carterschonwald | Hacker News Reader

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

View on HN

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.

The onus placed on them is too great when it appears as a dilemma between a yearly $X0,000 extortion or one-time $X,000,000 lawsuit.

Fair point, though the lawsuit cost insanity is hardly limited to patents.

That's absolutely true, it's far too easy to get in a situation like that even without considering patent law. I just think patents make the scatter-gun approach too accesible, and the damages are far too high. Software doesn't need to protect R&D costs on FDA studies and years of testing. If the goal is to foster innovation, either software patents should be abolished, or there should be very reasonable limits to damages, or there should be a simple and inexpensive way to trigger a review that invalidates ridiculously obvious patents such as "scan-to-email" and friends.

In practice, independent invention happens all the time, and we end up with absurd patent lawsuits as a result.

AFAIK none of these ludicrous patents are about data structures, algorithms or math formulas.

I find that somewhat difficult to accept, given that pretty much every single patent that touches software is ludicrous.

Can someone in the know elaborate on the current state of US patent law here? And what exactly TokuDB / the universities hold a patent on?

Curious outsider here, and understand that all IANAL caveats apply.

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.

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

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

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)

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

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?

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?

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.

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.

Reply on news.ycombinator.com