Scalability

What Tarzan could teach us

Many years ago, I wrote my first magazine column about what I called the “Rhino Algorithm”; if you have ever seen an old Tarzan movie, you remember that Tarzan would avoid becoming African road pizza by simply jumping to one side and letting the rhinoceros charge past him. My point in the article was that jumping aside is an algorithm that does not scale well to a herd of rhinoceroses.

Today we have two kinds of scalability problems: more data and more users. Neither of these problems can be solved by simply buying more hardware. This used to work better with file systems, since linear growth in the data usually meant linear growth in the program run times. One more record or terminal meant one more cycle through the main program loop. A larger database will require totally different storage structures. You may want to look at some of Ralph Kimball’s old columns on data warehouses to see what that side of the trade does for large static datastores. But looking at the database I have today, how can I tell it will be a problem in the future?

One indication that your database will have problems with really large data sets is whether or not the vendor exposes row numbers to the users. If you have a row ID of some sort, it means that the data is stored in physically contiguous columns. This is a lousy way to store very large amounts of data. You want to replace the contiguous columns with a pointer or bit vector structure that will assemble the row on demand. Another giveaway is how tightly it is tied to a particular operating system. A small single-user operating system obviously will not handle a large multiuser database very well. But things can be more subtle. What were the assumptions about file sizes, datatypes, file locks, and so forth in the operating system that the database system will inherit if they are tied together?

For example, if a particular client/server operating system evolved from a Nintendo game, the developers inside the company might seriously propose putting graphics drivers into ring zero and kicking out file locking on the grounds that users want to see their screens refresh faster (and besides, if your database crashes, you can always reboot).

File and storage speed is vital for a large database. Gaps are fine for smaller files, so old mainframe systems used to require users to allocate physical blocks with a fixed number of records to each block. This usually resulted in a little waste in each block (not tragic when 95 percent or more of your files are well under one gigabyte). But it starts to add up with tables that are in the terabyte range. The time to read a physical device is far greater than the time to internally compute the location of a properly stored chunk of data.

To use an analogy, consider the Library of Congress. It stores approximately 18,000,000 books and is adding approximately 300,000 new volumes each year. The Library runs out of storage space faster than you do! It can keep the books in strict Library of Congress order and build more buildings. However, one group inside the Library has proposed shelving books by size with all the large books on big shelves and all the small books on small shelves, so that there would be no space wasted on “holes” in the book shelves. This will increase available space by a third and not require new construction. But both proponents and opponents admit that fast retrieval will require a good indexing system and batching of requests.

But storage and VLDBs are not the only ways to scale up a system. At the other storage extreme, we are seeing main-memory databases. Why would you want one of these creatures? Simply because they have a throughput up to 20 times faster than the memory-resident cache of disk-based database systems. This is very attractive to e-commerce sites, which scaled up the number of users in ways beyond our control, but do not have very large databases and complex queries.

If you would like to take a look at one of these sites, Angara Database Systems (www.angara.com) announced Angara Data Server, the first main-memory database to operate on the Linux platform at the LinuxWorld conference in March of this year. The Angara Data Server runs under Red Hat Linux 5.2, in addition to other available versions of the Linux platform.

Tarzan changed his platform from live action to computer animation. You might find that you are in the same situation with your database and have to drop what you were doing to scale up.

Joe Celko is an Atlanta-based independent consultant. He is the author of three books on SQL -- SQL For Smarties (Morgan-Kaufmann, 1995), SQL Puzzles and Answers (Morgan-Kaufmann, 1995), and Instant SQL Programming (Wrox Press, 1997) -- and wrote the SQL for Smarties column for DBMS magazine. You can contact him via email at www.celko.com or 71062.1056@compuserve.com.