In my recent travels, I’ve been speaking with database users at various meetups and trade shows worldwide. Very often, I got questions centering around the best use cases for our products, be it TokuDB, our MySQL storage engine, or, TokuMX, our distribution of MongoDB. Over 90% of the time, I responded Cloud, Big Data or both. You see, in the software industry we’re like kindergartners, we like things to fit into neat categories. If you know any software sales people, you’ll recognize this as a fitting analogy (at least in terms of energy and attention span), but I digress. This strategy helps allocate resources where they are most likely to make an impact, and, thus, optimize our return on investment. In this blog series, I’m going to go slightly against the grain and explain why the Fractal Tree makes databases work in these environments.

Before I get into more detail, let me …

Modern file systems are well equipped to deal with large writes. One area that remains challenging however is to efficiently write out “microdata”, such as metadata and small portions of large files, while showing good I/O utilization when the data is read back. This challenge is evident with mount options like “noatime” which disables updating file access time on reads. This kind of solution avoids the problem altogether. Another approach, delayed allocation, is meant to coalesce small writes in memory as long as possible before writing it out to disk. Filesystems like ext4 and Btrfs use delayed allocation to make a best-effort at reducing fragmentation and random I/O.

Isn’t there a way to fundamentally solve filesystem fragmentation and random I/O?

This week, I’ll be speaking at HotStorage 2012 in Boston. My talk …

Executive Summary

Fast indexing requires the leaves of a Fractal Tree® Index to be big. But some queries require the leaves to be small in order to get any reasonable performance. Basements nodes are our way to achieve these conflicting goals, and here I’ll explain how.

Big Leaves

On many occasions, we at Tokutek have pointed out that TokuDB is write optimized, which means TokuDB indexes data much faster than a B-tree solution such as InnoDB. As with any write-optimized data structure, Fractal Tree indexes need to bundle up lots of small writes into a few big writes. Otherwise, there’d be no way to beat a B-tree. So the question is, how big do the writes have to be?

Consider how long it takes to write k bytes to a disk. First, there is the seek time s, which we can assume to be independent of k. Next, once we’ve moved the disk head somewhere, we need to write the bytes, which …