If you're on mongo and interested in performance, take a look at tokumx. It's a drop in replacement for mongodb with a better storage engine. http://www.tokutek.com/2013/09/tokumx-vs-mongodb-in-memory-s...
2,312 karma · joined March 25, 2009
http://leifwalsh.com
Our compression technique is naive, you're right (but we don't decompress the whole 4MB for one single point query, as you may be thinking, we're a bit more sophisticated). We have some more ideas in the pipeline if we need them (basically a bunch of tricks you can play when you know the schema), but the fact remains that what we have right now is extremely effective and there isn't much incentive yet to finish off our smarter prototypes.
Let me be clear: in the worst case with a unique index, Fractal Tree indexes are the same speed as B-tree indexes. In most cases, they're far better. When you add in compression and agility, it really is "beat B-trees across the board."
A few users still point out annoyances here and there (like the location of files on disk, how certain metadata is presented at the MySQL level, dealing with corner cases in the query optimizer) that don't have to do with the data structure, but with the integration as a MySQL concept, and though these complaints are rare, they will eventually need to be addressed, and it's hard to find the manpower to address them immediately.
Part of this problem is that it just takes a long time to sand down all the rough little edges of a product, even though the core data structure is mature. Another part is educating people, changing expectations (for example, teaching people that unique indexes do have a higher cost than non-unique indexes), and generating better documentation. It's a slow process but we're confident that it's progressing and will continue. Recall that InnoDB, while broadly accepted as superior to MyISAM for many years before, only became the actual default engine in MySQL 5.5.
Yes, unique checks are bad. They make it perform as badly as a B-tree for unique inserts. There are sometimes ways around that but at some level if you aren't reading in the leaf node, you're going to be at a loss for some information. B-trees seem to have spoiled users into thinking uniqueness checks don't make inserts any more expensive, when in fact that's just because B-tree inserts are already that slow.
The log(N) performance of a B-tree is not just extremely hard to improve on (for searches), it's impossible to improve on. The lower bound for searching (in the DAM model) is log(N)/log(B), and B-trees meet that.
But B-trees are also log(N)/log(B) for insertions, which is, it turns out, pretty damn slow. There's an optimal trade-off curve between insertions and queries (the fastest data structure for insertions is to just log them, but that forces all queries to read all the data), and B-trees are on it, but there are many more interesting points on that curve.
There is a family of data structures that matches B-trees' performance on queries while blowing it completely out of the water for insertions. The COLA and Cache-Oblivious Streaming B-tree are where you'll find them in academia, and the implementation I work on has a very marketing-flavored name: the Fractal Tree. All that means is that we took the theory and started implementing it and came up with enough innovations in the implementation that it sort of needed a new name, but it's spiritually the same concept.
I've written a fair amount about this that I'll link to at the end, but here's a brief description so you don't think I'm making this all up.
Basically what we do is we take a B-tree and, on all the internal nodes, we stick large buffers that accumulate messages. Want to insert something? Just stick it in the root's buffer, you don't need to do any I/O to find the proper leaf node it needs to go in (yet). If the buffer's full, flush it down by taking all its messages, sorting them between the root's children, and putting messages in the buffers in the children. This flushing can cascade as you'd imagine, and splits and merges work about the same as in a B-tree.
So now what's the analysis?
Well, the tree has the same shape as a B-tree, so searches have to look at the same log(N) number of nodes (which in practice is almost always just 1 for the leaf node after cache hits on the internal nodes, both for B-trees and for Fractal Trees, but the asymptotic analysis also tells you they have the same query cost).
For insertions though, let's walk through the process. The tree has height log(N), which means that, for an insertion to get "fully inserted", meaning it reaches the leaf node and won't be flushed any more, it has to get flushed down log(N) times. And what's the cost to flush a buffer full of messages? That's just O(1) I/Os, for the parent and children (and in practice it's actually only 2 I/Os because you can just flush to a single child, not all of them). But a buffer flush does work for O(B) messages at once, so the amortized cost to flush a single message down one level is just O(1/B). Do that log(N) times, and the insertion cost is O(log(N)/B), which is in practice around 100x less expensive than the B-tree's O(log(N)/log(B)) insertion cost.
On top of this, while for B-trees you want small leaf nodes because you're going to be reading and writing them all the time, for Fractal Trees, since the goal is to get a lot done with each I/O, you actually want large leaves, on the order of a few megabytes each. This has two nice effects:
1) While range queries on a B-tree can slow down as the tree ages and the leaves start to get randomly placed on disk, range queries on a Fractal Tree stay fast because each time you do a disk seek, you get to read and report a few megabytes' worth of data. This basically solves the "B-tree fragmentation" problem that makes database users run optimize table, or vacuum, or reIndex() or compact() operations like madmen.
2) Compression algorithms (like zlib, our default) can compress large blocks of data much more effectively than they can compress small blocks. So InnoDB, which has small blocks like most B-trees, if you turn on compression, apart from eating CPU as it tries and fails and re-tries to compress your data to fit it into its block size, it'll only get at most about 4x compression. In contrast, TokuDB (our MySQL storage engine using Fractal Trees [4]) routinely gets 10-20x compression without breaking a sweat.
I have some blog posts about this [1] and [2], and our benchmarks page is [3]. We also have a version of MongoDB in which we've replaced all the storage code with Fractal Trees, we call it TokuMX [5]. Don't mind the marketing haze, it's all serious tech under the hood.
[1]: http://www.tokutek.com/2011/09/write-optimization-myths-comp...
[2]: http://www.tokutek.com/2011/10/write-optimization-myths-comp...
[3]: http://www.tokutek.com/resources/benchmarks/
Tokutek delivers next generation storage technology for the database world. We develop the open-source, high-performance Fractal Tree indexing library (http://github.com/Tokutek/ft-index) and its integration into MySQL as TokuDB (http://tokutek.com/tokudb-for-mysql) and into MongoDB as TokuMX (http://tokutek.com/tokumx-for-mongodb).
http://tokutek.com/careers (the QA position has been filled and will be taken off this page soon)
We are looking for a full-time Technical Support Engineer to join our product development team. This position interacts directly with customers, troubleshooting issues and working closely with engineering to resolve bugs. Ideal candidates have 5+ years experience in software support and a background in databases. The position reports directly to the VP of Engineering.
Responsibilities
- Work with customers, community users, and evaluators to resolve issues
- Create issue reproducers for internal test/fix process
- Identify areas of needed improvement in product features, usability, and documentation
- Participate in our ongoing development process improvements (CI, release engineering, etc.)
Requirements
- Experience using/testing relational databases (SQL, architecture, schema), MySQL is a plus
- Ability to work independently in an entrepreneurial, start-up environment
- Comfortable in Linux (usage and scripting)
- Excellent verbal and written communication skills
- Solid testing skills
Desirable
- Experience with MongoDB
- Application development skills (C, C++, Python, Perl, Java, Ruby, PHP)
Location: Lexington, MA
You're right, with a reliably performant engine you can get a lot more out of a single machine than a lot of people these days seem to think. That's part of our vision for TokuMX, to bring back a little bit of "scale up" potential to the NoSQL space.
Partitioning is often a bad idea because it messes with your queries. I don't know what's new about partitioning in InnoDB but I think it's generally a symptom of the over-use of B-trees, which don't try to do anything smart about random writes. The change buffer is a decent idea but it's just a stopgap, when you have enough data it doesn't make a dent any more. A better idea is to use a data structure that can handle lots of writes.
I have just started learning about Riak, and from what I understand, they need to do a query (so, a disk seek) on every insert (to calculate something with vector clocks), so they aren't actually using the write optimization that LevelDB's LSM-trees can provide. I don't actually think it should provide that fantastic performance, but I should admit I haven't run it yet. Maybe they're more interested in the compression LevelDB gives them.
Shameless plug time! http://www.tokutek.com/2011/09/write-optimization-myths-comp...
In any case what they seem to be measuring is a read-only, in memory workload, so this is not that impressive. IIRC, InnoDB has no trouble pulling off something like this.
Full-time testing/QA engineer. Use whatever you like to break our software in interesting ways. We want someone who can build out and own testing for the long term. MySQL and/or MongoDB experience would be great. C/C++ even better but definitely not necessary.
You'll be responsible for designing and implementing new test infrastructure for both correctness and performance, you'll be in direct contact with our VP of Engineering, Tim Callaghan, as well as most of us engineers.
We're a highly technical storage systems company, with two flagship products that share a highly-tuned core: TokuDB, a storage engine for MySQL, and TokuMX, a fork of MongoDB. We currently have 6 core engineers, plus Tim.
Email us at {leif,tim} at tokutek dot com.
Tell your friends!
For 1.0 we wanted to match mongodb feature-wise as broadly as possible.
However, fractal trees can handle multiple clustered indexes very well, and this extends to a few ideas I have for adding things to do sharding in what I think will be a much better way. It's a bit up in the air right now but I can tell you we plan to make some significant innovations here, and if you have experience you can share, you should email us and we can talk it over and maybe change what we end up doing.