Update 3,Nov 2016: When I first wrote this post, there were a lot of opinions/comments (in my older blog) about how I am wrong in thinking about choosing a datastore is almost like choosing a data structure when writing a program. Here is an excerpt from Nathan Marz’s book “Big Data: principles and best practices of scalable real-time data systems” that supports my views. There is nothing satisfying than getting your ideas validated by smarter people than you are.
Original post: Making technology choices, be it choosing commercial products or open-source are becoming increasingly difficult for organisations. Especially, since bigdata became a buzzword everyone wants to move to NoSQL world leaving RDBMs without fully understanding the underlying concepts. Choosing a datastore can be intuitive based on your use cases and here is my take. The book ‘The art of choosing’ by the Canadian B-School professor Sheena Iyengar and this post overlaps only in terms of the title and not the concepts explained. BTW, the word ‘app’ in the title isn’t a shorthand for mobile apps, it generally denotes all kinds of software applications.
Ok, Some background..
Have you ever wondered why choosing a technology or a software product or a framework for our next project has become such a bewildering task ? How many times you felt you have done a good job of choosing as opposed to lived with a lingering apprehension about your choice? Its funny that fragmentation has gotten into open-source products as well, just imagine how many distributed NoSQL data stores are available today promising multitude of things.
Here is a wishful thinking, what if we will be presented with a ‘choice environment’ where choosing is made easy, with all right information which we can understand clearly before choosing ? what if we will still be presented with choices without any form of force ? what if we don’t have to have any apprehensions about the ‘choice environment’ itself as it aims to help as opposed to cause any damage. So basically given our needs the ‘choice environment’ will influence you to make the right decision.
This is the central premise of the book ‘Nudge’ (Richard Thaler and Cass Sunstein) and the idea of influencing your people to make the right choices is ‘Nudging‘. Nudging for good by presenting choices in a way it will be understandable and useful is called a ‘Choice architecture’.
No, I am not ranting about something unrelated, in fact this exactly what we need to make choosing easier when it comes to choosing a data store or anything for that matter.
I hope thats enough background, Let’s focus now on choosing data store for your app.
Basics of storing and retrieving data
The very basic operation every App does is storing and retrieving data.This could be in memory or in disk (or SSD, because you are fancy). The underlying data structure used by the data store for storing and retrieving can make or break your choice. Here a good choice of data store mean different things to different audience. For some it could be space-efficient and for some it could time-efficient, it completely depends on the type of the application and specific use case.
Say, your use case is to store and retrieve related data and the only concern is time-efficiency. when I mean related data, I mean the type of data we used to store in associative arrays (mathematically speaking) or key-value pairs. For instance, it could be a person’s name and her age stored as a pair. In programming world associative arrays are called HashMaps or dictionaries or simply a Key-Value pair. So a programmer could think of this as the right fit as soon as the requirement is to store/retrieve key-values in constant time i.e.O(1).
Now if you think of modern IMDBs or caches like Memcache or REDIS or RIAK they are on the core a key-value pair store. Yes ,they have other fancy features like replication, memory to disk snapshotting, recovery from replica, fault tolerance and so on. But the underlying data structure is an associative array or a hash map or may be even a variant very specific to implementation.
Now that might sound like an oversimplification, you cannot argue that starting with an use case and knowing your data store mechanics will help you choose a near perfect data store.
So takeaway ? – if we start with our use-case it should be straightforward to choose a data structure.
What are we doing wrong ?
I was wondering why data stores aren’t chosen by applying this basic principle above, wouldn’t it make choosing a data store easy and intuitive ?
Instead we get carried away by the fancy jargons, so-called features, marketing materials, explainer videos (on how one product is better than the other) and slide-share presentations. Based on the limited and biased information collected from the above sources we either go with the most popular option or we put together a candidate set for a prototype exercise thinking we choose only with diligent analysis. (and btw it’s a prototype you build and not a PoC, a Proof of concept is only for proving a concept that already didn’t exist, like extracting electricity from human body heat).
Getting back to choosing data stores, you do it either way, most likely it’s going to be a wrong choice unless luckily your choice matched with your app requirements at every level.
Your strategy for choosing a datastore, NoSQL or RDMBS or whatever it is depends on 2 critical parameters.
- Application insights – what kind of application are you building, who you are building for, what is the expected user experience, is it write-heavy or ready heavy, what are the overall latency requirements, application SLAs et cetera.
- The underlying data structure used to store and retrieve the data.
So how to know what’s the underlying data structure used in a data store ?
To get the answer for this question we need to understand first what a database engine or storage engine is. ( Lets call it a storage engine for the rest of the post.)
A storage engine is the part of a database and it is responsible for managing how data is stored on the physical storage and hence the retrieval. Many databases support multiple storage engines, where different engines perform better for specific workloads. For example, one storage engine might offer better performance for read-heavy workloads, and another might support a higher-throughput for write operations. The storage engine typically uses the data structures to do the actual store and retrieve. Also knowing how the 3 critical metrics write amplification, read amplification and space amplification play out for the underlying data structures of the storage engine also is important. Read-amp is the amount of real work done per logical read operation. Write-amp is the amount of real work done per logical write operation. Space-amp is the ratio of the size of the database to the size of the data in the database. You will understand them practically as we move forward. (more details here and here).
Some top data structures used in popular data stores
B+-Tree is a balanced binary search tree in principle and is used to index data in my data stores. If you need a refresher you could see how a simple Binary search tree (BST) works here. Below figure will help you understand a basic BST insert
As you can see from the figure,
- B+-Trees are fast at sequential inserts
- B+-Trees are slow at Ad Hoc inserts
- B+-Trees incur disk seek for every insert and disk seeks are slow.
- If we add indexes to optimise read performance, write performance will be affected
- Write amplification is very high is B+-Trees
LSM trees are designed to provide better write throughput than traditional B+ tree.
Why ? At its core it’s the old problem of disks being slow for random operations, but fast when accessed sequentially. Regardless of whether the disk is magnetic or solid state or even, although to a lesser extent, main memory sequential access is faster than random access.The figures in this ACM report here/here make the point well. if we are interested in write throughput, what is the best method to use? A good starting point is to simply append data to a file. This approach, often termed logging or journaling. But the downside is reading data from log files can be slow. This means logs are only really applicable to simple workloads, where data is either accessed in its entirety, as in the write-ahead log of most databases, or by a known offset, as in simple messaging products like Kafka.
LSM tree is basically a hierarchy of B+-Trees B0, B1, B2 where these will be merged later.
It’s nearly a decade since Google released its ‘Big Table’ paper. One of the many cool aspects of that paper was the file organisation it uses. The approach is more generally known as the Log Structured Merge Tree, after this 1996 paper (although not specifically referenced as such by Google). LSM is now used in a number of products as the main file organisation strategy. HBase, Cassandra, LevelDB, SQLite, even MongoDB 3.0 comes with an optional LSM engine, after it’s acquisition of Wired Tiger.
Read amplification is very high is B+-Trees. Remember reads take a hit in LSM trees, yeah worse hit than B+-Trees.
Fractal Trees (proprietary of Tokutek)
What may not be so familiar is Tokutek‘s Fractal Tree Indexing technology that is supposed to be even better than B+ trees and LSMs. As explained by the Tokutek folks it topologically looks like a B+-Tree and buffers/merges like a LSM so this hybrid approach yields better read and write performance.
Now getting back to Nudge and choice architecture – I am wondering when would database companies will market their offerings in a way audience can understand and relate features to the values. When will they make all the required technical information accessible to make a good decision. When will they publish unbiased benchmarks.
Until that time, how popular social media site Quora decided to use MySQL and why Facebook ditched MySQL for NoSQL will remain unclear.
Knowing key app insights and information about your storage engine and in turn the underlying data structures can help you pick a reasonably good data store for your app. If your app is too big and has multiple parts and by our principle each parts deserves different types of data stores that’s when you go for a polyglot persistence model. Mix and match.
Choose right data store(s), build a great app !
- Here is a good video on how B+-Tree works.