Database selection

Highlighted from System Design Interview Fundamentals, Chapter 5

Introduction

:brain: All databases will scale, otherwise they wouldn’t be competing in the database space. And yes, MySQL scales too.

“I will use NoSQL over MySQL because it’s more scalable.” —> not a legit reasoning.
Most of the time relational databases do scale, and all big companies use them.
Relational databases may not scale only for particular use cases, and there are better options, and you should be clear about why.
Databases are very complicated and are often not an apples-to-apples comparison. In an interview, it’s really about if they make sense, and how you sell your justifications to the interviewer. Also, keep in mind that you may need more than just one database for different use cases in a single question.
Many people use the CAP theorem to justify a database.
Interviewers generally aren’t too interested in the specific technology. Instead, they’re usually more interested in the fundamentals of the category of the database.
- Relational Database
- Document Store
- Columnar Store
- Object Store
- Blob Store
- Wide Column Store
- Reverse Index Store
- In-Memory Store
- Geo-Spatial Databases
- ZooKeeper

Databases will not impact your functional requirements.

Whichever database you use you can still achieve your functional requirements somehow, but at the cost of huge performance degradation. So when we say requirement, we usually mean non-functional requirements.

Factors

Structure of the data
Query pattern
Amount or scale that you need to handle

Relational Database

Example: MySQL, Postgres

(+) Easy to represent the entities as tables and define the relationship between them.
(+) It supports transactions to write to one or many entities and
(+) Supports simple to complex read queries.
(+) You’re able to add in an ad-hoc index to improve the read performance at the expense of write performance.
(+) If you have multiple entities with shared attributes, you can fetch results with a joined or unioned table.
(+) Also, it supports updates for a record well. (Some databases are append-only.)
You can normally consider using a relational database by default unless you find a better reason to use another database choice.
- if the use case is metrics collection where there’s a high write ingestion without the need to join tables and is append-only, a relational database probably “doesn’t scale” for that use case.
Relational databases can provide stronger data integrity through transaction guarantee.
- If you’re designing a file system with a table folder and a table file. If the folder table has a column called number_of_files, you may have a transaction to add a file in that folder and increase number_of_files by 1. If the database increases number_of_files by 1 first and the operation to add a row to the file table fails, number_of_files will get rolled back.
Note: Many resources will claim that relational databases have good ACID properties. However, ACID is a very high-level term that isn’t necessarily unique to relational databases.

Document Store

Example: MongoDB, Amazon DocumentDB

You should use a document database if the data you are storing is unstructured and doesn’t fit well in a relational database.
- For example, if you’re storing a product catalog where the schema between each product catalog could differ significantly, creating a relational table with all the known columns may be wasteful, since the storage will be sparse.
Documents can use formats such as JSON and XML, and if your data fits naturally to those representations, then it’s a good fit.
In an interview setting, the data is usually structured unless the interviewer intentionally sets it up in a way that they’re looking for a document store.
When in doubt, favor relational over document since it’s just easier to deal with the flexibility of different queries by having tables.

Columnar Store

Example: InfluxDB, Pinot.

The columnar store has a schema that looks the same as a traditional relational database. However, columnar stores are more optimized for Online Analytical Processing (OLAP) queries to fetch data in a column fashion.
What is column fashion? For example, table looks like:

id	Date	Hours Played	Score
1	1/1	5	6500
2	1/2	6	700
3	1/3	3	500

traditional row oriented relational database, each row is physically stored together:


1, 1/1, 5, 6500
2, 1/2, 6, 700
3, 1/3, 3, 500

Columnar store, data is stored in a columnar fashion:


1, 2, 3
1/1, 1/2, 1/3
5, 6, 3
6500, 700, 500

If you want to provide a time series of “Date” and “Score,” you will need to access multiple rows in traditional data base, which is inefficient. This difference becomes more apparent when there are more rows, like in time series and analytics queries.
This query pattern is good for analytics databases and time-series databases which have a lot of overlaps.
For a time-series database that stores its data in a columnar fashion, writes happen more frequently than read. Update to any record is rare since most are append-only.
When deletion happens, the deletions happen in batches instead of an ad-hoc operation like in a relational database.
In a system design interview, a good candidate for a columnar store would be an analytics dashboard.
- Most analytics dashboards show some sort of graph with an x-axis and y-axis. And for each graph, you will want to fetch a series of data to be displayed on the dashboard.

Object Store

When you’re designing to store objects like photos, videos, file documents, etc. You need to handle objects differently due to the potential amount of data taking up the bandwidth and storage.
Blob storage is a type of object storage. Object storage keeps files or blobs in a flat “data lake” or “pool” with no hierarchy
- a data lake/pool is a large collection of unstructured data.
Object storage contrasts with file storage and block storage:
- File storage keeps data in a hierarchical file structure of folders, directories, subdirectories, and so on
- Block storage keeps data in similarly sized volumes of data called “blocks”
File and block storage are often not flexible enough or scalable enough for modern organizations. By contrast, object storage is so scalable that some consider it to be “unlimited” storage. However, using object storage instead of file or block storage can make data retrieval more complicated.

Blob Store

Example: Amazon S3.

Blob storage is a type of cloud storage for unstructured data.
A “blob,” which is short for Binary Large Object, is a mass of data in binary form that does not necessarily conform to any file format.
- Blobs do not have to follow a given format or have any metadata associated with them. They are a series of bytes. Any type of data can go in a blob.
Blob storage keeps these masses of data in non-hierarchical storage areas called data lakes. Imagine …
- Alice stores her clothes in curated outfits that are ready to be worn, while
- Bob simply tosses his clothes into a pile.
- Bob’s method is more like blob storage: any item of clothing can go into his pile, and the clothes do not have to be organized in any particular way.
- Bob’s method is advantageous in that he can quickly and almost endlessly grow his pile of clothes: he can just toss more on, instead of folding and organizing them like Alice.
- Even though Bob’s clothing storage method makes it more difficult to quickly locate specific clothing items, many organizations need a similar data storage approach. They have a lot of data, and they need to store large volumes of it without organizing it into a hierarchy or fitting it into a given format.
Blob storage enables developers to build data lakes for cloud-based and mobile applications.
Blob storage is particularly useful for storing media, large file backups, and data logs.
- Most organizations need to keep complete backups, particularly for recovering from ransomware attacks. As this data is duplicated in production and rarely accessed, blob storage is well-suited for backing up large data sets.
Blob stores are immutable. Once stored, you can not change the file. You can change by inserting or appending new data.
If you try to store a blob in a relational database, you will take up a lot of memory on the table and worsen the performance of the regular OLTP transactions.
In a system design interview, good candidates for a blob store would be:
- Design Instagram:
  - For Instagram, assuming you’re storing videos and images for each post, you will want to store the videos and images in a blob store.
- Log Storage: When you need to store logs, you can consider using an object store to store the log dump.
- File Storage:
  - For any files that you need to store, you can use object storage.
  - For example, if the interviewer asks you to design a system that takes in a pdf of CSV and has a data pipeline to process the files, you may want to store the pdf or CSV in the object store and have some pipeline pull from the object store to be processed.

Wide Column Store

Example: Big Table, HBase, and Cassandra

From the outside, the term “wide column” is just the schema. However, it’s coupled with some popular databases like Big Table, HBase, and Cassandra.
Internally, those wide column databases use LSM indexing strategy, which is more optimized for writes. Also, within a column family, data are stored together physically next to each other for a given row.
Wide column store works well when there’s a lot of data collected at a very high write speed. The read performance is also great when the read targets a row key that is defined.
A wide column store isn’t good when you need to do joins across tables.
Although a wide column store doesn’t support ad-hoc modifications to a persisted value, the read query does well when it is append-only.
In an interview, a wide column store can be a good candidate for questions like:
- Design Facebook Chat:
  - The chat messages usually come into the system with a high write throughput and typically appends only. On read, it’s usually reading a list of messages for a chat_id.
- Design Metrics Collection:
  - For the metrics collection type of question, the write throughput is usually very high because metrics are generally assumed to omit data constantly.
  - Your system has to deal with the high rate of data collection.
  - The read query targets a group of specific device_id’s that omit the metrics without a complex query.
(Note: even within the wide column database type, there are different replication strategies.)
- HBase uses a leader-follower replication, whereas Cassandra uses a leaderless replication.
- Because of the leaderless replication, Cassandra has to deal with conflicting writes with lower consistency than HBase.
- In an interview, you can pick one of the two based on your design requirement, and it’s worth talking about your strategy on conflict resolution if you decide to use a leaderless solution like Cassandra.

Reverse Index Store

Example: Examples Elastic Search, Lucene.

When designing for a search-related problem where you need to build reverse indexes, you can consider a reverse index store.
Internally a reverse index is just a key-value store where the key is the term token, and the value is the item you’re searching for.
- (A posting list is an abstract term for the item you’re searching for.)
Some example:


Document 1: “my dog house”
Document 2: “their dog”
 
#reverse index
“dog” → [doc1, doc2]
“house” → [doc1]
“my” → [doc1]
“their” → [doc2]
 
# query
"dog AND house" : [doc1]

In-Memory Store

Example: Redis, Memcache.

Sometimes you may not need to go to disk if the requirement is to achieve better performance at the cost of worsened durability.
- For example, if you need to store the driver locations for a ride-matching service, it’s not critical to have durability since the location changes frequently.
- If you need the locations for analytics, you can write back to another database. If analytics isn’t a core use case, you don’t need a database here.

Geo-Spatial Databases

Examples Google S2, MongoDB Geo Queries.

Geospatial databases are great to use for location-based queries. For example, given a coordinator longitude and latitude, give me all the points within a radius, polygon, or custom shape supported by the database.
Geo-spatial database is helpful for questions like the following:
- Design Yelp: For a given point on the map, give me all the interesting points of interest within a particular region.
- Design Find My Friend: For a given point on the map, give me all the friends near me.
A geodatabase is a very niche database, so it’s doubtful the interviewer will go too deep into this. Few keywords for further read: Quadtree, 2dsphere index, Hilbert Curve

ZooKeeper

Examples Chubby, ZooKeeper.

ZooKeeper is more than just a store. But it’s worth talking about storage since ZooKeeper is commonly used to store configurations and name registries.
In addition, you can use ZooKeeper because it provides strong consistency with good fault tolerance to the end-user.
In a system design interview, here are some places where A ZooKeeper may be used:
- Shard Manager
  - You will have a list of physical nodes you need to call for a given logical shard. You can store this information in ZooKeeper.
  - Knowing this might come in handy if the interviewer asks you for more detail about your sharding architecture.
- Configuration Manager
  - If you have an application that needs to read a global configuration service that needs to be strongly consistent, you can consider ZooKeeper.
- Leader Election
  - When you have a chosen leader-follower replication for your database when you’re discussing the fault tolerance of your database, you can mention that ZooKeeper will monitor the health of your leader and follower nodes and perform an election to elect a new leader.
The intuition is that ZooKeeper uses a consensus protocol to ensure the cluster is fault-tolerant by selecting a leader when it is down. It also uses a consensus protocol to ensure the writes are strongly consistent.
- Strong consistency means that multiple clients read the data as if there is just a single object.
- In reality, multiple machines are powering this strongly consistent property. This property is also known as linearizable.
Since the configuration and name registries have low write-to-read ratios, writes are usually strongly consistent. To scale for reads, you can scale by asynchronously replicating read replicas at the expense of less consistency.
Consensus protocols like Zab, Paxos, and Raft is a very deep and complicated topic. It is unlikely an interviewer will ask you about the nitty-gritty of a consensus protocol unless you have deep experience in that area.