Toru Maesaka

Disclaimer: This post is based on HEAP/MyISAM’s sourcecode in Drizzle.

Here are my brief notes on investigating how index keys are generated in HEAP and MyISAM. I lurked through these because I’ve started preparing for decent index support in BlitzDB. I also wrote this to assist my biological memory for later grepping (I have terrible memory for names). I’m only going to cover key generation on write in this post. Otherwise this post is going to be massive.

HEAP Engine

The index structure of HEAP can be either BTREE or HASH (in MySQL doc terms). Like other engines HEAP has a structure for keeping Key definition (parts, type, logic and etc). This structure is called HP_KEYDEF and it contains function pointers for write, delete, and getting the length of the key. These function pointers are assigned to at table creation or when the table is opened. The assigned function depends on the data structure of the index and it can be either of the following:

BTREE

• hp_rb_write_key()
• hp_rb_delete_key()

HASH

• hp_write_key()
• hp_delete_key()

As for get_key_length(), either of the following functions are used for both data structures.

• hp_rb_var_key_length()
• hp_rb_null_key_length()
• hp_rb_key_length()

When writing a row to the tree, HEAP writes to the index using a key generated by hp_rb_make_key(). Note that it does not use this for the hash index. The generated key is populated inside ‘recbuffer’ in HEAP’s handler object (HP_INFO structure).

From my understanding, it loops through the key segments (I suspect it is similar the internal KEY_PART_INFO structure) and appropriately copies each key field value to the output buffer. By meaning “appropriately” it respects the characteristics of the data type when packing the buffer. For example, for a variable length field, it will only copy the actual data and not the max possible size of it. The final byte that is copied to the buffer is the address of the chunk where the record lives.

MyISAM Engine

The upper layer of key handling in MyISAM looks somewhat similar to HEAP so you can really tell that it was written by the same people. Things are nicely wrapped together by the MYISAM_SHARE structure so it’s relatively easy to follow. BlitzDB has a class called BlitzShare for the same purpose (This is based off Archive Engine’s ArchiveShare class).

Like HEAP, MyISAM has a structure for individual key definition called MI_KEYDEF (it’s defined in myisam.h). There are more function pointers in this structure than HEAP.

• bin_search()
• get_key()
• pack_key()
• store_key()
• ck_insert()
• ck_delete()

In Drizzle, _mi_ck_write() is assigned to ck_insert() which is the entry point to writing a MyISAM index. The key that MyISAM uses to write to the index is generated by _mi_make_key(). Like HEAP, it will loop through the key segments and pack the relevant fields accordingly to the characteristic of the data type. The output buffer belongs to MyISAM’s hander (lastkey2).

From Here

I’ve actually written a naive key generator for BlitzDB already based on Drizzle/MySQL’s internal KEY_PART_INFO array. It seems to be working on EXACT MATCH but I still need to implement an index scanner which looks much harder to pull off than a table scanner. What I’m really worried about is supporting composite indexes (namely reading/searching on it) but hopefully I’ll understand how this area of the storage system works soon.

Toru Maesaka drizzle, knowledge, oss drizzle, mysql, storage

FURTHER UPDATE: Further thoughts on BlitzDB’s Index Handling

My open source friends might have noticed that I’ve been working quite a bit on BlitzDB lately. To tell the truth, I had a hidden goal to get Version-1 done by Christmas. Unfortunately it doesn’t look like I can reach that goal. However, looking at the brightside I got a lot done in the past few weeks so allow me to “journal” it in this blog post.

Agony of Knowing

The more I understood Drizzle’s storage mechanism and Tokyo Cabinet’s internals, the more I disliked what I previously had. This led me to spending quite a bit of time rewriting BlitzDB’s codebase. I was using pthread’s rwlock for concurrency control but I decided to design and write BlitzDB’s own lock mechanism to get the best out of TC (in terms of concurrency). I also rewrote the entire table scan code which is something you’d hope won’t be executed that often (people should use indexes!) but needless to say, it’s an important component of a relational storage engine so I’ve put in a lot of effort there.

Rewriting the Table Scanner

In the process of rewriting the table scanner, Jay Pipes’ gave me a fantastic advise on using Drizzle’s internal atomic type (drizzled::atomics). He gave me this advise because he noticed that my atomic ID generator was securing atomicity with pthread’s mutex. It is debatable that this mutex was only enabled for only few CPU instructions but the philosophy of using the most efficient method on the platform where BlitzDB is to be run was appealing enough for me to use drizzled::atomics. Mikio did some experiments on this and found that in a competitive/congested environment, using the compiler’s builtin function can gain you 3x throughput.

Hacking on Index Support

I’ve finally started hacking on index support and I just finished supporting basic operations on a primary key. By design, BlitzDB’s index is a dense clustered b+tree but in the first release I am going to limit PK to only be a HASH index. This is because I want BlitzDB to treat all PKs as direct keys inside the data dictionary (hash database where the actual rows are stored). So in other words, I want people to use PK for “needle in a haystack” like queries only. An example of a needle in a haystack like query is:

SELECT * FROM TABLE WHERE primary_key_column = whatever;

Saying that, I don’t like to force people to do things the way I like so I plan on providing best of both worlds by supporting both data structures for PKs in Version-2:

CREATE TABLE t1 (id int, PRIMARY KEY(id) USING btree) ENGINE=blitzdb;
CREATE TABLE t1 (id int, PRIMARY KEY(id) USING hash) ENGINE=blitzdb;

BlitzDB’s default configuration will use PK as a “direct” data dictionary index. If you wish to do range queries on PK, the solution is to create a index on the PK column.

Primary Key lookup Performance

So, how does my implementation perform? Here’s a quick benchmark with a test-run that randomly fetches 100 thousand rows from a BlitzDB table with 1 million rows. This is the table I used:

CREATE TABLE t1 (id int PRIMARY KEY, a int, b int) ENGINE=blitzdb;

and the query looks like this:

SELECT * FROM t1 WHERE id = random_number_under_one_million;

The hardware I used is the following commodity server: Intel Quad Xeon E5345 (2x4MB L2 cache), 8GB Memory, 500GB SATA II. Unfortunately I could not prepare a standalone client server today so both the server and the test program were run on the same machine. Yeah… this sucks so I can’t claim that this benchmark is 100% creditable.

Here is the result I obtained from skyload. Please only view it as a guideline to BlitzDB’s lookup performance. I’ll do a proper benchmark with the Drizzle Community and publish it after I get Version-1 released.

[ READ LOAD EMULATION RESULT ]
  SQL File               : 100k_select.sql
  Concurrent Connections : 1
  Task Completion Time   : 5.88856 secs
  Number of Queries:     : 100000
  Number of Test Runs:   : 1
 
[ READ LOAD EMULATION RESULT ]
  SQL File               : 100k_select.sql
  Concurrent Connections : 2
  Task Completion Time   : 6.94474 secs
  Number of Queries:     : 100000
  Number of Test Runs:   : 1
 
[ READ LOAD EMULATION RESULT ]
  SQL File               : 100k_select.sql
  Concurrent Connections : 4
  Task Completion Time   : 7.04455 secs
  Number of Queries:     : 100000
  Number of Test Runs:   : 1

As you can see, “needle in a haystack” queries can be executed pretty efficiently in BlitzDB. Looking at the first result, we can observe that it took an average of 0.058 milliseconds to process a query.

Future Plans

Admittedly, primary key support isn’t completely done so I’ll continue working on it. After that, I will start hacking on b+tree indexes and write more tests as I go. Once I support at least two indexes, I’ll ask the Drizzle Community to consider merging BlitzDB into Drizzle’s trunk. This is my goal for BlitzDB at the moment.

I also happen to own blitzdb.com so I’m planning on putting user documentation (including tutorial) and architectural notes there. This is currently not so high on my TODO list so I suspect it won’t happen until I get Version-1 released. All I can say about the release schedule at the moment is, “before the MySQL conference in april”.

So, that’s all I have to summarize for now. Thanks for reading this far. Merry Christmas and have a Happy New Year. Don’t trip on ice :)

Toru Maesaka drizzle, oss blitzdb, drizzle, storage

In brief, valgrind is a framework of awesome tools that does an amazing job at detecting memory errors. It will catch silly (often unexpected) mistakes and memory leaks that you’ve made in your code. IMHO, it’s a must have tool for open source hackers that work with Linux. If you develop a plugin or a storage engine for Drizzle/MySQL, you often end up wanting to test your program for memory errors. Actually, it’s not a “want”, it’s a MUST.

Conveniently by supplying a simple startup option, Drizzle and MySQL’s test runner will run the daemon process on valgrind’s virtual machine. I’m not sure about MySQL since I’ve never developed anything for it but at least with Drizzle you can run a test case independently by supplying the desired test name to the test runner.

 $ ./dtr your_test_file_name --valgrind

So, with BlitzDB this is what I do to isolate the test runner to only run my tests:

 $ ./dtr blitzdb.test --valgrind

Very simple.

The minor complication here is that the test runner will not output the valgrind report to the console and instead it writes the output to a file. So where is this file? the answer is, it’s written to the daemon’s error log which is located in the source tree:

$ less drizzle_src/tests/var/log/master.err
CURRENT_TEST: main.blitzdb
==24563== Memcheck, a memory error detector
==24563== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
...

Here’s another tip. If you ever wondered where the files that were generated in the test (like table and index files) are stored, they are stored inside the source tree as well. Here’s an example on my machine:

$ ll drizzle_src/tests/var/master-data/
total 20528
-rw-rw---- 1 tmaesaka tmaesaka 10485760 2009-12-01 22:06 ibdata1
-rw-rw---- 1 tmaesaka tmaesaka  5242880 2009-12-01 22:06 ib_logfile0
-rw-rw---- 1 tmaesaka tmaesaka  5242880 2009-12-01 22:06 ib_logfile1
drwxr-xr-x 2 tmaesaka tmaesaka     4096 2009-12-01 22:06 mysql
drwxr-xr-x 2 tmaesaka tmaesaka     4096 2009-12-01 22:06 test

So, with all that in mind, happy hacking :)

Toru Maesaka drizzle, knowledge, oss drizzle, hacking

Admittedly I’m a lazy guy. Due to this nature I’m a little behind on the updates made to the Drizzle Storage Engine API. From lurking through the source code in the Drizzle trunk, I’ve noticed these changes.

• Engines can now have an alias
• handler class is replaced by the Cursor class
• Engine handler is now a subclass of Cursor
• Table definitions are handled/stored by the storage engine
• doCreateTable(), doDropTable(), doGetTableNames(), doGetTableDefinition()

Currently I’m trying to catch up with the updated Drizzle Storage API and take this opportunity to rewrite most of BlitzDB. The reason is that the more I understand TC internal, the more mistakes I realized that I’ve made. I’ll blog more about this soon. Instead, I’m going to introduce something small but nice today.

A while back I poked folks like Monty Taylor and Stewart Smith that it would be cool if engines could have an alias. I mentioned this because InnoDB was allowed to use both “innodb” and “innobase” in the system whereas other engines could only have one name. Another reason I was interested in this issue was that I couldn’t understand how InnoDB could use two names since there was no way to do this in the old interface. Turns out InnoDB was treated specially in the core, which is obviously not desirable in a microkernel philosophy.

In the current Drizzle Storage Engine API, there is a function called addAlias(). By calling this function inside the storage engine constructor, you can allow your engine to have multiple aliases. For experiment purposes I wrote this to BlitzDB:

BlitzEngine(const string &name_arg)
  : drizzled::plugin::StorageEngine(name_arg, HTON_CAN_RECREATE) {
  table_definition_ext = drizzled::plugin::DEFAULT_DEFINITION_FILE_EXT;
  addAlias("BLITZ");
  addAlias("TCDB");
}

Here, I added aliases BLITZ and TCDB. TCDB is my way of showing respect to Mikio and Tokyo Cabinet. So given the above, we should now be able to create tables with three names.

drizzle> CREATE TABLE t1 (foo int) engine=blitzdb;
Query OK, 0 rows affected (0 sec)
 
drizzle> CREATE TABLE t2 (foo int) engine=blitz;
Query OK, 0 rows affected (0 sec)
 
drizzle> CREATE TABLE t3 (foo int) engine=tcdb;
Query OK, 0 rows affected (0.01 sec)

Success! Yep, this is something so trivial that I think most people wouldn’t care about but I was happy to see this update in the trunk :)

Toru Maesaka drizzle api, drizzle, storage

Yesterday I merged the BlitzDB tree with Drizzle‘s trunk for the first time in a long time (yeah…) and discovered some interesting changes made to the storage subsystem while I was away.

Previously all functions that caused an action to the storage engine was a member of the handler class but various things like table creation and transaction related functions have now moved to the StorageEngine class. These changes are somewhat drastic but makes good sense for Drizzle to grow further since it makes the subsystem easier to understand and frees Drizzle from the interface design that was strongly affected by MyISAM. For those that are interested, the StorageEngine class is located in “drizzled/plugin/storage_engine.h”.

For me it was pretty easy to update BlitzDB to work with the new subsystem since I don’t have anything special in the engine that required me to use my brain. I only had to move bas_ext(), table creation and rename functions over to the StorageEngine class and adjust it to the new interface:

int createTableImpl(Session *session, const char *table_name, 
                    Table *table_arg, HA_CREATE_INFO *ha_create_info); 
 
int renameTableImpl(Session *session, const char *from, const char *to);

For a real example, I recommend comparing the old InnobaseEngine class declaration with the updated one. As for where this redesign is going, this is the answer I got on the Drizzle channel from Stewart who did the actual work for all this.

stewart: tmaesaka: the basic idea is that handler becomes a cursor. the StorageEngine is for actions on the engine.
stewart: tmaesaka: and handler is a cursor on a table.

Something to keep in mind if you’re thinking about creating or porting a storage engine to Drizzle :)

Toru Maesaka drizzle, oss drizzle, mysql, storage

Today, I would like to introduce “skyload“, a small project that I’ve been working on for the last couple of weeks. In brief, skyload is a libdrizzle based load emulation tool that is capable of running concurrent load tests against database instances that can speak Drizzle (and/or) the MySQL protocol.

• http://code.google.com/p/skyload/

Something I’d like to emphasize here is that, skyload is not a replacement for mysqlslap or drizzleslap since it only provides a subset of what they can do. As I’ve stated on the project description, skyload is designed to do a good job at this subset of tasks by giving you more control over how you emulate the load in an intuitive way. For instructions on installing skyload and quickly getting up to speed, take a look at the following URL:

• http://code.google.com/p/skyload/wiki/Tutorial_en

As you will see, the first release only contains bare minimum specifications (only INSERT load emulation). The next step I want to take is to discuss features that other storage engine developers would actually find useful. This is because I started writing skyload for primarily myself and other storage engine developers (more on this next).

Original Intentions

I originally began writing skyload for BlitzDB development since I wanted to see the concurrent insertion performance of Tokyo Cabinet based row storage mechanism that I wrote. I first tried benchmarking the write performance with drizzleslap but it turned out that drizzleslap’s original code (inherited from MySQL 6.0) is rather buggy and segfaulted quite easily (I’m planning on contributing a fix for this).

So I gave up on drizzleslap for the time being and started looking at the sysbench port for Drizzle that Monty Taylor has been working on:

• sysbench: now with Drizzle

Sysbench for Drizzle is a lovely piece of software but it couldn’t quite provide what I was looking for (concurrent insertion benchmark). After having a quick conversation with Monty about my requirements on the Drizzle IRC channel, I decided to write a libdrizzle based benchmark tool that can be used for both Drizzle and MySQL.

Future Plans

I don’t want to reinvent existing software that works (or those that can be fixed). The project positioning that I’m hoping for skyload is a good mix between (mysql|drizzle)slap and sysbench. Hopefully it will be useful to folks that works on Drizzle and MySQL related projects.

I’m totally open for ideas, patches, and contributors. If this project had caught your attention, please don’t hesitate to ping me or the Drizzle community :)

I haven’t setup a mailing list since I don’t see the need for it yet so if you’d like to share your thoughts I think either the Drizzle mailing list or IRC (#drizzle @ irc.freenode.net) is the quickest way for me to get back to you.

Happy Hacking!

Toru Maesaka drizzle, oss benchmark, drizzle, mysql, oss, skyload, tools

Something I’ve added to BlitzDB recently that was pretty high on my todo list is support for variable width tables. So what is a variable width table? it is a table that contains columns that can vary in size, namely BLOB and TEXT types.

Going back to the basics, when a new row is to be written, a storage engine is given a pointer to the row data in MySQL format that it must somehow store for later lookup/retrieval. By meaning “somehow”, the storage engine is given the freedom to do whatever it likes with the row.

Writing a row for a fixed length table (a table with columns that are always the same size) is deadly easy. A storage engine can choose to not temper with the row and simply write or copy the data to it’s storage mechanism. This is because the storage engine is given a row that contains all the data. Rows for variable width tables however, are treated differently since things aren’t as simple (it’s variable!).

The difference is that columns for BLOB and TEXT types are represented by two parts inside a MySQL/Drizzle row:

• length of the data
• pointer to the actual data

This is simple to understand since we need to know the size of the data to copy it.

Minor Complication

The minor complication as you would expect here is that you can’t directly write the provided row to your engine like you can with fixed length tables. The data that you want to copy/write exists elsewhere (hence the pointer) so directly writing the row has no meaning (the data would have disappeared by your next access to that row). You need to make sure that the actual data for BLOB/TEXT column(s) are arranged appropriately on your engine’s row buffer and written out to it’s storage mechanism.

This process is commonly referred to as row packing (converting to your engine format) and unpacking (convert back to MySQL format). So how is this done? it’s actually pretty simple!

The solution is actually simple

As much as it sounds like a bother to support variable length rows, it’s actually not that bad. First you need to understand what a MySQL row looks like internally.

A MySQL row begins with a bitset that represents which fields are NULL. The length of this data obviously depends on the number of NULLable columns you have but this is easy to handle with Drizzle since we’re given all the relevant information by the TableShare object (same goes for MySQL from a different object).

After this data comes the actual column data in the order that appears in your CREATE TABLE statement. What you need to do to get packing working with this row is the not-so-obvious part that you really need an example to look at. Fortunately Tweeting about this attracted Brian’s attention which helped me move forward.

Loop the fields!

So, let’s take row insertion to a variable width table as an example. Imagine this table:

CREATE TABLE t1 (
  id int PRIMARY KEY NOT NULL,
  description text,
  arbitrary_data blob
) engine=your_engine;

and let’s imagine that we need to process this query:

INSERT INTO t1 VALUES (1, "hello world", "blobbbbb");

Now, the storage engine needs to “pack” the data for each column into it’s buffer in the write_row() function. Conveniently, Drizzle/MySQL provides a pack() function for it’s column types (fields) that will do the data packing for you. That is, you do not have to inspect the provided row for pointers to the actual data and do the packing/copying yourself.

How? well, the table object (which is visible from your engine) conveniently holds a list of fields in the appropriate order. The actual pack() function is a member of these fields so you just need to call it as you loop over the list:

/* make sure row_buffer has enough memory */
unsigned char *pos = row_buffer;
 
/* copy NULL bits, "table->s" is the TableShare object */
memcpy(pos, row, table->s->null_bytes);
pos += table->s->null_bytes;
 
/* "row" is the MySQL formatted row given by the core */
for (Field **field = table->field; *field; field++) {
  if (!((*field)->is_null()))
    pos = (*field)->pack(pos, row + (*field)->offset(row));
}

The above code snippet will populate “row_buffer” with the actual data that you want to write to your storage mechanism. You do not have to forward the “pos” pointer because pack() returns a pointer at the end of where it had worked in the buffer (think Pascal Strings). This is precisely why we created the pos pointer, to avoid row_buffer from being forwarded.

For the opposite situation (when retrieving a row), an unpack() function is provided for each field so you just need to take advantage of it like we did with the pack() snippet above.

Little bit more on fields

The actual pack() function that gets called depends on the type of column since the Field class is an abstract base class for the sub classes that actually represents column types inside Drizzle/MySQL. If you want to know what a pack() function looks like for a BLOB type, grep for “Field_blob” in the source tree and there will be a pack() member function for it.

The code layout for field subsystem in MySQL is rather difficult to comprehend since everything is crammed in “sql/field.c” and “sql/field.h” files (at least as of 5.4). So, if you want to get a good grasp of how things are architectured, you should take a look at Drizzle. Field subclasses are located individually in the “drizzled/field/” directory and the base class is located in “drizzled/field.h”.

So, that’s about it! Hopefully this information will help other engine developers when they come across a need to support variable width tables :)

Toru Maesaka drizzle, knowledge, oss drizzle, engine, mysql, storage

If you’re working on developing a Drizzle plugin, you may come across situations where you want to accept user options for it at server startup. For example, if you design your plugin to create files for activity logging, you may want to allow the DBA to specify where to write those files out.

In my case, I decided to provide a command line option to BlitzDB for row based query caching. This option is intended for special use-cases where the read/write ratio is 9:1. For those that are interested, row caching is disabled by default because it creates overhead in the engine for read-through logic and cache invalidation _unless_ read requests are significantly higher than update requests.

There are situations where BlitzDB’s row cache can be helpful but this is beyond the scope of this entry so I will save it for another day :)

Adding startup options to your plugin

Drizzle allows you to add command line options to your plugin without editing the server code. But before you start hacking away, there are few not-so-obvious things that you need to understand.

So, let us first look at the data types that your plugin can accept:

• DRIZZLE_SYSVAR_BOOL
• DRIZZLE_SYSVAR_STR
• DRIZZLE_SYSVAR_INT
• DRIZZLE_SYSVAR_UINT
• DRIZZLE_SYSVAR_LONG
• DRIZZLE_SYSVAR_ULONG
• DRIZZLE_SYSVAR_LONGLONG
• DRIZZLE_SYSVAR_ULONGLONG
• DRIZZLE_SYSVAR_ENUM

As you can see, there is a wide range of types that you can choose from. What you should choose depends on what you want to use the value for.

Pick your data type

So lets take my row cache option as an example. Caching over 4 billion rows in one physical server is very unlikely and since we’re not interested in negative numbers, we’re going to pick:

• DRIZZLE_SYSVAR_UINT

which we can store the value as uint32_t in the plugin.

Declare that your plugin accepts options

Every plugin must declare itself as a plugin which looks like this for BlitzDB:

drizzle_declare_plugin(blitz) {
  "BLITZ",
  "0.3",
  "Toru Maesaka",
  "Non-transactional General Purpose Engine",
  PLUGIN_LICENSE_GPL,
  blitz_init,             /*  Plugin Init      */
  blitz_deinit,           /*  Plugin Deinit    */
  NULL,                   /*  status variables */
  blitz_system_variables, /*  system variables */
  NULL                    /*  config options   */
}
drizzle_declare_plugin_end;

Here, we’re interested in the second last argument which is called blitz_system_variables in the above example. Feel free to call this whatever you like for your plugin.

So what exactly is blitz_system_variables? Its a null-terminated array of system variables that your plugin accepts. This is what it looks like for BlitzDB:

static struct st_mysql_sys_var *blitz_system_variables[] = { 
  DRIZZLE_SYSVAR(row_cache),
  NULL
};

As you can see, BlitzDB only supports one option at the moment so there is only one entry called row_cache.

Define your options

You must define every option that you’ve added to the system variable array. We decided to use DRIZZLE_SYSVAR_UINT earlier and called it row_cache so it is defined like this:

static DRIZZLE_SYSVAR_UINT (
  row_cache, /* option name */
  blitz_row_cache_size, /* variable to set the value to */
  PLUGIN_VAR_READONLY, /* mode */
  N_("Enable row caching for BlitzDB tables."),
  NULL,       /*  check func    */
  NULL,       /*  update func   */
  0,          /*  default value */
  0,          /*  minimum value */
  UINT32_MAX, /*  maximum value */
  0           /*  block size    */
);

The comments pretty much explains what the arguments are but for more details, you should take a look at the macros in drizzled/plugin.h. You could also look at what other plugins do by grepping for the system variable type that you’re interested in.

Test your new startup option

If all goes well you should be able to compile Drizzle and check whether command line options are visible from the plugin. An option takes the following form:

--<name_of_plugin>-<option_name>

So, in the row cache example, row cache can be enabled like this:

/usr/local/sbin/drizzled --blitz-row_cache=10000

Also note that you can replace the underscore with a hyphen:

/usr/local/sbin/drizzled --blitz-row-cache=10000

That’s it! it should be relatively easy to add more options once you successfully get your first one done.

Toru Maesaka drizzle, knowledge, oss blitzdb, drizzle