February 21, 2010

MongoDB Sharding

Messed around today with MongoDB sharding on version 1.2.2. It was pretty easy to setup. All I had to do was:

  1. Download MongoDB
  2. Do this setup

Here’s the question that prompted me to try it: does MongoDB only fetch the necessary subset of chunks when doing range queries? The short answer is yes, it does. It was natural to assume it would, but I wanted to see it in action.

To test this, I created the test.people collection from step 2 above, then ran this with the mongo client:

for (i=0; i < 3000000; i++) { test.people.insert({name: i}) }

When that finished, I had three chunks.

> printShardingStatus(db.getSisterDB("config"))

--- Sharding Status ---
sharding version: { "_id" : ObjectId("4b7df95cc03e000000005d6b"), "version" : 2 }
shards:
{ "_id" : ObjectId("4b7df969c03e000000005d6c"), "host" : "localhost:10000" }
{ "_id" : ObjectId("4b7df96ec03e000000005d6d"), "host" : "localhost:10001" }
databases:
{ "name" : "admin", "partitioned" : false, "primary" : "localhost:20000", "_id" : ObjectId("4b7df969b90f00000000
56aa") }
my chunks
{ "name" : "test", "partitioned" : true, "primary" : "localhost:10001", "sharded" : { "test.people" : { "key" :
{ "name" : 1 }, "unique" : true } }, "_id" : ObjectId("4b7df982b90f0000000056ab") }
my chunks
test.people { "name" : { $minKey : 1 } } -->> { "name" : 0 } on : localhost:10001 { "t" : 126654
7599000, "i" : 4 }
test.people { "name" : 0 } -->> { "name" : 2595572 } on : localhost:10001 { "t" : 1266547599000,
"i" : 2 }
test.people { "name" : 2595572 } -->> { "name" : { $maxKey : 1 } } on : localhost:10000 { "t" :
1266547599000, "i" : 5 }

You’ll see that three chunks exist above. Two are on one shard, one is on the other. The important point to notice is that one is for [0, 2595572) and another for [2595572, maxkey). I’m not sure why [minkey, 0) and [0, 2595572) wasn’t just [minkey, 2595572), but that’s something for another day. For the purposes of my range test, this suffices.

I then tried operations such as:

> db.people.find({ name: { $gt: 1, $lt: 3 } } )
{ "_id" : ObjectId("4b7df9c85a4800000000485d"), "name" : 2 }

> db.people.find({ name: { $gt: 2595573, $lt: 2595575 } } )
{ "_id" : ObjectId("4b7dfb8f903c000000003c92"), "name" : 2595574 }

> db.people.find({ name: { $gt: 2595570, $lt: 2595575 } } )
{ "_id" : ObjectId("4b7dfb8d5a4800000027e34f"), "name" : 2595572 }
{ "_id" : ObjectId("4b7dfb8f903c000000003c91"), "name" : 2595573 }
{ "_id" : ObjectId("4b7dfb8f903c000000003c92"), "name" : 2595574 }
{ "_id" : ObjectId("4b7dfb8d5a4800000027e34e"), "name" : 2595571 }

I watched the mongod output on these finds. The first two queries only hit one shard. The last query hit both shards. So MongoDB does in fact only query the necessary chunks even when doing range queries.

August 11, 2009

Database Normalization: First, Second, and Third Normal Forms

I read a great explanation of first, second, and third normal form a few weeks ago. For those that know what database normalization is but haven’t seen the “forms”, the different forms are essentially rules for having a well normalized relation DB. Keeping them in mind when doing DB design is key to keeping a great database. I’d like to make an attempt at condensing the linked tutorial into its essentials.

First Normal Form (1NF): No repeating elements or groups of elements

Don’t repeat your columns. Avoid this:

OrderId ItemId1 ItemId2
1 100 101

ItemId1, 2, … should be split out into relational tables.

Second Normal Form (2NF): No partial dependencies on a concatenated key

This is a complex way of saying that if a column isn’t intrinsically related to the entire primary key, then you should break out the primary key into different tables.

Example:

OrderId (PK) ItemId (PK) OrderDate
1 100 2009-01-01
1 101 2009-01-01

The primary key is (OrderId, ItemId).

Consider OrderDate. It is conceptually part of an order. An order always occurs at some time. But is an OrderDate related to an Item? Not really.

You may be saying, “but items are part of an order!”, and you would be right. But that’s not what I’m getting at. OrderDate is independent of the item itself.

Look at another way: in the table above the OrderDate will always be the same for a given OrderId regardless of the value of the ItemId column. This means data duplication, which is denormalization.

Here’s how we correct the problem:

Orders
OrderId (PK) OrderDate
1 2009-01-01
Order_Items
OrderId (PK) ItemId (PK)
1 100
1 101

Here is an excellent line from the article, “All we are trying to establish here is whether a particular order on a particular date relies on a particular item.”

Third Normal Form (3NF): No dependencies on non-key attributes

2NF covers the case of multi-column primary keys. 3NF is meant to cover single column keys. Simply stated, pull out columns that don’t directly relate to the subject of the row (the primary key), and put them in their own table.

Example:

Orders
OrderId (PK) OrderDate CustomerName CustomerCity
1 2009-01-01 John Smith Chicago

Customer information could be the subject of its own table. Pull out customer name and other customer fields into another table, and then put a Customer foreign key into Orders.

Wikipedia has a great quote from Bill Kent: “every non-key attribute ‘must provide a fact about the key, the whole key, and nothing but the key’.”

June 21, 2009

MySQL Join Performance

Earlier this week I was curious about the performance of JOINs in MySQL. How severe is the performance hit of joins? How much slower is a string join over an integer join? I decided to do some tests, and I’m going to share my results here.

I did these tests on a computer with the following specs and software:

  • 3.2 GHz Pentium 4
  • 2 GB of RAM
  • Windows XP
  • MySQL 5.0.51b running in development mode (no query caching)

I made two tables:

CREATE TABLE `parents` (
`id` int(10) unsigned NOT NULL auto_increment,
`uuid` varchar(128) default NULL,
`time` datetime default NULL,
`string` varchar(128) default NULL,
PRIMARY KEY  (`id`),
UNIQUE KEY `uuid` (`uuid`),
KEY `time` (`time`),
KEY `string` (`string`)
)

CREATE TABLE `children` (
`id` int(10) unsigned NOT NULL auto_increment,
`uuid` varchar(128) default NULL,
`parent_id` int(10) unsigned NOT NULL,
`parent_uuid` varchar(128) default NULL,
`time` datetime default NULL,
`string` varchar(128) default NULL,
PRIMARY KEY  (`id`),
UNIQUE KEY `uuid` (`uuid`),
KEY `parent_id` (`parent_id`),
KEY `parent_uuid` (`parent_uuid`),
KEY `time` (`time`),
KEY `string` (`string`)
)

I filled these tables with records using the following Ruby code:

require 'mysql'
require 'digest/sha1'
require 'base64'

RECORDS   = 10_000
stringS = ['blue', 'red', 'green'].freeze

my = Mysql::new("localhost", "user", "password", "db_perf")

my.query("DELETE FROM parents")
my.query("DELETE FROM children")
my.query("ALTER TABLE parents  AUTO_INCREMENT = 1")
my.query("ALTER TABLE children AUTO_INCREMENT = 1")

def make_uuid(arg)
Digest::SHA1.hexdigest(arg.to_s)
end

start_time = Time.now.tv_sec
(1..RECORDS).each do |i|
if ((i % 500) == 0)
puts "Iteration #{i}"
time    = Time.now.tv_sec
elapsed = time - start_time
time_per_record = elapsed.to_f/i
time_to_complete = time_per_record * RECORDS
puts "Minutes to complete: #{time_to_complete/60}"
end

uuid   = make_uuid(i)
time   = Time.at(i * 3600).strftime('%Y-%m-%d %H:%M')
string = stringS[i % stringS.length]
res  = my.query(
"INSERT INTO parents "                 +
"(uuid, time, string) VALUES " +
"('#{uuid}', '#{time}', '#{string}')" )
res  = my.query(
"INSERT INTO children "         +
"(uuid, time, string, parent_id, parent_uuid) VALUES " +
"('#{uuid}', '#{time}', '#{string}', #{i}, '#{uuid}')" )
end

puts ''
puts 'DONE'
end_time = Time.now.tv_sec
elapsed = end_time - start_time
puts "Elapsed time in minutes: #{elapsed.to_f/60}"

The table engine you use and the character encoding will make a difference. Why? Because the engine will affect how keys are stored and used, and the character encoding will affect the speed of string comparisons.

I use Rails these days, and when dealing with Rails, InnoDB (which is transactional) and UTF8 are common, so let’s look at them:

image

image

Blue designates queries without a join. They are:

Select Group by String SELECT * FROM children GROUP BY string
Select Group By Time Func SELECT * FROM children GROUP BY YEAR(time), DAYOFYEAR(time)
Select SELECT * FROM children

Red designates queries with a join, which are:

Join Integer Group by String SELECT * FROM children INNER JOIN (parents) ON (children.parent_id = parents.id) GROUP BY parents.string
Join Integer Group by Time Func SELECT * FROM children INNER JOIN (parents) ON (children.parent_id = parents.id) GROUP BY YEAR(children.time), DAYOFYEAR(children.time)
Join String Group by String SELECT * FROM children INNER JOIN (parents) ON (children.parent_uuid = parents.uuid) GROUP BY parents.string
Join String Group by Time Func SELECT * FROM children INNER JOIN (parents) ON (children.parent_uuid = parents.uuid) GROUP BY YEAR(children.time), DAYOFYEAR(children.time)
Join Integer SELECT * FROM children INNER JOIN (parents) ON (children.parent_id = parents.id)
Join String SELECT * FROM children INNER JOIN (parents) ON (children.parent_uuid = parents.uuid)

The 10K queries were run 10 times, and the 100K queries were run 6 times. I did a warmup round before each measured round (so for a 10K query, that means 10 times to warmup, 10 times to measure). The times you see in the charts are the average times. Be sure to turn off query caching.

The results speak for themselves, so I’m offering them up with no analysis for now.

May 31, 2008

On Database Abstraction, PHP, and Ruby

It took me a couple days on my current PHP/MySQL project to get the DB abstraction with proper error handling, input validation, and relational support coded to the point where I’m happy with the model. This was after trying Zend_Db, Doctrine, and Propel, which are all good libraries, but I hit points where the work of getting it to do what I wanted efficiently just wasn’t worth it. I decided it would be faster to just roll my own slim library.

I’m always mystified at why DB models are such a hassle to code, so I spent a little time reading. I think I get it now. It has to do with the mapping problem between relational systems and object oriented systems.

Ted Neward, writer of several books on C# and Java, calls this “The Vietnam of Computer Science“. What he’s saying is that object-relational mapping (ORM) quickly reaches a point of diminishing returns. The problem stems from the conceptual disconnect between the language and the data store.

Hoping to shed additional light on the subject, I went looking for alternative perspectives to my PHP/MySQL solution. Since it’s all the rage for ease of use, I was mostly curious about Ruby, the Rails framework, and object oriented databases.

Ruby is certainly different, but after some reading, I’m starting to understand why the language lends itself better to the OO style of DB abstraction. On top of that, Rails has powerful scaffolding that lets you flesh out pieces very fast without the code getting ugly. With ActiveRecord in mind from the ground up, things can be pretty elegant some times.

I also found some really cool systems for bridging the gap between languages and data stores. For instance, check out MagLev for Smalltalk/Ruby. Imagine using an OO DB so you don’t have to do the relational mapping, doing it in a distributed fashion, and using things like shared memory more efficiently as an object staging area between your running site scripts and the DB. That’s kind of MagLev.

All of this is interesting, but for the current project I’m sticking with PHP. However, on the next project I might try Ruby on Rails. I want to see first hand if and how it overcomes some of the challenges.

On a slightly tangential subject, a part of me really dislikes the weak typing of both Ruby and PHP. The net effect in PHP is that you pretty much end up using arrays for everything, making it hard to keep track of structure. Ruby on Rails does get around some of the weak typing issues with some better built-in validation, scaffolding, and member attributes (I’m not sure if that’s what they call them). Sometimes I’d rather be doing C#.