iiBench measures the rate at which a database can insert new rows while maintaining several secondary indexes. We ran this for 1 billion rows with TokuDB and InnoDB starting last week, right after we launched TokuDB v5.2. While TokuDB completed it in 15 hours, InnoDB took 7 days.

The results are shown below. At the end of the test, TokuDB’s insertion rate remained at 17,028 inserts/second whereas InnoDB had dropped to 1,050 inserts/second. That is a difference of over 16x. Our complete set of benchmarks for TokuDB v5.2 can be found here.

We developed the iiBench benchmark to measure performance for a use case that occurs commonly in production applications, such as online advertising, social media, and network management.

iiBench simulates a pattern of usage for always-on applications that:

• Require fast query performance and hence require indexes
• Have high data insert rates
• Cannot wait for offline batch processing and hence require the indexes be maintained as data comes in

Note that iiBench was created as an open-source benchmark, which allows others to freely use it, extend it, and contribute their changes back. We originally unveiled the benchmark in the context of a challenge issued at the 2008 OpenSQL camp. Since then, iiBench has been downloaded and used many times, and ported by the community (in this case, Mark Callaghan) to a Python Script.

Please let us know any feedback you have on iiBench. For additional information on…

• iibench overview click here
• TokuDB version 5.2 Overview click here
• TokuDB version 5.2 Performance, including iibench, SysBench, Compression, and TPCC-like, click here

 
Thanks again to Sheeri Cabral  for having me at the Boston MySQL Meetup on Monday for the talk on “Fractal Tree^® Indexes – Theoretical Overview and Customer Use Cases.” The crowd was very interactive, and I appreciated that over 50 people signed up for the event and left some very positive comments and reviews.

In addition, the conversation spilled over late into the night as we made our way over to nearby Mead Hall afterwards for a few drinks, some food, and to continue the discussion.

The presentation is available here.

As a brief overview – most databases employ B-trees to achieve a good tradeoff between the ability to update data quickly and to search it quickly. It turns out that B-trees are far from the optimum in this tradeoff space. This led to the development at MIT, Rutgers and Stony Brook of Fractal Tree indexes. Fractal Tree indexes improve MySQL^® scalability and query performance by allowing greater insertion rates, supporting rich indexing and offering efficient compression. They can also eliminate operational headaches such as dump/reloads, inflexible schemas and partitions.

The presentation provides an overview on how Fractal Tree indexes work, and then gets into some specific product features, benchmarks, and customer use cases that show where people have deployed Fractal Tree indexes via the TokuDB^® storage engine.
 

There are about a gazillion FAQs and HOWTOs out there that talk about XFS configuration, RAID IO alignment, and mount point options.  I wanted to try to put some of that information together in a condensed and simplified format that will work for the majority of use cases.  This is not meant to cover every single tuning option, but rather to cover the important bases in a simple and easy to understand way.

Let’s say you have a server with standard hardware RAID setup running conventional HDDs.

RAID setup

For the sake of simplicity you create one single RAID logical volume that covers all your available drives.  This is the easiest setup to configure and maintain and is the best choice for operability in the majority of normal configurations.  Are there ways to squeeze more performance out of a server by dividing the logical volumes: perhaps, but it requires a lot of fiddling and custom tuning to accomplish.

There are plenty of other posts out there that discuss RAID minutia.  Make sure you cover the following:

• RAID type (usually 5 or 1+0)
• RAID stripe size
• BBU enabled with Write-back cache only
• No read cache or read-ahead
• No drive write cache enabled

Partitioning

You want to run only MySQL on this box, and you want to ensure your MySQL datadir is separated from the OS in case you ever want to upgrade the OS, but otherwise keep it simple.  My suggestion?  Plan on allocating partitions roughly as follows, based on your available drive space and keeping in mind future growth.

• 8-16G for Swap –
• 10-20G for the OS (/)
• Possibly 10G+ for /tmp  (note you could also point mysql’s tmpdir elsewhere)
• Everything else for MySQL (/mnt/data or similar):  (sym-link /var/lib/mysql into here when you setup mysql)

Are there alternatives?  Yes.  Can you have separate partitions for Innodb log volumes, etc.?  Sure.  Is it work doing much more than this most of the time?  I’d argue not until you’re sure you are I/O bound and need to squeeze every last ounce of performance from the box.  Fiddling with how to allocate drives and drive space from partition to partition is a lot of operational work which should be spent only when needed.

Aligning the Partitions

#fdisk -ul

Disk /dev/sda: 438.5 GB, 438489317376 bytes
255 heads, 63 sectors/track, 53309 cylinders, total 856424448 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00051fe9

   Device Boot      Start         End      Blocks   Id  System
/dev/sda1            2048     7813119     3905536   82  Linux swap / Solaris
Partition 1 does not end on cylinder boundary.
/dev/sda2   *     7813120    27344895     9765888   83  Linux
/dev/sda3        27344896   856422399   414538752   83  Linux

# mkfs.xfs -d su=64k,sw=4 /dev/sda3
meta-data=/dev/sda3              isize=256    agcount=4, agsize=25908656 blks
         =                       sectsz=512   attr=2
data     =                       bsize=4096   blocks=103634624, imaxpct=25
         =                       sunit=16     swidth=64 blks
naming   =version 2              bsize=4096   ascii-ci=0
log      =internal log           bsize=4096   blocks=50608, version=2
         =                       sectsz=512   sunit=16 blks, lazy-count=1
realtime =none                   extsz=4096   blocks=0, rtextents=0

/var/lib/mysql           xfs     nobarrier,noatime,nodiratime

echo noop > /sys/block/sda/queue/scheduler   # update the scheduler in realtime

kernel /boot/vmlinuz-2.6.18-53.el5 ro root=LABEL=/ noapic acpi=off rhgb quiet notsc elevator=noop

Limelight Networks

Issue addressed: Managing metadata at exabyte scale

Delivering Agile Storage in the Cloud with Billions of Assets

The Company: Founded in 2001, Limelight Networks, Inc (NASDAQ: LLNW) is an Internet platform and services company that integrates the most business-critical parts of the online content value chain. Limelight’s cloud-based services enable customers to profit from the shift of content and advertising to the online world, from the explosive growth of mobile and connected devices, and from the migration of IT applications and services to the cloud. More than 1,800 customers worldwide use Limelight’s massively scalable services to better engage audiences, optimize advertising, manage and monetize digital assets and build stronger customer relationships.

The Challenge: Limelight designed a unique high-availability Agile Storage cloud service, which gives users control over how and where their content is stored by offering massive storage capacity, extreme flexibility for setting business rules and replication policies, with localized ingest and content access around the globe. The service provides vast storage volumes for large libraries of any type of digital asset.

The system was designed for a total capacity on the order of exabytes worldwide and is presently capable of supporting over 100 billion assets. To succeed with the platform, Limelight needed a storage engine that could handle insertion and query performance on large tables and scale as the database grew, and it needed to accomplish this in a cost effective manner. “This vast amount of information brings with it a rich and large amount of metadata around policies, file names, storage pointers, asset registries, users, and groups” according to Wylie Swanson, VP Technology, Cloud Services at Limelight. “Ensuring the metadata could be managed in an efficient and flexible way was critical to the design of the offering.”

A number of options Limelight had considered were insufficient. These included:

InnoDB – Despite familiarity with the MySQL storage engine InnoDB, Limelight found that it didn’t meet the project’s requirements. According to Swanson “the minute you run out of RAM for indexing, InnoDB performance starts to fall apart. We were seeing this occur at 50M – 100M rows. You can shard content, of course, but that feeds back into application and management complexity. Moreover, not all of our database schema is amenable to simple sharding methods.”

RAM Expansion – “While high powered servers and more RAM can somewhat extend the size of a database that InnoDB can handle, doing so is ultimately cost prohibitive” according to Swanson. “To support our system using more traditional database technology, we would have had to purchase terabytes of RAM for our servers.”

Schooner – “Schooner offered performance improvements, but was too expensive. In addition, it didn’t look like it could achieve the performance levels of our commodity servers using TokuDB in our application” according to Swanson.

The Solution: Limelight Agile Storage uses TokuDB for metadata management

Limelight needed a system that could access the database remotely with high availability, flexibility, performance and capacity. Limelight chose MariaDB for components of the platform. To satisfy the need for high availability, the Agile Storage Service uses a high availability Linux cluster to manage the metadata.

For the requirements of flexibility, performance and capacity, TokuDB was an unparalleled choice. “TokuDB provides incredible scaling, keeping a high insert rate throughout as the metadata repository continues to grow” noted Swanson. “This is crucial to keeping up with high-ingest points that are spread all around the world. TokuDB also provides the underpinning for a system that supports arbitrary queries – for example which policies are expired on which assets.”

In addition, Limelight benefited from other TokuDB features such as high data compression yielding a savings of 65% of disk capacity for the meta-directory components.

The Benefits:

Scale: The Agile Storage platform was designed to scale to exabytes of data. Cost effectively scaling compute power, storage, and software was critical to the design. “We don’t know how we could have gotten to our required scale and price points for our meta-directory components without TokuDB” according to Swanson.

Ease of Implementation: Swanson noted that “TokuDB worked seamlessly from the start with MariaDB. Installing it was quick and simple, and we were up and running in a few hours and it worked out-of-the-box with default settings, so that we could focus on maximizing the performance of our platform, not our databases.”

Compression: In addition to fast insertion rates, TokuDB provides data compression levels that are much higher than InnoDB’s. TokuDB’s advanced compression technology reduced Limelight’s disk space requirements by roughly 3x, from over 1 TB down to about 350 GB.

At next month’s Boston MySQL Meetup, I will give a talk: “Fractal Tree Indexes – Theoretical Overview and Customer Use Cases.” The meetup is 7 pm Monday, January 9th, 2012, and will be held at MIT Building E51 Room 337e (corner of Ames & Amherst St, Cambridge, MA). Thanks to host Sheeri Cabral for the invitation.

Most databases employ B-trees to achieve a good tradeoff between the ability to update data quickly and to search it quickly. It turns out that B-trees are far from the optimum in this tradeoff space. This led to the development at MIT, Rutgers and Stony Brook of Fractal Tree^® indexes. Fractal Tree indexes improve MySQL^® scalability and query performance by allowing greater insertion rates, supporting rich indexing and offering efficient compression. They can also eliminate operational headaches such as dump/reloads, inflexible schemas and partitions.

I’ll give an overview on how Fractal Tree indexes work, and then get into some specific product features, benchmarks, and customer use cases that show where people have deployed Fractal Tree indexes via the TokuDB^® storage engine.

I hope to see you there!

As a storage engine developer, I am excited for MySQL 5.6. Looking at http://dev.mysql.com/tech-resources/articles/whats-new-in-mysql-5.6.html, there has been plenty of work done to improve the performance of reads in MySQL for all storage engines (provided they take advantage of the new APIs).

What would be great to add is API improvements to increase the performance of writes, and more specifically, updates. For many applications that perform updates, such as applications that do click counting or impression counting, there are significant opportunities for improving write performance.

Take the following example of click counting (or impression counting). You have a website and want to save the number of times links on your website have been clicked. Your table may look something like:


create table num_clicks( link_id int, num_clicks int);


To update the number of clicks, you do something like:


insert into num_clicks (LINK_ID, 1) on duplicate key update set num_clicks=num_clicks+1;


With MySQL as it currently works, this is slower than it needs to be, as I explained here. At a high level, the reason is that MySQL forces the storage engine to check in the table if a value exists for LINK_ID. If a row is returned, MySQL performs the increment away from the storage engine, and passes a new row to the storage engine for an update. The check incurs a disk seek, which is very costly in terms of latency. Disks can do only hundreds of seeks per second. Furthermore, NoSQL solutions based on B-trees are similarly limited and can’t be significantly accelerated because updates incur disk I/O.

However, with some changes to MySQL, a storage engine can take advantage of this knowledge to improve its algorithms. All that’s needed is for the storage engine to know that the user wants to perform an insert or to perform this particular update, as opposed to getting individual handler calls of write_row, index_read, and update_row (which is the current design). Hence, what’s needed is a way for the storage engine layer to be able to apply updates on its own.

This change can help all storage engines. Although I am not an expert in MySQL Cluster, I imagine reducing these individual handler calls also helps MySQL Cluster avoid network hops to retrieve information. For in-memory databases, performance may increase due to reducing the number of calls made by the handler. InnoDB can potentially use its insertion buffer to store the “insert … on duplicate key update” operation, thereby giving the operation the same boost insertions into secondary keys get. For TokuDB, we estimate that these types of updates aided by this additional information could run much faster. In future posts, I will expand on how we think TokuDB can do this.

Many database management tasks become difficult as you move from millions of rows and gigabytes of data to billions of rows and terabytes of data. Such tasks include ingesting data while maintaining indexes; changing schemas without downtime; and supporting connections, replication, and backup. For some scaling problems (connections and replication), MySQL^® is better than most of the competition. For others, such as indexing, schema changes, and backup, MySQL has typically been harder to use. Fortunately, the tasks MySQL does well are in its core, whereas the tasks that are more difficult can be solved with storage engine plug-ins.

I recently gave a talk at Oracle Open World 11, a copy of which can be found here. This presentation discusses how MySQL’s storage engines have recently made dramatic progress in large database manageability.

A list of other MySQL talks can be found in a handy list that Ronald Bradford put together here. For those who want to learn more about TokuDB^®, we have an upcoming webinar here.

I’ve been benchmarking and testing TokuDB for a few months now. One goal of benchmarking is to understand what is limiting the performance of a particular configuration. I frequently use “show engine [innodb/tokudb] status;” from within the MySQL command line client as part of my research.

As I run most of my benchmarks on InnoDB as well as TokuDB, I noticed that there are significant differences in the way each present status information. InnoDB returns a single row, with various sections and carriage returns to maintain readability. In contrast, TokuDB presents one piece of status information per row (currently 139 rows as of TokuDB v5.0.5). This is an important distinction if you want to parse, compare, or store discrete status values. Here is sample output from each engine. I’ve cut out portions of each to maintain readability.

InnoDB plugin v1.0.13

mysql> show engine innodb status;
+--------+------+-------------------------------------------+
| Type   | Name | Status                                    +
+--------+------+-------------------------------------------+
| InnoDB |      |
=====================================
111018  7:05:21 INNODB MONITOR OUTPUT
=====================================
Per second averages calculated from the last 59 seconds
-----------------
BACKGROUND THREAD
-----------------
srv_master_thread log flush and writes: 1
--------
FILE I/O
--------
I/O thread 1 state: waiting for i/o request (log thread)
I/O thread 2 state: waiting for i/o request (read thread)
0.00 reads/s, 0.00 creates/s, 0.00 writes/s
No buffer pool page gets since the last printout

  <<**** MANY LINES REMOVED FOR READABILITY ****>>

Pages read ahead 0.00/s, evicted without access 0.00/s
LRU len: 15, unzip_LRU len: 0
I/O sum[0]:cur[0], unzip sum[0]:cur[0]
--------------
ROW OPERATIONS
--------------
0 queries inside InnoDB, 0 queries in queue
1 read views open inside InnoDB
Number of rows inserted 0, updated 0, deleted 0, read 0
----------------------------
END OF INNODB MONITOR OUTPUT
============================
+--------+------+-------------------------------------------+
1 row in set (0.00 sec)

TokuDB v5.0.5

mysql> show engine tokudb status;
+--------+------+-------------------------------------------+
| Type   | Name | Status                                    +
+--------+------+-------------------------------------------+
| TokuDB | checkpoint period                       | 60     |
| TokuDB | checkpoint status code (0 = idle)       | 0      |
| TokuDB | last complete checkpoint LSN            | 196    |
| TokuDB | txn oldest live                         | 0      |
| TokuDB | next LSN                                | 201    |

  <<**** MANY LINES REMOVED FOR READABILITY ****>>

| TokuDB | original version                        | 14     |
| TokuDB | version at startup                      | 14     |
| TokuDB | last LSN of version 13                  | 0      |
| TokuDB | malloc count                            | 482    |
| TokuDB | free count                              | 322    |
| TokuDB | realloc count                           | 6      |
| TokuDB | malloc fail                             | 0      |
| TokuDB | realloc fail                            | 0      |
+--------+------+-------------------------------------------+
139 rows in set (0.00 sec)

MySQL provides 3 columns for the results of show engine status: Type, Name, and Status. I’m not sure why InnoDB pushes all output into the Status column of a single row, maybe there are historical reasons. Our implementation uses one Name / Status pair per row, which is much easier to read, parse, or sort.

One of our developers created a simple Python script that polls MySQL to get the current TokuDB engine status, compares the values to the last values read, and outputs the delta of the two. Pretty handy when trying to understand what the storage engine is up to. The script is named “tokustat.py”, but I alias it as tokutop.

The source code of the python script is available via this link. Because our engine status information is so well organized, it is only 86 lines of code (and could probably be much smaller).

I’d be interested to hear how others are reading and parsing the status of other engines, email me at tim@tokutek.com.

We were happy to see a lot of folks from Japan on Twitter this weekend having a discussion about MySQL and Tokutek. While we always endeavor to explain ourselves as simply as possible, hearing what users and peers have to say and ask in their native language is very helpful. Here is a sampling of several of the 30+ tweets and re-tweets (translations courtesy of a colleague I know from frequent past visits to Tokyo and Yokohama):

.

First, @frsyuki provided a general overview:

“TokuDB” 新種のMySQLストレージエンジン。INSERTが20〜80倍ほど速い、パーティションなしで数TBのデータを突っ込める、MVCCサポートなど。Fractal Treeというアルゴリズムを実装しているらしい。http://www.tokutek.com/

(Translated: TokuDB is a new type MySQL Storage Engine.  The main features are a) INSERT speed is 20-80times faster, b) load several TB data without partitions and c) support MVCC.  http://www.tokutek.com/)

.

Next, @mtanda remarked on TokuDB v5.0′s addition of Hot Schema Changes:

TokuDBの説明にHot Schema Changesとある。これもけっこう便利そう。 http://ow.ly/5LtVr

(Translated:  I found Hot Schema Changes in the explanation of TokuDB.  It sounds very convenient. http://ow.ly/5LtVr)

.

We heard how one of our founders gave hope for theorists from  @_eiko_ :

@frsyuki TokuDB開発者のKuszmaulさんは、以前はAkamaiのネットワークのアーキテクト、古くはThinking Machines CM-5というスパコンのネットワーク開発者。理論やさんの活躍の場って多彩。

(Translated: TokuDB developer “Kuszmaul” used to work as the network architect in Akamai, and as the network developer of the supercomputer called Thinking Machines CM-5 in the past.  There are many opportunities for a “theorist”. )

.

All this chatter got the attention of some new folks such as @KrdLab:

Fractal Tree というものがあるんですね．知らんかった. http://bit.ly/pbUS1Q

(Translated: I did not know things like a “Fractal Tree” exists…. http://bit.ly/pbUS1Q )

.

Finally, @repeatedly could not have summed it up better:

これからの時代はB-TreeではなくてFractal-Treeなのか？ > http://en.wikipedia.org/wiki/TokuDB#Fractal_Tree_Indexes

(Translated: Time flies so fast… it appears the trend has now gone from B-Trees to Fractal-Trees? http://en.wikipedia.org/wiki/TokuDB#Fractal_Tree_Indexes)

.

So, for those reading from Japan, いらっしゃいませ (welcome).

To address some of the questions and comments raised above:

• @frsyuki – Here is additional information on performance and partitioning
• @mtanda - You may find these blog posts on Hot Schema Changes helpful — Hot Indexing, HCAD Part I and II
• @KrdLab - A good overview presentation on Fractal Tree™ indexing can be found here.
• @repeatedly – Yes, many people are seeing the benefits. For some commentary, see here.

In general, even if we are limited today to responding only in English, we are always happy to try to explain the benefits of Fractal Tree™ indexing , work with you to help select optimal indexes, and troubleshoot when it seems like TokuDB isn’t performing as well as expected. Please drop us a line anytime, either via e-mail or twitter.

Thanks again to Sadayuki for kicking off this Twitter stream. Next time you are in Boston, or I am in Japan, the first Suntory is on me.

Unless you are Aston Kutcher (@aplusk), or one of his Hollywood buddies, you don’t need to read any further. Allow me to explain…

Over the weekend, we launched our new website. This type of announcement used to be interesting in the high-tech world. I heard Kara Swisher of the WSJ’s All things D speak at a MassTLC event in May.  She admitted back in the 1990s, when the web was just getting into high gear, that a new website from an interesting company might actually get some coverage. Not anymore.

I’ve also been told at all the SEO classes I’ve taken that as much as marketing folks sweat over every detail, link, font and color, it all doesn’t matter. And as far as Google is concerned, your site could be all in 5 point courier grey font on a black background – as long as you have the right keywords and lots of links to you, you’ll be ranked well and the right people could find you.

So, who can I share my excitement with over our new site? It occurred to me this weekend – Ashton Kutcher and his Hollywood pals!

With Ashton’s recent investment in MemSQL maybe Hollywood is finally getting hip to databases! If that’s the case, then Ashton, do we have a site for you! The all new Tokutek.com brings you:

• A Technology Overview section packed with such insight on Fractal Tree ™ indexing that we can guarantee you’ll impress Demi (@mrskutcher) with your new-found knowledge
• The latest updates on the database space right on the home page, ready for you to instantly retweet to your 7M+ Twitter followers
• The chance to practice “getting into character” for a Hollywood database movie with our opening for a support engineer
• A shared passion for snowboarding
• The opportunity to see how databases have evolved since That 70s Show, the time period when the oft-used but very outdated B-Trees were first described.

We hope you’ll swing by and check us out!