Databases

Durable storage for application state. Data is usually stored in hard disk for persistence.

Types

SQL

• ACID Compliant
  • Atomic
  • Consistency
  • Isolation
  • Durable
• Relational
• Real-life data tends to follow a relational pattern (i.e. Feeds consists of Posts and both Feed and Post is owned by some User)
  

NoSQL

• Relax SQL’s strict consistency rules in exchange for scalability and schema flexibility. Inplace of ACID Compliance, NoSQL follows BASE:
  • Basically Available
  • Soft State
  • Eventually Consistent
    An easy way to understand this compliance is that there is an “eventual consistency in return for ease of scaling”. It trades perfect, instant correctness for speed and availability by allowing for some temporary disagreement between copies of data to happen.
• There are 3 major types of stores in NoSQL
  • Document Store
  • Key-value Store
  • Graph store

Scaling

Replication

Databases can/will eventually fail. Using only one single database also limits read & write throughput to that one single node. To fix this, Replication is used. Replication is simply the act of having copies of data, allowing

• Some resistance to hardware failures
• Improve database performance

Replicas will send data to one another via a replication log (similar data structure to write ahead log). There are 2 types of replications

• Asynchronous Replication
  Deals with “eventual consistency” concept. On a write, only a subset of the replicas must process the data/change before the write is considered to be commited. Other replicas will be back-filled with the change in the background
  • Writes can tolerate some node failures and will be faster
  • Reading from certain nodes will return nothing/stale data
• Synchronous Replication
  On a write, all replicas must process the data/change before the transaction/write is considered to be commited
  • All reads to the replica will return the most updated data
  • If a single replica is down, it will not commit any writes

Sharding

A table with too much load or simply storing too much data must be split across multiple different nodes. A huge consideration in keying shards is to ensure that majority of queries go to a single node for a single query. Shards should also have a relatively balanced/equal count of operations, and prevent hotspots.

• Range of Key
  Undoubtedly, hotspots will occur.
• Range of Key Hash
  Similar to Hash Indexes, it will only perform well with a well designed hashing function, and it will perform poorly for range queries.
  Note that to equally distribute among nodes, usually the easiest approach is to get the modulo with the number of partitions

Indexes

A feature used/supported by many databases to allow for more efficient read queries, albeit often, sacrificing the speed of write queries.

Hash Indexes

Keep keys in buckets in hash map. Buckets correspond to the hashed value of keys.

• $O(1)$ for reads & writes
• but key set needs to fit in memory and poor support for range queries, since hashing the keys does not necessarily put relevant keys adjacently.
• collision may occur
• better for single key read/writes if designed with good hashing function

B+ Trees

Tree of keys on disk, traversing through the tree to get to your key and its corresponding data on hard disk

• $O(log(n))$ for read & writes,
• slower single item reads than hash index (need to traverse tree)
• but since adjacent keys are stored next to each other on disk, faster range queries
• B+ Trees are self-balancing, and all leaf nodes are always strictly in the same depth
• Leaf nodes are connected via a linked list to enable efficient range queries.