Database Scaling Guide Notes

Relational Database Management System (RDBMS)

• A relational database like SQL is a collection of data items organized in tables.
• Scaling techniques include: master-slave replication, master-master replication, federation, sharding, denormalization, and SQL tuning.

ACID Properties

• ACID is a set of properties of relational database transactions:
  • Atomicity: Each transaction is all or nothing.
  • Consistency: Any transaction will bring the database from one valid state to another.
  • Isolation: Executing transactions concurrently has the same results as if the transactions were executed serially.
  • Durability: Once a transaction has been committed, it will remain so.

Database Replication Strategies

Master-Slave Replication

• The master serves reads and writes, replicating writes to one or more slaves, which serve only reads.
• Slaves can also replicate to additional slaves in a tree-like fashion.
• If the master goes offline, the system can continue to operate in read-only mode until a slave is promoted to a master or a new master is provisioned.
• Disadvantages:
  • Additional logic is needed to promote a slave to a master

Master-Master Replication

• Both masters serve reads and writes and coordinate with each other on writes.
• If either master goes down, the system can continue to operate with both reads and writes.
• Disadvantages:
  • You'll need a load balancer or you'll need to make changes to your application logic to determine where to write
  • Most master-master systems are either loosely consistent (violating ACID) or have increased write latency due to synchronization
  • Conflict resolution comes more into play as more write nodes are added and as latency increases

General Replication Disadvantages

• There is a potential for loss of data if the master fails before any newly written data can be replicated to other nodes
• Writes are replayed to the read replicas. If there are a lot of writes, the read replicas can get bogged down with replaying writes and can't do as many reads
• The more read slaves, the more you have to replicate, which leads to greater replication lag
• On some systems, writing to the master can spawn multiple threads to write in parallel, whereas read replicas only support writing sequentially with a single thread
• Replication adds more hardware and additional complexity

Database Partitioning Strategies

Federation (Functional Partitioning)

• Federation splits up databases by function.
• For example, instead of a single, monolithic database, you could have three databases: forums, users, and products, resulting in less read and write traffic to each database and therefore less replication lag.
• Smaller databases result in more data that can fit in memory, which in turn results in more cache hits due to improved cache locality.
• With no single central master serializing writes you can write in parallel, increasing throughput.
• Disadvantages:
  • Federation is not effective if your schema requires huge functions or tables
  • You'll need to update your application logic to determine which database to read and write
  • Joining data from two databases is more complex with a server link
  • Federation adds more hardware and additional complexity

Sharding

• Sharding distributes data across different databases such that each database can only manage a subset of the data.
• Taking a users database as an example, as the number of users increases, more shards are added to the cluster.
• Similar to the advantages of federation, sharding results in less read and write traffic, less replication, and more cache hits.
• Index size is also reduced, which generally improves performance with faster queries.
• If one shard goes down, the other shards are still operational, although you'll want to add some form of replication to avoid data loss.
• Like federation, there is no single central master serializing writes, allowing you to write in parallel with increased throughput.
• Common sharding strategies: User's last name initial or geographic location.
• Disadvantages:
  • You'll need to update your application logic to work with shards, which could result in complex SQL queries
  • Data distribution can become lopsided in a shard. For example, a set of power users on a shard could result in increased load to that shard compared to others
  • Rebalancing adds additional complexity. A sharding function based on consistent hashing can reduce the amount of transferred data
  • Joining data from multiple shards is more complex
  • Sharding adds more hardware and additional complexity

Database Optimization Techniques

Denormalization

• Denormalization attempts to improve read performance at the expense of some write performance.
• Redundant copies of the data are written in multiple tables to avoid expensive joins.
• Some RDBMS such as PostgreSQL and Oracle support materialized views which handle the work of storing redundant information and keeping redundant copies consistent.
• Once data becomes distributed with techniques such as federation and sharding, managing joins across data centers further increases complexity.
• Denormalization might circumvent the need for such complex joins.
• In most systems, reads can heavily outnumber writes 100:1 or even 1000:1.
• A read resulting in a complex database join can be very expensive, spending a significant amount of time on disk operations.
• Disadvantages:
  • Data is duplicated
  • Constraints can help redundant copies of information stay in sync, which increases complexity of the database design
  • A denormalized database under heavy write load might perform worse than its normalized counterpart

SQL Tuning

• SQL tuning is a broad topic and many books have been written as reference.
• It's important to benchmark and profile to simulate and uncover bottlenecks.
  • Benchmark: Simulate high-load situations with tools such as ab
  • Profile: Enable tools such as the slow query log to help track performance issues

Schema Optimization

• MySQL dumps to disk in contiguous blocks for fast access
• Use CHAR instead of VARCHAR for fixed-length fields
  • CHAR effectively allows for fast, random access, whereas with VARCHAR, you must find the end of a string before moving onto the next one
• Use TEXT for large blocks of text such as blog posts. TEXT also allows for boolean searches
• Use INT for larger numbers up to $2^{32}$ or 4 billion
• Use DECIMAL for currency to avoid floating point representation errors
• Avoid storing large BLOBS, store the location of where to get the object instead
• VARCHAR(255) is the largest number of characters that can be counted in an 8 bit number
• Set the NOT NULL constraint where applicable to improve search performance

Index Optimization

• Columns that you are querying (SELECT, GROUP BY, ORDER BY, JOIN) could be faster with indices
• Indices are usually represented as self-balancing B-tree that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time
• Placing an index can keep the data in memory, requiring more space
• Writes could also be slower since the index also needs to be updated
• When loading large amounts of data, it might be faster to disable indices, load the data, then rebuild the indices

Query Optimization

• Avoid expensive joins - denormalize where performance demands it
• Partition tables - break up a table by putting hot spots in a separate table to help keep it in memory
• Tune the query cache - In some cases, the query cache could lead to performance issues

NoSQL Databases

• NoSQL: A collection of data items represented in a key-value store, document store, wide column store, or a graph database.
• Data is denormalized, and joins are generally done in the application code.
• Most NoSQL stores lack true ACID transactions and favor eventual consistency.

BASE Properties

• BASE is often used to describe the properties of NoSQL databases.
• In comparison with the CAP Theorem, BASE chooses availability over consistency:
  • Basically available: The system guarantees availability
  • Soft state: The state of the system may change over time, even without input
  • Eventual consistency: The system will become consistent over a period of time, given that the system doesn't receive input during that period

Types of NoSQL Databases

Key-Value Store

• Abstraction: Hash table
• A key-value store generally allows for O(1) reads and writes and is often backed by memory or SSD.
• Data stores can maintain keys in lexicographic order, allowing efficient retrieval of key ranges.
• Key-value stores can allow for storing of metadata with a value.
• Key-value stores provide high performance and are often used for simple data models or for rapidly-changing data, such as an in-memory cache layer.
• Since they offer only a limited set of operations, complexity is shifted to the application layer if additional operations are needed.

Document Store

• Abstraction: Key-value store with documents stored as values
• A document store is centered around documents (XML, JSON, binary, etc), where a document stores all information for a given object.
• Document stores provide APIs or a query language to query based on the internal structure of the document itself.
• Based on the underlying implementation, documents are organized by collections, tags, metadata, or directories.
• Although documents can be organized or grouped together, documents may have fields that are completely different from each other.
• Examples: MongoDB, CouchDB, DynamoDB, Elasticsearch

Wide Column Store

• Abstraction: Nested map ColumnFamily
• A wide column store's basic unit of data is a column (name/value pair).
• A column can be grouped in column families (analogous to a SQL table).
• Super column families further group column families.
• You can access each column independently with a row key, and columns with the same row key form a row.
• Each value contains a timestamp for versioning and for conflict resolution.
• Examples: Google Bigtable, HBase, Cassandra

Graph Database

• Abstraction: Graph
• In a graph database, each node is a record and each arc is a relationship between two nodes.
• Graph databases are optimized to represent complex relationships with many foreign keys or many-to-many relationships.
• Graphs databases offer high performance for data models with complex relationships, such as a social network.
• They are relatively new and are not yet widely-used; it might be more difficult to find development tools and resources.
• Examples: Neo4j, FlockDB

SQL vs NoSQL Decision Matrix

• Sample Data Well-Suited for NoSQL
  • Rapid ingest of clickstream and log data
  • Leaderboard or scoring data
  • Temporary data, such as a shopping cart
  • Frequently accessed ('hot') tables
  • Metadata/lookup tables

Caching Strategies

def get_user(self, user_id):
 user = cache.get("user.{0}", user_id)
 if user is None:
 user = db.query("SELECT * FROM users WHERE user_id = {0}", user_id)
 if user is not None:
 key = "user.{0}".format(user_id)
 cache.set(key, json.dumps(user))
 return user

• Caching improves page load times and can reduce the load on your servers and databases.
• In this model, the dispatcher will first lookup if the request has been made before and try to find the previous result to return, in order to save the actual execution.
• Types of Caching
  • Client caching: OS or browser level
  • CDN caching: Content Delivery Networks
  • Web server caching: Reverse proxies like Varnish
  • Database caching: Built-in database optimization
  • Application caching: In-memory stores like Memcached and Redis
• Cache Levels
  • Row level
  • Query-level
  • Fully-formed serializable objects
  • Fully-rendered HTML

Cache Update Strategies

Cache-Aside

• The application is responsible for reading and writing from storage. The cache does not interact with storage directly.
• Advantages:
  • Only requested data is cached, avoiding unnecessary cache filling.
• Disadvantages:
  • Each cache miss results in three trips, which can cause noticeable delay
  • Data can become stale if updated in the database
  • When a node fails, it is replaced by a new, empty node, increasing latency

Write-Through

• The application uses the cache as the main data store, reading and writing data to it, while the cache is responsible for reading and writing to the database.
• Advantages:
  • Data in cache is never stale, subsequent reads are fast.
• Disadvantages:
  • Write operations are slow due to synchronous database writes
  • New nodes don't cache entries until database updates occur
  • Most written data might never be read

Write-Behind (Write-Back)

• The application adds/updates entries in cache and asynchronously writes to the data store, improving write performance.
• Advantages:
  • Improved write performance through asynchronous operations.
• Disadvantages:
  • Potential data loss if cache goes down before hitting data store
  • More complex to implement than other strategies

Refresh-Ahead

• Configure the cache to automatically refresh any recently accessed cache entry prior to its expiration.
• Advantages:
  • Can reduce latency if cache accurately predicts needed items.
• Disadvantages:
  • Inaccurate predictions can result in reduced performance

Asynchronous Processing

• Asynchronous workflows help reduce request times for expensive operations that would otherwise be performed in-line.
• They can also help by doing time-consuming work in advance, such as periodic aggregation of data.

Message Queues

• Message queues receive, hold, and deliver messages.
• If an operation is too slow to perform inline, you can use a message queue with the following workflow:
  • An application publishes a job to the queue, then notifies the user of job status
  • A worker picks up the job from the queue, processes it, then signals the job is complete
  • The user is not blocked and the job is processed in the background
• Popular Message Queue Solutions
  • Redis: Simple message broker but messages can be lost
  • RabbitMQ: Popular but requires AMQP protocol adaptation
  • Amazon SQS: Hosted solution but can have high latency and duplicate message delivery

Task Queues

• Task queues receive tasks and their related data, run them, then deliver their results.
• They can support scheduling and can be used to run computationally-intensive jobs in the background.
• Example: Celery has support for scheduling and primarily has Python support.

Back Pressure

• If queues start to grow significantly, the queue size can become larger than memory, resulting in cache misses, disk reads, and even slower performance.
• Back pressure can help by limiting the queue size, thereby maintaining a high throughput rate and good response times for jobs already in the queue.
• Disadvantages: Asynchronism
  • Use cases such as inexpensive calculations and realtime workflows might be better suited for synchronous operations, as introducing queues can add delays and complexity