Mapreduce and Key-Value Systems

I've been playing around with Riak (ree-ack), my first foray into NoSQL, and it's been a lot of fun. Riak is an open source implementation of Amazon's DynamoDB. It's a web-ready key-value store that scales easily. And it's a whole different world from RDBMS's. Basho has a great tutorial for getting started.

If you're a database guy like me, you're probably wondering what you can do with a key-value store. Using key-value tables is a SQL anti-pattern. Even if you get performance and scalability (which I'll discuss in an upcoming post), it's hard to see how you could do any interesting queries with a key-value system.

One thing to note is that a file system is basically a key-value store. The key is the file name and the value is the contents of the file. You can do searches on file systems, but you can't really do much querying. If your data needs are more like a file system than complex analytics, a key-value store might be right for you.

I also finally learned what the MapReduce algorithmic framework does. You may have heard of MapReduce (amongst many other new technologies) in connection with Hadoop. MapReduce will probably go down in history as one of Google's greatest contributions to computer science (along with the PageRank algorithm).

MapReduce is inspired by a functional language, LISP.  The idea is simple: take the algorithm to the data. In a highly distributed and scalable system, it's not feasible to move data to a processor in order to aggregate and slice it. You have to do any processing in-place. The way to do this is to map your keys to some kind of broader category and then run a reduce algorithm over the mapped data to pick out only the information you need.

For example, let's say your key-value store contains documents, and you want to count the number of documents beginning with the letter 'X' that contain the word 'tibialoconcupiscent'.  In this case, you would map all documents with a key like 'x*', such as 'xerophagy.pdf'.  Your reduction algorithm would simply return 1 for every case of the word and 0 otherwise. This reduction could be run on each server, a group of servers, and then all servers, returning a single (probably small) number.

This framework may seem limited, and it is. Key-value systems just aren't great for complex querying. One reason SQL has been so popular is that it allows for unlimited combinations of queries. You're limited in the ways you store data, and you have to wait for the system to write the data to disk in order to ensure consistency, but you can read the data in lots of interesting ways. That's why it's called a Structured Query Language.

(Riak does let you do some more interesting things because you can create links between different keys that define any kind of relationship between them. These links are just metadata. You can MapReduce across links, but the basic idea is the same.)

Now, where would I use Riak? There are a good number of production users already. I would think it would be best used in systems that don't require a lot of complex querying or complex data types. For instance, it could store webpages, messages, or other content. Unless you have a huge amount of data or require very fast writes, it's probably not necessary. But if you're looking to grow fast, it might be the right choice.

Cathedrals, Bazaars, and Data

According to Eric Raymond, with enough eyeballs, all bugs are shallow. This is the secret to the success of open source software. Linus Torvalds' primary innovation wasn't so much creating Linux as the development model surrounding it: get something out there, get people using it, and have them be your testers / contributors. That is, make users co-owners, not just consumers. Raymond compares open source software development to a bazaar, as opposed to a building a cathedral.

I've been using Linux and open source software for more than a decade, but I've always been a bit wary of open source databases. Do you really want a fail early/often approach when dealing with people's data? Oracle has made a killing off of Data Fear. After all, can you promise 99.999% uptime with an unproven system? Open source might be fine for startups, but is it fit for enterprise?

PostgreSQL seems to merit the hype. Even SQL Server DBAs like it. I don't have experience with it on the enterprise, but I'm impressed so far. I believe that it's a tested solution, and I really like its extensibility. Anyone can create any kind of extension, such as an Amazon Web Services interface or K Nearest Neighbor mapping.

As a .Net/SQL Server developer, however, I have some concerns.

First, is free really free? SQL Server Enterprise is $6,874 per core. Oracle Enterprise is $47,500 (though Standard Edition One is only $5,800). That's nothing to sneeze at. I don't know Oracle that well, but with SQL Server, you get a whole suite of technologies--ETL (SSIS), data warehousing (SSAS), and reporting (SSRS) in particular. You get a number of disaster recovery options, like 2012's AlwaysOn.

By default, PostgreSQL works from the command line. You can download PGAdmin, but Navicat costs money. Graphical ETL tools? I don't think so. Reporting? You'll probably have to spring for Crystal reports. Data Warehousing? I hear Pentaho is a pain. It would be hard to keep PostgreSQL free--at least in an enterprise environment.  If you're just doing CRUD for a web UI, you're probably ok--for a while.

The second thing that makes me nervous is the ridiculous number of open source technologies out there. The principle of open source is to 'let a thousand flowers bloom,' but in practice this means playing around with a whole lot of different products and figuring out how they can fit together. It seems like chaos. Microsoft is known for its Three Letter Acronyms (TLAs), but at least everything fits together pretty well.

Finally, because of the complexity of open source solutions, I can't imagine they'd be easy to maintain. Most companies now outsource common DBA and production support tasks. If you're running a PostgreSQL OLTP system with a MongoDB document store and Hadoop web logging, you'll have trouble getting Tata to maintain that for you. Even if you're not interested in outsourcing, it is useful to have standards and best practices across companies.

Of course, it's the innovative start-ups that are using new open source technologies to do new things.  This is one of the main factors that helps them be innovative. They don't want to be standardized. They want to be part of the bazaar of new tech IPOs, rather than the cathedrals of established companies--at least until they have enough users for the cathedrals to buy them.

Anyway, I'm having a lot of fun.  Check out my new favorite book.

The Art of War

While heeding the profit of my counsel, avail yourself also of any helpful circumstances over and beyond the ordinary rules.
-- Sun Tzu

How do you win a war? There is no easy answer. If ever there was an art that could not be reduced to a set of axioms, it's war--and perhaps database programming. Admittedly, I have neither fought in nor commanded in any skirmishes, battles, police actions, or wars, but I'm pretty sure that if there was a surefire way to win, it would have been discovered by now. (Well, there is one rule: never start a land war in Asia.)

The same is true with database programming (never
select *). All forms of programming, and of problem-solving more generally, involve trade-offs. But the trade-offs are the greatest with database programming. As the database is the greatest barrier to performance in any application, its design is the most fraught with philosophical and practical dilemmas. I find it very difficult to interview people for database-related jobs, because there are rarely any right answers. It's also difficult to glean advice from books and blogs, because situations vary so wildly.

For instance, there is a trade-off between reads and writes in a database. If you have a lot of reads, you can create indexes to your heart's content, assuming you have unlimited space, which is never the case. Similarly, there is a trade-off between batch processing and real-time transactions. If your database handles both, and you cannot simply schedule batch jobs for off-hours, you will have to prioritize one or the other. Another trade-off is between reporting and online transactions. Even if you report off of a mirrored snapshot, you must accept the timing delay thus incurred.  This list could be extended indefinitely.

An early database under siege

It can be a frustrating realization that there are no general principals by which lowly database programmers abide. But this can be liberating as well. What would be the point of programming if you too could be replaced by a machine following a set of principals? Programmers are the last stop against the ever-increasing automation of the world. Embrace the art!

More practically, there are some things you can do. Once you've achieved a certain level of proficiency, the best you can do--really--is to catalog trade-offs.  I recently ran into one between database complexity and service traffic. It is usually a good idea to reduce the amount of chatter over a web service, but it's also a good idea to write clear, maintainable SQL code. Another trade-off: you can make all your code dynamic in order to deal with the deployment processes and future change, but then you have to deal with a more complex database design.

Stéphane Faroult outlines five factors that contribute most to performance:

• The number of rows in the tables involved
• The existing indexes on these tables
• Storage peculiarities (like partitioning)
• The quality of the criteria provided

Query diagram à la Tow

• The size of the result set

Compare to Dan Tow's query diagrams, which show:

• The join order of tables
• The selectivity of the filters on those tables
• The selectivity of the joins between tables

Of course, performance is only one of many database goals and involves trade-offs at a micro and macro level. For example, decisions have to be made about indexes on particular tables, and about whether performance or maintainability is more important. There aren't any universal truths, just experience and deliberate thought.

What trade-offs have you found?

Antipatterns and the Limits of Language

I recently read Bill Karwin's SQL Antipatterns, which details common design practices that are usually bad ideas. I found Karwin's book interesting from a 'scientific' viewpoint, as it provides a taxonomy of common design mistakes. For example, if you see someone design a column that contains multiple comma-separated values, you can accuse them of 'Jaywalking.' If you see a table that contains key-value pairs in an attempt to add some flexibility to the relatively static nature of SQL metadata, you can yell out 'Entity-Attribute-Value'!

These are not rules set in stone, and Karwin is careful to detail the situations in which each antipattern might have a use. It is worth mentioning here that many of the arguments you see about database design stem from the belief that a one-size-fits-all approach is possible. In the end, however, it is typically business requirements that determine database design, and this can often lead to circumstances that require a less-than-ideal approach from an architectural perspective. What was most interesting for me, however, is the kind of the explanation Karwin provides for why you should not use an antipattern. This always comes in the form of something like: SQL wasn't designed to do that. Why is it a bad idea to use self-referencing tables to represent a tree-structure? Because SQL wasn't designed to do that! You'd have to manage all the updates and deletes yourself, and there's no easy way to traverse the tree--at least, if you want to be ANSI compliant.

On the one hand, this kind of answer makes sense. Why should you normalize tables? Because then you benefit from the functionality SQL was designed to implement--namely referential integrity and non-redundancy. Why is it a bad idea to 'clean up' gaps in auto-generated primary keys? Because the value of a key is only important insofar as it is a uniquefier, not as an actual value. In the end, SQL was designed to solve certain problems and not others. If you have a problem that requires you to use SQL in ways that twist your database's architecture into strange contortions, you'll end up with wasted effort and sub-optimal performance.

On the other hand, this kind of answer is disappointing. If SQL can't solve my problem, what will? If my metadata is constantly changing, what should I use instead of SQL? If my data cannot be represented by relations, how could it be effectively structured? Karwin does not really provide these answers. He does tell us what SQL is good for by telling us what we it is not good for, but this is not the same thing as telling us what we should use instead of SQL. Of course, Karwin cannot be blamed for this. These questions about the limits of a language cannot be answered from within the language itself. When we are actually working in a language, we know when we are at its limits: things become very complicated and require a lot of work. You could do statistical regressions in SQL, but it might take an infinite amount of time! It's really only with experience that we understand which languages--and which paradigms--are useful for which problems.

For all of these reasons, a large part of this blog will be dedicated to my exploration of various languages, paradigms, and their limits. Though this is a seemingly-abstract question, it is one that gets at the heart of design and the ways in which we solve problems.

A few links:
-An excerpt from Karwin's book
-Louis David's Ten Common Database Design Mistakes