Applicative 2016 / Speakers

Mark Callaghan


Read, write and space efficiency – pick two

Read, write and space efficiency make it easier to compare database algorithms. By efficiency I mean the amount of work, CPU and storage, per user request. While the algorithms for a b-tree and log structured merge tree are different, in the end we can measure their efficiency for real workloads and then make models to explain what we measure. I don’t think it is possible for one algorithm to be optimal for read, write and space efficiency. Therefore we can pick the algorithm based on the one or two efficiency metrics that matter most for each deployment. I will discuss how to do that in the context of MySQL and MongoDB now that we have a RocksDB storage engine for both.


Mark Callaghan worked with great teams to make MySQL better for web-scale deployments at Facebook and Google for more than 10 years. His current focus at Facebook is RocksDB, MyRocks and MongoRocks. Prior to his web-scale work he spent many years working on RDBMS internals at Oracle and Informix. He invented and implemented a fast sort algorithm for the Oracle RDBMS. He has an MS in CS from UW-Madison.

Twitter: @markcallaghan

© 2016 ACM.