April 16, 2009

Introduction to Tokutek

Tokutek has a paradoxical pitch: Tokutek writes data particularly quickly, and therefore you’re supposed to buy Tokutek for query-oriented uses. Highlights of the Tokutek story include:

Tokutek’s initial target market is the usual combination of clickstream/personalization/other network management. The idea is that many data warehouse technologies have trouble getting latency below, say, 15 seconds to 5 minutes, at least at very high update volumes. So if immediacy is more important than raw complex query performance, Tokutek’s performance profile could be attractive.

Tokutek’s core technology is something it’s named “fractal tree” indexing. The “fractal” part of the name is based on a kind of “self-similar at different size ranges” flavor to the scheme. But if I understood correctly, it doesn’t sound like much of a tree, in that it always goes root-branch-leaf, rather than ever going root-branch-branch-branch-leaf or whatever.

The basic idea is that (to a first approximation) there’s one index block each of length 1, 2, 4, 8, and so on. With each insert, blocks get emptied and filled, so that each block is either completely empty or completely full. (And each block is in a sorted state as soon as it’s filled.) This results in a huge amount of shuffling in RAM — where the shorter blocks live — but disk only gets touched for occasional orderly pre-sorted merges. Tricks are obviously needed to:

I have a plane to catch, so I’ll just post this much and stop. More later.


14 Responses to “Introduction to Tokutek”

  1. Tom Hotchkiss on April 16th, 2009 7:40 pm


    Thanks for the post and also thanks for the quote for our TokuDB press release – it was over the phone so mea culpa if we messed up the wording.



  2. Daniel Weinreb on April 17th, 2009 6:53 am

    Curt, may I rephrase your description slightly? The way I’d put it is: Tokutek’s technology is based on a fundamentally new index structure/algorithm. Many database experts thought that the B-tree was the ultimate best answer, but this new one has a huge advantage over ordinary B-trees: inserts are much, much faster. This is an impressive and fundamental new concept, widely applicable.

    In a conventional relational database system, you have a tradeoff. Adding more indexes makes queries (that use whatever columns are indexed) faster, but it makes updates slower because you have to update all those indexes (and write back the pages they’re stored on). Tokutek’s basic idea is that now you’re free to put in as many indexes as you want (hence the reason it’s good for query-orinted uses), because the indexes do not slow down writes the way ordinary B-tree indexes would.

    The “fractal tree” algorithm has been published. It’s based on the “Cache Oblivious” concept; see Wikipedia, which in turn points you to a nice explanation by Prof. Eric Demaine of MIT. The “fractal tree” index papers are pointed to from http://supertech.csail.mit.edu/cacheObliviousBTree.html. Note that the name “fractal tree” was introduced by Tokutek and is not used in these papers. They use names like “cache-oblivious search trees”, just so you know that that’t the thing we’re talking about. “Fractal Tree”, in my opinion, is a reasonable name from a technical point of view and better from a marketing point of view. Naturally, Tokutek and the inventors have patents pending. Bradley Kuszmaul of MIT, Michael Bender of Stony Brook U., and Martin Farach-Colton of Rutgers are the inventors.

    It seems to me that doing ACID transactions will still incur costs for committing the index changes to disk, if you implement it the most obvious way. Presumably they will implement it more cleverly than the obvious one. This is not discussed in the academic papers. I speculate that this is why they have not yet implemented ACID — it’s not as easy as just following the published methods. But that’s just a speculation.

  3. Seth Grimes on April 17th, 2009 8:21 am

    Dan Weinreb, you’re restating several years worth of justification for non-b-tree approaches to management of data for for analytical use put forward by various academics and software companies, in particular column-store backers. No problem there. I just wanted to point it out.

    Is reliance on a “cache-oblivious dynamic search tree as an alternative to the ubiquitious [sic] B-tree” (quote from the paper you cite) meant to appeal to analytics users? B-trees are good for random-access retrieval of relatively small numbers of records and the implication of the term “search tree” is that it would be similarly suited.

    If the goal is fast data availability, why not look at a streaming-data engine that caches good volumes of recent data in memory? Or is the advantage here that this software is a MySQL engine?

  4. Jerome on April 17th, 2009 8:33 am

    Curt, are they a client of yours?

  5. Curt Monash on April 17th, 2009 8:59 am


    Not at this time. But I took pity on them and did a favor anyway.

  6. Curt Monash on April 17th, 2009 9:02 am


    Nothing that comes to mind is faster than a streaming engine integrated with a DBMS. But for use cases where Tokutek does the job, it could be simpler/cheaper than that approach.

  7. Jerome on April 17th, 2009 9:39 am

    Ouch that hurts 🙂

  8. Daniel Weinreb on April 17th, 2009 10:41 am

    @Seth: Sure, a lot of what I wrote is just background, in order to provide the context to explain about Tokutek’s index. I intended it for readers with less experience than you.

    I don’t know whether it’s aimed at analytics users. I have a tendency to think in terms of OLTP, since I am working on an airline reservation system.

    As you say, the fact that it has a MySQL front end may mean that they have in mind LAMP-stack web sites, Drupal sites, etc. I don’t know. And also as you say, streaming technology is good for caching recenbt data in memory. I don’t know whether they are aiming at applications with that property.

    As Pror. Stonebraker says these days, one size does not fit all. There are many useful architectures now, and for high performance you have to be careful to match the architecture to the use cases you care about.

    ObjectStore, which I co-architected, was aimed at C++ programmer who wanted language transparency, sharing, ability to take advantage of powerful client-side computers, operating on data with good spatial and temporal locality, and not doing complex queries. (There were plenty of customers who were happy with that and Object Design was very successful.) That’s another example of a different (in some ways) DBMS architecture.

  9. Calpont update — you read it here first! | DBMS2 -- DataBase Management System Services on April 20th, 2009 3:15 am

    […] Calpont plans to offer a MySQL storage engine for analytic database processing. Thus, Calpont will compete with Infobright, Kickfire, and perhaps Tokutek. […]

  10. Some NoSQL links | DBMS2 -- DataBase Management System Services on March 13th, 2010 12:58 pm

    […] hand, he praised or at least expressed hope for a variety of MySQL-related technologies, including Tokutek’s TokuDB and Continuent’s […]

  11. More on NoSQL and HVSP (or OLRP) | DBMS 2 : DataBase Management System Services on August 26th, 2010 5:10 am

    […] same site says Tokutek finally was able to raise some VC. […]

  12. Notes and comments — October 31, 2012 | DBMS 2 : DataBase Management System Services on October 31st, 2012 4:08 am

    […] Looking back for a couple of examples even if you’ve never heard of him before, I see that Dan ‘s 2009 comment on Tokutek is still interesting today, and so is a post on his own blog disagreeing with some of my choices in […]

  13. NewSQL thoughts | DBMS 2 : DataBase Management System Services on January 5th, 2013 3:43 pm

    […] vendors I’ve written about in the past include Akiban, Tokutek, CodeFutures (dbShards), Clustrix, Schooner (Membrain), VoltDB, ScaleBase, and ScaleDB, with […]

  14. Tokutek update | DBMS 2 : DataBase Management System Services on July 30th, 2013 3:45 pm

    […] all been true since I first wrote about Tokutek and TokuDB in 2009. However, TokuDB’s technical details have changed. In particular, Tokutek has deemphasized […]

Leave a Reply

Feed: DBMS (database management system), DW (data warehousing), BI (business intelligence), and analytics technology Subscribe to the Monash Research feed via RSS or email:


Search our blogs and white papers

Monash Research blogs

User consulting

Building a short list? Refining your strategic plan? We can help.

Vendor advisory

We tell vendors what's happening -- and, more important, what they should do about it.

Monash Research highlights

Learn about white papers, webcasts, and blog highlights, by RSS or email.