Tag Archive for data-warehousing at Xaprb

Tag Archive for 'data-warehousing'

Kickfire: relational algebra in a chip

Published at April 14, 2008 in SQL. 0 Comments

I spent the day Thursday with some of Kickfire’s engineers at their headquarters. In this article, I’d like to go over a little of the system’s architecture and some other details.

Everything in quotation marks in this article is a quote. (I don’t use quotes when I’m glossing over a technical point — at least, not in this article.)

Even though I saw one of Kickfire’s engineers running queries on the system, they didn’t let me actually take the keyboard and type into it myself. So everything I’m writing here is still second-hand knowledge. It’s an unreleased product that’s in very rapid development, so this is understandable.

Kickfire’s TPC-H benchmarks are now published, so you can see the results of what I’ve been seeing them work on. They are now #1 in the world, in two categories. Visit them at their booth in the exhibition area at the conference, and you will be able to see more for yourself.

The big picture

At a high level, Kickfire is an appliance consisting of two or more commodity rack-mountable 1U pizza-box units.

One unit contains the Kickfire chip and a lot of standard, high-speed, server-grade ECC memory. This unit is what executes the queries at high speed.

The other unit is connected to the Kickfire chip unit via a standard PCIe interconnect. It runs stock CentOS 5, with MySQL 5.1. Kickfire has their own storage engine, which uses fairly well-known techniques such as column storage and compression.

To the outside world, the unit behaves just like an ordinary MySQL server. You connect to it in the same manner, you issue the same kinds of queries, you manage users and privileges the same way, and so on. However, when you run a query, it doesn’t get executed in the traditional MySQL manner (nested-loop joins with calls to the storage engine via the storage engine API). Instead, the query goes to the Kickfire chip and executes there. The chip is designed to execute queries very fast, through a variety of techiques that a) I’m not allowed to tell you about yet or b) are sometimes unclear to me because Kickfire was being a little protective about some of my technical questions.

I met with quite a few people at Kickfire, but I’ll just mention one: Ravi Krishnamurthy. Before Kickfire approached me, I had not heard of him. Anyway, I’ll just link to Ravi Krishnamurthy on Google Scholar, and let you read up on his papers if you want. It’s enough to say that I really enjoyed speaking with him and the other people at Kickfire.

One of the overall impressions I got was that the Kickfire engineers aren’t the type to do something halfway. When complete, this is not intended to be a system that has only some of the features you’d expect.

I/O bottlenecks

The Kickfire chip has no registers. Instead, the Kickfire chip addresses a very large amount of memory directly. Remember, registers are a bottleneck. As I said in my first article on Kickfire, using registers to process large amounts of data is like using a paper cup to fill your bathtub. Allowing the chip to address this memory directly removes a huge bottleneck.

There is still on-disk storage, though. (And no, it’s not SSD.) The interconnect between the on-disk storage and the memory is a standard PCIe connection. Nothing exotic or proprietary. But the system is apparently capable of moving a very large amount of data at very high speed from the disks to the Kickfire chip’s memory, where it can be addressed in O(1) speed like an array lookup.

Another interesting technique is that the system does not decompress the data to operate on it. According to the engineers, the queries run on the data in its compressed form. As Ravi told me, implementing this is “not for the faint of heart.”

Kickfire seems to have really worked hard at removing bottlenecks wherever possible. For example, they’ve rewritten the out-of-the-box drivers for key pieces of the commodity hardware they’re using.

Souped-up MySQL

If you know how MySQL executes queries, the statement “Kickfire executes joins directly in the Kickfire chip” implies that the Kickfire system isn’t just a storage engine, because MySQL currently processes many of the most costly parts of queries at the server level, not in the storage engine. Obviously Kickfire is not going to perform well unless it changes that. Kickfire has in fact built their own optimizer, which replaces the MySQL optimizer. It compiles the incoming query into a series of macro-operations, which apparently are very similar to the basic relational operators (project, join, etc). This is then sent to the chip for execution, and as the chip produces results it injects them back into the stream of bytes that the server normally uses to send results back to the client.

The Kickfire chip doesn’t implement everything in hardware. For example, there is no MD5() function in the chip. When it encounters an operation it can’t do in hardware, it makes a call back to the MySQL server to fill in the gaps in its functionality.

The rewritten optimizer sounds like an interesting piece of engineering. Ravi told me with pride that the optimizer is “world-class” and “can stand toe-to-toe with the best optimizers in the database industry.” It is a cost-based optimizer with rewrites (e.g. it transforms the operator tree into the most efficient equivalent structure) and it is exhaustive (e.g. it tries all possible combinations to find the best execution plan, unlike MySQL’s optimizer which by default switches to a greedy search when the number of tables to be joined becomes large [correction: as Timour pointed out to me today, I made it sound like MySQL’s optimizer isn’t exhaustive; I neglected to mention that you can configure it]).

I asked whether they had benchmarked the optimizer’s performance. (I mean how fast it can find an optimal query plan, not the performance of its results.) Of course, there is no standard benchmark for this, but I think it’s interesting just to compare it against the MySQL optimizer. They had not done this, but I think they will now that I have mentioned it. I think it’s relevant because if you use Kickfire for short queries, a slow-performing optimizer could actually become noticeable.

Is it really stream processing?

I wanted to know whether the chip really does stream processing, or whether it is only conceptually stream processing that’s really implemented some other way. It sounds to me like it’s the genuine article. I asked some pointed questions to this effect, such as “is there a way to interrupt a partially completed query.” As it turns out there is, but only because the stream processor apparently does time-slicing like a standard chip, and when it comes up for air it can check to see if a query should be aborted. In general, I was told, there is no interruption once the data stream starts flowing. That lets the query literally “run at the speed of electrons.”

But what about subqueries, you ask? That’s what I asked too. Stream processing is all very well for joins, but what about a correlated subquery, for example?

It turns out that if you’re clever, you can figure out ways to decorrelate them and then execute them in streaming fashion. The same holds for aggregation over data that’s not in the order needed for streamed aggregation. Pretty interesting ideas; I can’t go into them, because those are proprietary, but Ravi and I talked about them for quite a while.

And very large IN() lists can be turned into a relation and treated like any other.

Storage

Storage is obviously crucial to processing extremely large amounts of data very fast. A few of the things I noted about the storage:

Each column is stored in a fixed width. This is how Kickfire can look up a row as though it’s doing an array access.
The internal representation is chosen automatically and may not match what you think. Kickfire can profile data as it’s loaded, and choose the type as it goes.
If you tell Kickfire you’ll only store values that are X large in a column, and it builds its column storage space to hold that large a value, what happens when you then start adding larger values later? Ravi explained how it works, and it’s proprietary right now, but suffice to say that Kickfire does not need to rewrite all the data you’ve already stored if you suddenly start storing values you didn’t anticipate. Yet, it can still maintain O(1) array-lookup performance on the compressed data.
You can pass the storage engine special comments in the CREATE TABLE statement to tell it what kinds of data each column will get. These comments are part of MySQL’s standard syntax — Kickfire has not changed the MySQL parser, so it should be 100% syntax-compatible with a standard MySQL server.
Kickfire has a very Oracle-like set of features around tablespaces, extents, and so on. You can have multiple tablespaces, and you can add devices to tablespaces, etc.
Storage is transactional and ACID-compliant, with logging and ARIES recovery much like Oracle, InnoDB, etc. If it surprises you that a system built for large data warehouses would be transactional and ACID-compliant, welcome to the club. I was expecting the usual special-case behavior, you know, you can load data but you can’t update it, or something like that. But as I said, Kickfire isn’t doing this halfway. Plus, TPC-H requires ACID properties.

Loading, ETL, and star schemas

Loading data is also important to accelerate: executing queries on large amounts of data isn’t good if it takes forever to get the data into the server. Kickfire has their own suite of tools, including one for loading data that accelerates the load process with the SQL chip itself.

Kickfire’s attitude towards star schemas is that you shouldn’t need to build a special schema for your data warehouse. They think their system will be so fast that you can keep your data in the same schema you use for OLTP. If that turns out to be true, that will save a lot of work. (How much effort have you put into building a separate schema for your data warehouse?)

Other notes of interest

Here are some other tidbits I thought I’d share with you:

The system has support for foreign keys. It automatically creates indexes on foreign keys and primary keys.
The standard types of indexes don’t really apply. Instead, the indexes are “hardware-friendly” (the other term they used was that the indexes are “impedance-matched to the hardware”). There are special features for indexing ranges of dates and indexing words inside a string (but this is not a full-text index; I’m unclear on how it really works, but it helps accelerate LIKE queries, which is important for the TPC-H benchmarks)
The deadlock detection is via cycle detection in the waits-for graph, not timeout-based. As a result, it should be fast.
The system I saw was running in debug mode, and wrote its optimized query plan to a file for every query. I talked with them about making this available via SQL. The plan is much more detailed and informative than MySQL’s EXPLAIN. They asked me whether it would be a good idea to wedge this information into EXPLAIN, and I told them I wouldn’t do that; EXPLAIN is a tabular output that doesn’t make much sense unless you really know how to read it. When you’re trying to understand a query plan, which is generally a tree of relational operators, you need a hierarchical view of it.
They told me that they use the INFORMATION_SCHEMA extensively, but I did not get a chance to look at it myself.
They also told me that they use UDFs extensively for system management, but again I can’t confirm.

Licensing

As you probably know, I’m a strong believer in Free Software. I am not aware of any plans for Kickfire to release the source code for their modified version of MySQL or their storage engine or optimizer. These are the satellite diamonds that surround the crown jewels: open-sourcing them would make it easier to reverse engineer the chip, which they don’t want. However, they’ve promised me that they’re going to open-source some of the migration tools, etc etc. Not initially, but as time permits; and later they’ll look at open-sourcing other parts.

I have made sure that they know where I stand on this: I think the ethical thing to do is GPL all the code that they ship, and I think everyone I talked to heard me say that at least once. If you’re going to buy their magical hardware, you deserve to have the source code for everything that runs on it, too. And they need to release the interface specs for their hardware so people can use it in new and surprising ways. Who knows — someone could use it to find a cure for cancer.

Summary

My two days with Kickfire left me with a lot more questions, not surprisingly, and I don’t think that will change until I actually get access to a machine and start testing it myself. I saw a lot of slideshows; I saw some demos; I walked into the server rooms and saw the pretty blinking lights; but I’m not going to tell you that Kickfire will do X or Y because I don’t know a heck of a lot. I was hoping for more hands-on experience and in-depth technical details, but that wasn’t the way it really worked out. However, based on what I’ve seen, I have no reason to believe other than that Kickfire’s system will do what they claim: it will run large, complex queries on very large datasets extremely quickly.

Technorati Tags:ARIES, column store, data warehousing, Kickfire, mysql, Ravi Krishnamurthy, stream processing, TPC H

Kickfire: stream-processing SQL queries

Published at April 4, 2008 in SQL. 9 Comments

Some of you have noticed Kickfire, a new sponsor at this year’s MySQL Conference and Expo. Like Keith Murphy, I have been involved with them for a while now. This article explains the basics of how their technology is different from the current state of the art in complex queries on large amounts of data.

Kickfire is developing a MySQL appliance that combines a pluggable storage engine (for MySQL 5.1) with a new kind of chip. On the surface, the storage engine is not that revolutionary: it is a column-store engine with data compression and some other techniques to reduce disk I/O, which is kind of par for the course in data warehousing today. The chip is the really exciting part of the technology.

The simplest description of their chip is that it runs SQL natively.

OK, but now you need to do something: get “SQL chip” out of your mind. It doesn’t work the way you think it does, and your pre-conceived ideas may prevent you from understanding how different this really is. (Everyone says their technology is a paradigm shift, so I expect you to be numb to this phrase.)

I can’t explain all of the technology in this post, partially because of NDA, but I want to prepare you for when you do hear the details. If you’re like me, you’ll miss a lot of stuff because you have tunnel vision, and then you’ll say “wait, I get it now! Can you please repeat everything you’ve been saying for the last hour so I can think about it all over again?”

An important note

Very important: I have not seen this technology, tasted it, smelled it, or benchmarked it. This information is based on discussions with their engineering and other staff. I will not pretend to know anything I don’t. I will be spending two days in the lab with the engineers next week, and then I will be able to write in greater detail with more confidence.

How your computer currently works

To understand how Kickfire’s chip works, you need to understand something you probably take for granted: how most chips work. Most computers today use the same architecture they always have: there’s data that is held in the CPU, and data that is not. The CPU has registers, which hold a miniscule bit of data – the data it is currently working with. When the CPU processes an instruction that asks for some more data it doesn’t have, the CPU has to go fetch it. In the meantime, the instruction can’t complete.

As you might imagine, this is not terribly efficient. Fetching data that’s not in the CPU can take hundreds of CPU cycles (or more). To work around this, computer architects have developed a hierarchy of caches: the on-chip cache, the main memory, and the hard drive, to name a few. The caches make it faster to get data when it’s not already on hand. And modern chips have a pipeline, too. The pipeline looks at the instructions as they flow towards the CPU, tries to predict which data they’re going to need, then pre-fetches it.

In the best case, this works okay. Not always — for example, the Pentium 4 has a very long pipeline, so the cost of a wrong branch prediction is very high. Another case is when you simply need a lot of data, such as tens of gigabytes. Suppose for your 10GB operation, you’re only going to look at each byte once (a common occurrence in data warehousing queries). This renders your caches useless, because caches work on the principle that you’re likely to look at recently accessed data again soon.

In these cases, the speed of the computation is constrained by the Von Neumann bottleneck: the inefficient fetch-compute-wait cycle of constantly going to the memory (or disk) for more data, a teeny bit at a time. Remember, even in-memory data is very slow compared to data that’s in the registers. Having a lot of fast memory is not a solution to the Von Neumann bottleneck. It’s a workaround to reduce the cost.

Kickfire’s architecture

Kickfire is designed to work well where today’s general-purpose computing architectures run queries slowly because they’re sitting on their thumbs much of the time. Think data warehousing: complex queries with lots of data.

What is the industry’s answer to this? So-called massively parallel processing, or MPP. Current MPP data-warehousing solutions are special-purpose database software that runs queries on dozens or hundreds of CPUs, which occupy a lot of storage space and require lots of power, hardware, and cooling. “If you throw enough Von Neumann machines at the problem simultaneously, they can answer your questions faster,” or so the thinking goes. In other words, the current state of the art is to arrange conventional computers in new ways.

Kickfire takes the opposite approach: stream processing. This is a fundamentally different computing architecture. Stream processing is to Von Neumann machines as LISP is to C.

For those of you who aren’t LISP programmers, here’s another analogy: In stream processing, you take a bunch of data and you shove it through the chip without stopping. Rather than the chip asking for data from the storage subsystem as needed, the data actually gets pushed at the chip. That is, it’s push-processing instead of the conventional pull-processing.

Conventional processing is like trying to fill your bathtub from the sink with a paper cup. Stream processing is like putting your tub under the sink and opening the drain.

I’m taking some liberties here, to illustrate the differences. As I said, I haven’t seen the wiring diagrams of the Kickfire chip. But hopefully you get the concept.

This is not a new idea. If you’ve worked with modern graphics cards, you’ve seen this in action. Programming languages like Cg express the stream-processing concepts elegantly. If you’ve ever been in a classroom full of C++ programmers trying to learn Cg, you’ve seen how hard it is to grasp this different approach. Essentially, graphics programming on one of these chips is a series of transformations, not a series of instructions. You input some vertexes at one end of the processor, and you tell the chip to do some matrix multiplies and so on. Out pops the result at the other end.

If this doesn’t sound much different from instructions… well, meditate on it. It’s like an assembly line, but nobody leaves their station along the conveyor belt. In a traditional CPU, the “person” at the conveyor constantly leaves to go get the materials he needs.

Kickfire runs in commodity hardware, and it is just one or two servers, not racks full. Like many other systems designed for large amounts of data, it uses a column data store. Unlike many other systems, it uses an industry standard interconnect and a custom pluggable MySQL storage engine.

What took so long?

Stream processing is the obvious way to run SQL queries. Some readers may never have thought about it this way, but my guess is that a lot of you already think of SQL in a stream-processing way, even though you might know that computers today really implement it in conventional ways. I have always tried to think of it this way, and I always try to explain SQL as a stream, too.

So when I was on a call with the Kickfire engineers and it finally sunk in, I felt really silly. Why didn’t I think of that? It’s so obvious.

But then again, most breakthroughs are really obvious in hindsight.

Performance

I have seen initial benchmark results, but I’m under NDA about them. I can’t say any more yet. And I haven’t run any benchmarks myself yet, nor have I had access to the hardware. So this is all theoretical until I get my hands on the system. Caveat emptor, your mileage may vary, etc etc.

One thing I’m interested in is how well the system performs for general-purpose queries. When you take it away from complex queries on lots of data, does it still have an advantage? I’ll be trying to get an answer to that question next week.

About Kickfire

They are still in stealth mode and my NDA prevents me from being able to tell you a lot or answer all your questions yet. But someday they will no longer be in stealth mode, and you’ll find out everything you want to then.

Hint: they are going to be giving a keynote address on their technology, but there’s not much detail in the description. Come to the keynote and find out.

Why am I writing this?

Well, they promised me chocolate…

Seriously: I do have an agenda, but there are actually several motivations here. The first is that they initially contacted me because of my involvement with the MySQL community. Of course they’re hoping to gain publicity through me, but they also wanted to let the community have some input. I’ve been sort of a secret liason for you, representing your interests to Kickfire. I’ve advocated pretty strongly for certain things I’ll go into in a later post.

The other reason I’m working with them is that I’m excited about their technology, even though I don’t have hard evidence about their claims and benchmarks yet. If what they’re saying is true, their product will be very good for the environment. It will let people save a lot of energy (power, cooling, the need to build data centers) and it will help avoid the need to build a bunch of servers. Computers are extremely toxic to manufacture.

I’m also interested in seeing them succeed because I anticipate that even if this product isn’t what it claims to be, they’ll prove the concept and there will be a competitive rush into this space. That is guaranteed to produce a lot of changes in how people build computers, probably in more areas than just data warehousing. So I’m happy that they’re starting this, because others will finish it whether they do or not. And that’s good news for the environment, too.

Stay tuned. More details are forthcoming.

PS: if you have questions you’d like me to look into while I’m onsite with the engineers, feel free to post them in the comments. But I probably can’t answer them yet.

Technorati Tags:caching, Cg, column store, CPUs, data warehousing, Graphics, Keith Murphy, Kickfire, MPP, mysql, mysqluc2008, pluggable storage engine, QPU, Von Neumann bottleneck

MySQL Archiver can now archive each row to a different table

Published at November 5, 2007 in Perl, SQL and Tools. 0 Comments

One of the enhancements I added to MySQL Archiver in the recent release was listed innocently in the changelog as “Destination plugins can now rewrite the INSERT statement.” Not very exciting or informative, huh? Keep reading.

If you’ve used plugins with MySQL Archiver you know that I created a series of “hooks” where plugins can take some action: before beginning, before archiving each row, etc etc. This lets plugins do things like create new destination tables, aggregate archived rows to summary tables during archiving (great for building data warehouses, though not as sophisticated as Kettle), and so on. Well, this release added a new hook for plugins: custom_sth.

This lets a plugin override the prepared statement the tool will use to insert rows into the archive. By default the prepared statement just inserts into the destination table. But the custom_sth hook lets the plugin inspect the row that’s about to be archived and decide what to do with it. This lets it do interesting things like archive rows to different tables.

This came up because some of the tables I’m archiving to suddenly hit the bend in the hockey-stick curve. I diagnosed the problem very simply: inserts began taking most of the time during archiving. As you might know, MySQL Archiver has a statistics mode where it profiles every operation and reports the stats at the end. I’m archiving out of InnoDB into MyISAM; take a look at the stats:

Action          Count       Time        Pct
inserting      800584 12722.8245      88.35
deleting       800584  1464.1040      10.17
print_file     800584    58.3453       0.41
commit           3204    29.4391       0.20
select           1602     8.5654       0.06
other               0   116.5321       0.81

Inserting suddenly took 88% of the time spent archiving, when it had been taking a very small fraction of the time. I’d been meaning to split the archived data out by date and/or customer, and this convinced me it was time to stop procrastinating. There are columns in the archived rows for both of these dimensions in the data, so it shouldn’t be hard. So I added the custom_sth hook, wrote a 40-line plugin, and did it. Results:

Action             Count       Time        Pct
deleting           51675   525.2777      87.62
inserting          51675    49.3903       8.24
print_file         51675     4.4639       0.74
commit               208     2.1553       0.36
custom_sth         51675     1.4575       0.24
select               104     0.6714       0.11
before_insert      51675     0.1135       0.02
before_begin           1     0.0001       0.00
plugin_start           1     0.0000       0.00
after_finish           1     0.0000       0.00
other                  0    15.9868       2.67

(You can see the effect of having a plugin, because the time taken for all the hooks is listed in the stats. There was no plugin previously.)

Now inserting takes only 8% of the time required to archive. Put another way, it used to insert 63 rows per second, now it inserts 1046 rows per second. This is single-row inserts. (It is not intended to archive fast; it is intended to archive without disturbing the OLTP processes. Obviously this server can do a lot more inserts and deletes than this.)

What had happened? The MyISAM tables on the destination end had just gotten too big for their indexes to fit in memory, and the inserts had suddenly slowed dramatically. I didn’t want to give them a lot more memory, because I want the memory to be used for the InnoDB data on that machine. This is the same kind of thing, I’d guess, that Kevin Burton just wrote about.

Oh yeah, while I was at it, I totally rewrote the archiver with unit-tested, test-driven, test-first, other-buzzword-compliant code. I added a lot of other improvements, too. For example, it can now archive tables that have much harder keys to optimize efficiently, such as nullable non-unique non-primary keys.

Technorati Tags:archiving, data warehousing, Hockey Stick Graph, innodb, Kettle, Kevin Burton, myisam, mysql, olap, oltp, Plugins, sql

High Performance MySQL, Second Edition: Backup and Recovery

Published at September 19, 2007 in High Performance MySQL and SQL. 11 Comments

Progress on High Performance MySQL, Second Edition is coming along nicely. You have probably noticed the lack of epic multi-part articles on this blog lately — that’s because I’m spending most of my spare time on the book. At this point, we have significant work done on some of the hardest chapters, like Schema Optimization and Query Optimization. I’ve been deep in the guts of those hard optimization chapters for a while now, so I decided to venture into lighter territory: Backup and Recovery, which is one of the few chapters we planned to “revise and expand” from the first edition, rather than completely writing from scratch.

Since we decided to take that approach, I began by following the outline from the first edition, and figured I’d re-read the first edition’s chapter and re-outline, then add more material as appropriate. To my surprise, I found this chapter in the first edition is one of the most cursory (I don’t mean to criticize too much — you’ll see where I’m going with this in a second). It’s quite short and doesn’t really discuss recovery at all, despite the chapter title. There’s one sub-section titled “Recovery,” but it’s only a few paragraphs, and mostly discusses dumping, not recovery! [Edit: whoops, I see each subsection in the “Tools and Techniques” has a few words about how to restore backups created with that specific tool. But there’s still not much general advice about how to restore backups.]

The chapter devotes a lot of space to code listings and such, and not enough on how to do high-performance backups in a high-performance application, in my opinion. I quickly decided it needs to be significantly expanded, not just updated, and I scrapped the original text and became more liberal with the outline. I’m referring to the first edition as I write, but I’m not keeping any of the text. Chalk it up to perfectionism.

The outline, as I have it so far, is as follows. If you compare it to the first edition, you’ll see I’ve rearranged it quite a bit:

1  Why Backups?
   (very brief, even more so than the first edition)
2 Considerations and Tradeoffs
   2.1 How Much Can You Afford to Lose?
   2.2 Online or Offline?
   2.3 Dump or Raw Backup?
   2.4 Onsite or Offsite?
   2.5 What to Back Up
   2.6 Storage Engines and Consistency
   2.7 Replication
3 Restoring from a Backup
   3.1 Copying Files Across the Network
   3.2 Starting MySQL
   3.3 Point-In-Time Recovery
4 Tools and Techniques
   4.1 mysqldump
   4.2 mysqlhotcopy
   4.3 Zmanda Recovery Manager
   4.4 InnoDB Hot Backup
   4.5 Offline Backups
   4.6 Filesystem Snapshots
   4.7 MySQL Global Hot Backup
   4.8 Automating and Scripting Backups
5 Rolling Your Own Backup Script

At this point, I have written sections 1, 2 and 3, which are about 11 pages in OpenOffice.org (compare to 6 pages on paper in the first edition). I’m sure this will only grow as other things occur to me. The outline of section 4 is completely open to change, and section 5 might not even happen; if you can script, you can script. Otherwise, you might want to use one of the tools listed in section 4. All in all, I’d say we’re looking at about 25 to 30 pages, just based on what’s in my head and not yet written down.

Now, to come to my point: what would be helpful to you? Are there any challenges you’d like me to cover, such as how you back up a data warehouse with terabytes of data? (I’ve already done that, in What To Back Up, but feel free to ask anyway.) Are there challenges you have had to solve, which you think would be very helpful to others? This chapter is largely open to suggestion at this point. If you tell me/us what you’d like to see, this is your opportunity to get at least four experts to solve your problems in-depth.

The usual disclaimers apply: no guarantees, this is all open to change, this is top-secret pre-production material anyway and you never saw this web page. What is the first rule of Fight Club, again?

I’m looking forward to your feedback.

Technorati Tags:backup, data warehousing, High Performance MySQL, mysql, recovery

Archive strategies for OLTP servers, Part 3

Published at June 15, 2007 in SQL. 3 Comments

In the first two articles in this series, I discussed archiving basics, relationships and dependencies, and specific archiving techniques for online transaction processing (OLTP) database servers. This article covers how to move the data from the OLTP source to the archive destination, what the archive destination might look like, and how to un-archive data. If you can un-archive easily and reliably, a whole new world of possibilities opens up.

For your reference, here are links to part 2 and part 1, and the original article on efficient SQL queries for archiving, which is the basis for this whole series.

How to move the data

At some point you have to actually take the data from the source and put it into the archive. This is a three-step process:

Find archivable rows
Insert them into the archive
Delete them from the source

I wrote an article on how to find archivable rows efficiently, so I won’t go into it more here. Inserting and deleting are usually straightforward, but there are subtleties and tricks that can lead to nifty solutions.

Transactions

The most important question about actually moving the data is how to do it safely, with or without transactions. Even if the source and archive are on different servers, you can do distributed transactions, either in your application logic or with a two-phase commit supported by your database product. For most purposes, I’ve found it just as reliable and more efficient to handle the transaction in your application logic.

For many of the reasons mentioned in the second article in this series, I would recommend relaxing the consistency requirements between source and archive, so you can keep the archived data out of the source’s transaction. You can do this safely by performing the operations in the order I listed above: insert, delete, commit the insert, then commit the delete. If you are archiving to a file at the same time, you can also write to the file before the insert.

Your archive might also be non-transactional. If you’re using MySQL, you should think about using a faster non-transactional engine that stores the data more compactly, such as MyISAM, for the archived data.

Use replication to unload the OLTP server

One of the most effective ways to archive an OLTP server without impacting it too much is to do the hard work of finding and inserting on a slave server, then performing the delete on the master and letting it flow through replication. Here’s an example from a past employer: we replicated the order table to a “transfer” database on the data warehouse server. A job on the data warehouse server looked for orders that had completed and shipped, and thus could be archived. It copied these in a transaction to the long-term storage, then deleted on the OLTP server. This delete flowed through replication back to the data warehouse, and removed the rows from the transfer database.

The archive server

I’ve already mentioned some ways you might design the archive server, but there are a few other things I want to cover briefly. The first is what happens when you don’t use a different server at all, and just archive to adjacent tables on the OLTP server. This can be a fine way to do things. As long as the data isn’t used, it’s just taking up space on disk. However, it might make backups more difficult.

If you use a different server to hold the archived data, you should probably consider some kind of partitioning scheme. If your server doesn’t support partitioned tables natively, you might want to archive into a different table every so often, building views over all the tables to present them as a single logical table. There are some important advantages to this, especially if you eventually want to purge really old data. It is much easier to drop an entire table when it ages out than to delete rows from a huge table.

This gets into the topic of how to build a large data warehouse, so I’ll just leave it at this: if you forsee the archived data getting large, start planning for it now.

Duplicated data

Unless you use distributed transactions or some clever way to guarantee atomicity, there’s a chance you’ll insert to your archive but fail to delete from the source. Now you have duplicate data. How will you handle this?

First, decide if you can tolerate the situation. (I told you we hadn’t seen the last of the consistency requirements!) I suggest you take it as a given, if at all possible. Design your archiving jobs so they can tolerate existing data in case they get terminated uncleanly or otherwise have errors. If they try to insert rows that exist, you should probably overwrite the existing rows with new ones, which might have changed on the OLTP server. Make sure you don’t lose data from this, one way or another.

If you are archiving summary tables, you might need to be careful. A row that’s built incrementally on the OLTP system might need to be re-aggregated, instead of replaced, if it already exists in the archive.

Duplicated data makes some queries hard to get consistent. For instance, a view that takes the union of archived and un-archived data will tell a lie if a row exists in both places. You need to factor this in when deciding how to do the archiving. Duplicates can also happen during un-archiving.

Un-archiving

Why would you ever want to un-archive?

Here are some reasons you might benefit from being able to un-archive easily:

You treat all the data as equally important, but some of it as more likely to be accessed
You know there’s unused data but it’ll be inefficient to figure out which rows
You can’t get an exact answer on whether rows are archivable

Think of it this way: the ability to un-archive lowers the risk of archiving the wrong data, and allows you to archive things you might otherwise be unable to touch. It takes away or mitigates the downside.

This goes back to my analogy of archiving as flushing from a cache. You probably don’t treat databases as a multi-tier cache, and that’s a good thing. If the data isn’t where you expect, your applications would need to look elsewhere and retrieve it. Unless you write a wrapper around your database access layer that handles it automatically, this is probably infeasible.

However, you can still use the concept of retrieving missing data under certain circumstances. Does the following sound workable?

Make most applications tolerate missing data and just do what they can with the data they have
Identify points of entry where incoming data is a signal to un-archive something
Hook an un-archiving system into the points of entry
Archive freely and let un-archiving bring back anything it needs to

Here’s a concrete example from the advertising system I mentioned previously. This system archives ads eagerly; if they don’t have any traffic in a while, it moves them away. There are limited points of entry for ad-related data: traffic data, and a record of a sale that is attributed to an ad. The systems that load this incoming data can simply check whether all referenced ads exist, and if not, attempt to un-archive any missing ones. This happens as part of the routine checks for bad incoming data. This approach is fairly new for us, and might have some kinks we haven’t yet discovered, but there is virtually no downside. The data isn’t gone, it’s just elsewhere. Now we can archive data we couldn’t before, because it was too hard to get a definite “yes, this can be archived” answer. (It’s often easy to get a “no,” but hard to get a “yes.”)

Un-archiving is non-trivial. In fact, depending on your schema, you might need to be more careful about consistency requirements than you are with your archiving strategy. However, if you’re archiving correctly, un-archives should be few and far between, so you can afford a more expensive process.

In many ways, your options for un-archiving strategies might be similar to archiving strategies. In the systems I’ve worked on, we take the depth-first-search, dependencies-first, all-one-chunk approach I think is too inefficient to use for archiving.

If your archive is non-transactional, be careful to commit the insert into the OLTP system before you delete from the archive. Otherwise your delete will be permanent, but your insert might be rolled back, and the data is lost.

You don’t have to un-archive

If you don’t want to build an un-archiving system, you can build your applications to look in the archive for data they need and can’t find in the OLTP system. If you do this seldom enough, it might work fine. One order-history system I know of does this to find orders that aren’t in the OLTP server.

Archiving miscellany

To round out this series, here is a collection of notes and references I didn’t want to mix in along the way, but I think belong here somewhere.

First, if you’re using MySQL, I’ve written tools that can handle much of the work I’ve described here. The first is MySQL Archiver, which can find and move archivable data very efficiently. It is full-featured and should handle most needs as-is, but it’s also extensible, so you can plug your own code in to handle complex archivability checks, dependency-first archiving, and so forth. Another of my tools, MySQL Find, can monitor and create historical records of table sizes, so you can get a sense of which tables are largest and/or growing the fastest (this is a one-liner that can go into your daily crontab). If you are archiving from InnoDB tables, you might want to record deadlocks with MySQL Deadlock Logger, for obvious reasons.

All these tools are part of the MySQL Toolkit, which is Free Software. Another useful tool is innotop, a real-time interactive MySQL and InnoDB monitor I’ve written.

A couple more notes on MySQL: the choice of storage engines makes MySQL especially attractive for single-server archiving solutions, in my opinion. It’s quite practical to run your intense OLTP workload on InnoDB tables (or another transactional storage engine, such as Paul McCullagh’s PBXT) and store the archive tables side-by-side in MyISAM or ARCHIVE tables. If you’re using MySQL 5.1, you also get partitioned tables; if you’re not that bleeding-edge, you might consider the strategy I suggested at the recent MySQL Conference and Expo: archive to a small InnoDB table for high concurrency, then regularly convert it to MyISAM and place it into a MERGE collection, with a view that unions the InnoDB and MERGE tables (Sheeri Critzer blogged about this also, though I’m not sure how many people are actually doing it).

I don’t really like triggers and foreign key magic, so I relegated this suggestion to here: you can use triggers and/or foreign key constraints with ON UPDATE actions to help with archiving and purging. I don’t like these approaches because I think they’re hidden, dangerous code. In Microsoft SQL Server I usually used stored procedures to archive, but in MySQL these days I use MySQL Archiver (linked above).

MySQL’s Edwin DeSouza wrote me to bring my attention to some of Craig Mullins’ recent articles about archiving. Craig’s insight is valuable if you’re researching archiving.

I think that’s it for the miscellany.

Conclusion

This series has covered what I believe to be the full scope of archiving strategies, from requirements to specific techniques you can use to archive and un-archive data from your OLTP systems. As a reminder, the larger context here is to offer scaling back as an alternative to the usual scale-up-or-scale-out dichotomy. There are always more options than you think! Archiving can be difficult and complex, but the potential gains for some types of data can be large, especially compared to some of the more frequently-discussed scaling tactics. Like other solutions, it doesn’t work for all situations, but if you forsee a huge amount of data coming at you, you should consider archiving along with other scaling techniques.

Technorati Tags:archiving, Craig Mullins, data warehousing, deadlocks, Edwin DeSouza, innodb, mysql, mysqltoolkit, olap, oltp, Paul McCullagh, pbxt, scaling, Sheeri Critzer, sql, transactions

MySQL Archiver 0.9.2 released

Published at June 9, 2007 in Perl, SQL and Tools. 3 Comments

Download MySQL Archiver

This release fixes some minor bugs and adds a plugin mechanism. Now you can extend MySQL Archiver with your own code easily. You could use this to run setup and tear-down, hook code into the archiving process, and more. Possibilities include building summary tables in a data warehouse during archiving, handling dependencies such as foreign keys before archiving each row, or applying advanced logic to determine which rows to archive.

The documentation contains full details about the plugin interface, including example code.

Technorati Tags:archiving, data warehousing, mysql, mysqltoolkit, plugin, sourceforge, sql

MySQL Archiver 0.9.1 released

Published at June 6, 2007 in Perl, SQL and Tools. 3 Comments

Download MySQL Archiver

MySQL Archiver is the implementation of the efficient forward-only archiving and purging strategies I wrote about more than a year ago. It nibbles rows from a table, then inserts them into another table and/or writes them to a file. The object is to do this without interfering with critical online transaction-processing (OLTP) queries.

Several people have asked me to release this code, which I originally wrote for my employer. As it turns out, the delay has been fruitful. I learned a lot more about query optimization during this time, found bugs with my original approach, and got exposure to different archiving needs and techniques. As a result, this tool runs something like four to ten times faster than the code I wrote last year.

I decided to write and release it now because my employer has grown to the point we need to archive more data, faster, more flexibly. Instead of just open-sourcing the code I wrote last year, I have rewritten it from the ground up. We are using exactly the same code, and hope to benefit from community feedback and improvements.

I think the result is a good tool that does a lot of work for you:

It automatically writes efficient queries by inspecting table structures and indexes.
It handles transactions, lock timeouts and deadlocks.
It writes archived data to a file in the same format LOAD DATA INFILE uses by default.

It has a lot of options and functionality, so I won’t go into it too much here. I also have several ideas I want to implement in the future, but I want to see what the community thinks of what I’ve done so far before I work on it too much more.

Despite the improvements, the basic approach remains the same: it finds the first row(s), and then on subsequent queries, it continues from where it left off, rather than scanning the whole table from the start. This makes it efficient to archive in small “nibbles,” which avoids contention with OLTP queries.

I’ve put almost 30 extra-curricular hours into this recently. Most of the time has gone into making sure every different type of archiving job my employer needs to run can be generated as efficiently as possible with a minimum of fuss, such as a simple command-line option or two. I’m eager to hear what you think of it, whether it meets your needs, and how it can be improved. And I’m glad I’ve finally gotten it done after all this time!

About MySQL Toolkit

MySQL Toolkit is a set of essential tools for MySQL users, developers and administrators. The project’s goal is to make high-quality command-line tools that follow the UNIX philosophy of doing one thing and doing it well. They are designed for scriptability and ease of processing with standard command-line utilities such as awk and sed.

Technorati Tags:archiving, data warehousing, mysql, mysqltoolkit, sourceforge, sql