Database Comparisons

SQL Databases

• relational normalized data (minimum duplicate data)

• Uses B Tree or B+ Tree indexing, where B+ Tree is more common

• Fast reads but slow writes

• good for situations where correctness is more important than performance, like banking, job scheduling, etc.

• ACID compliance with transactions

• in MySQL, data whose primary keys are close together are stored together, only secondary index would required random disk access

• but in PostgreSQL, this does not apply. In PostgreSQL, all indexes are considered as "secondary index", so all disk access are sort of random.

  • this results in a little faster write, but deteriates read (not really). however, PostgreSQL's storage engine does employ strategies to improve data locality within the heap (table), minimizing the impact of random disk access.

How does SQL handle unexpected system shutdowns?

• SQL uses WAL (write ahead log) to logs every commands. Insert/Update/Delete are first written to WAL before executed
• Only a "COMMIT" command in WAL indicates commit, others are ignored
• It is possible that there maybe inconsistencies between WAL and actual data state, for example WAL was written but actual data is not, this is why all play backs in WAL are done in an idempotent way, that is running the query multiple times will have the same effect as if the query was run only once
  • for example: insert with an id, so insert it again will not succeed
  • for example: record the state before the update, and only run update if the data state is identical to the before state
  • for example: delete with an id

NoSQL Database

• Some uses B Tree (mongoDB)
• Mostly uses LSM Tree (Memtable + SSTable)
  • Memtable is a balanced binary search tree in memory
• Fast writes to memory
• Search is slow because it may have to search many SSTables for the target key. Each SSTable requires O(Log(n)) to search (binary search because each SSTable is sorted), and O(n) for all the SSTables

Column Oriented Storage

• ref: Jordan

• Stores data column wise

• Pros:

  • Range query for a column is fast, because these data are stored together on disk
  • Therefore it's ideal for analytical use cases where only specific columns are needed to do calculations like mean or stddev, etc.
  • Column Compressions can be used to compress data, result in faster data transfer and more data in memory
    • a way to represent the entire column's data and store it has another strucutre, maybe a table?
    • assumption: there are some pattern in the column data, there are duplicates, the values are within a range
    • column bitmap representation => run length encoding
    • Dictionary Compression: assigning each data candidate a sequential number, then use than number to represent the data. of course a dictioanry needs to be maintained to store the mapping between data to its number
      • again only useful if there're lots of repeated data in the column
  • Predicate Pushdown
    • divide the column into sub files, each files maintains some stats data about the data within, for example: min, max, sum, average
    • when querying, for example count where value > 60, we can use the stats data to decide if we can skip that specifie subfile or that specific chunk of data

• Cons:

  • Every column must have the same sort order!
  • Each write needs to go to many different places on disk, because each column is stored separately

• Some real world examples: Amazon Redshift, Google BitQuery, Snowflake, ClickHouse, vertica

Columnar Database

Graph Database

MongoDB

• a NoSQL database with B+ Tree indexing
• document data model
• denomalized: data that need to be accessed together should be stored together, minor data duplication is ok
• supports transaction
• flexiby schema
• usually used in chats, but rarely makes sense in other system design situations. nothing is "special" about it.
• more like a SQL database without the need of table joins, or a "NoSQL" style of SQL database
• ACID compliance with transactions

Riak

• Key-value store
• multileader/leaderless replication
• uses LSM tree
• CRDT for write conflict resolution
• good for high write volume, where consistency is not as important, all writes and reads go to the same shard

HBase

• WideColumnStore | Strong Consistency | No ACID
• single leader replication, no write conflicts
• uses LSM tree
• uses column wide storage (data in the same column are stored together)
• good for application that need fast column reads
  • for example instagram, all images of the post are stored in the same column, so can be quickly queried, compared to row-wide storage where you need to read the image column from all rows

Memcahced and Redis

• KeyValue Store | ACID with Transactions | Eventual Consistency
• uses hash map
• good for extremely quick read and writes, like cache, or geo spatial index for Lyft
• not good for range queries
• can be expensive, because storing in memory is more expensive than storing on disk
• ACID compliance with transactions

Neo4j

• GraphDB | Strong Consistency

Timeseries

• TimeScaleDB / Apache Druid
• IoT sensor data
• uses LSM tree

NewSQL

• VoltDB
  • SQL in memory
• Spanner
  • SQL with GPS clocks

What is partitioning and what is sharding?

• partitioning: divide a table into subsets within the same node
• sharding: a more advanced and distributed form of horizontal partitioning
  • range-based sharding: good locality, but bad if hot spots exist
  • hash-based sharding: evenly distributed, but no data locality for range queries
    • to mitigate data locality issue, we can use a secondary index
  • geo-based sharding:

What is secondary indexes?

• additional index on a different column

• local secondary index:

  • an additional index on the column in each of the sharded nodes
  • reads need to query from all nodes
  • write is same as before, still write to one shard

• global secondary index:

  • copy all data, order them by the new index, and shard those
  • two copies of the data, possibly belonging to two differents nodes
  • faster reads, because no need to read from all nodes anymore,
  • horrible write, because we need to maintain consistency between the two seconds of data possiblly located on two nodes. Distributed transaction and 2 phase commit is required in this case.

• example of local secondary index:

  • table is sharded based on user_id
  • secondary index is based on age
  • query users whose age is in (30, 60)
  • since shard key was user_id, there is no guarantee where those users are distributed, so all shards needs to be queried, and results needs to be merged

• example of global secondary index:

  • "table1" is sharded based on user_id
  • another duplicated table "table2" is sharded based on age
  • merge(all_nodes("table1")) = merge(all_nodes("table2"))
  • but on any specific node, table1 != table2 because they're indexed on diffrent columns
  • reading is fast, but writing requires distributed transaction, or 2 phase commit

What is 2 phase commit?

• We need atomicity
• Two phases
  • Growing Phase: the transaction acquires all the necessary locks on data items it needs to access
  • Shrinking Phase: the transaction holds all acquired locks and begins releasing htem
• distributed transactions
• It prevents data anomalies like dirty reads, lost updates, and phantom reads
• but it may lead to deadlocks

What is 2 phase locking?

• Shared Reader lock
• Writer lock, only obtained when all read locks are released
• Obtain read lock, when all other reads are done, obtain write lock
• Deadlocks!
  • database has some sort of mechanisms to handle it
  • applications needs to monitor it as well as to retry after terminated due to deadlocks

How to pick the appropriate database for different scenarios?