Druid – A Column Oriented Database

I attended a talk at Philly ETE by Metamarkets, a company doing real-time analytics for advertising. Having worked on a couple Oracle-based reporting projects, I entered with interest. Their system is built around dimensional modeling, although with atypically high volume inserts and low latency for updating reports. They attempted to build this system with a traditional relational database (star schema + pre-computed fact subsets), and then when that didn’t work out, they tried using a key-value store (!) with many possible queries pre-computed.

Rather than purchasing a database from EMC (Greenplum) or Oracle, they decided to roll their own, which apparently is cheaper(?!). Likely, the reason this works is that there are an increasing number of OSS components, such as Zookeeper, Kafka, Hive, etc, so one can construct a bundled database product (a similar model to HortonWorks). Their system is called Druid, and was recently released as an open-source project, although as of this writing they admit it’s not the easiest thing to configure and stand up.

Unsurprisingly, the solution they built makes extensive use of bitmap indexes. Fact table data is partitioned into batches of up to a 1-2 million rows – each dimension is produced per batch, then query results are merged. This limits the cardinality of dimensions – each bitmap index will have no more unique values than rows in the partition. Bitmap indexes are nice, in that they can be ANDed and ORed directly in large batches, with one bit per unique value, so are much smaller than the source data. In fact, this data is also compressed in a way which can allow for boolean operations to work – Metamarkets claims the resulting index is 30-40% the size of an inverted index. Incidentally, there is a handy Java implementation of this compression algorithm.

This system appears to allow much wider scaling than a typical RDBMS (e.g. 100 nodes), and mitigates network I/O by tracking which nodes control a segment of data (they’re not the only DB vendor who has this – perhaps it’s a feature of zookeeper?). Data segments are also considered immutable – when changes are made, a new segment is created, the old one soft-deleted, and background jobs run nightly to clean up duplicates/leftover data.

More information here-

http://metamarkets.com/2011/druid-part-i-real-time-analytics-at-a-billion-rows-per-second/

http://metamarkets.com/druid/

Leave a Reply

Your email address will not be published. Required fields are marked *