Database Architecture

Created
TypeDatabase
LanguageNoSQLSQL
Last Edit

Introduction

Indexing

If you can’t keep your indexes in memory, you can’t keep your database fast.

In MySQL

Given the need for globally unique ids the obvious question is, why not use GUIDs? Mostly because GUIDs are big, and they index badly in MySQL. One of the ways we keep MySQL fast is we index everything we want to query on, and we only query on indexes. So index size is a key consideration.

Coalescing

Coalescing refers to the process of merging or combining adjacent free space fragments into a larger contiguous block. This is typically done to optimize storage utilization and reduce fragmentation, which can improve database performance.

Scaling Databases

Vertical Scaling

Horizontal Scaling

Load balancers can also help with horizontal scaling, improving performance and availability. Scaling out using commodity machines is more cost efficient and results in higher availability

Scaling Patterns:

Sharding

Aka Data Partioning

Instead of storing all our data on one really big database, we have lots of databases, each with some of the data, and spread the load between them.

Federated Queries

Ability to join tables which are in different datasets and which might not even have the same owner.

Queries that join tables from different datasets are called federated queries. Their syntax is very similar to that of other join queries with additional location information specified.

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.

SQL Tuning

Benchmarking and profiling might point you to the following optimizations.

Ticket Servers

Ticket Servers: Distributed Unique Primary Keys on the Cheap
https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

Ticket servers give us globally unique integers to serve as primary keys in our distributed setup.

Ticket servers give us sequentiality which has some really nice properties including making reporting and debugging more straightforward, and enabling some caching hacks.

Implemenation

A ticket server is a dedicated database server, with a single database on it, and in that database there are tables like Tickets32 for 32-bit IDs, and Tickets64 for 64-bit IDs.

The Tickets64 schema looks like:

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB

SELECT * from Tickets64 returns a single row that looks something like:

+-------------------+------+
| id                | stub |
+-------------------+------+
| 72157623227190423 |    a |
+-------------------+------+

When I need a new globally unique 64-bit ID I issue the following SQL:

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

A little over a decade ago MySQL shipped with a non-standard extension to the ANSI SQL spec, “REPLACE INTO”. Later “INSERT ON DUPLICATE KEY UPDATE” came along and solved the original problem much better. However REPLACE INTO is still supported.

REPLACE works exactly like INSERT, except that if an old row in the table has the same value as a new row for a PRIMARY KEY or a UNIQUE index, the old row is deleted before the new row is inserted.

Hash-Based Routing

Consistent hash-based routing to data services to enable more effective coalescing.

For each request to our data service, we provide a routing key. For messages, this is a channel ID, so all requests for the same channel go to the same instance of the service. This routing further helps reduce the load on our database.

Design

Assumptions

Calculations

  • 1 TB of new content per month
    • 1 KB per write * 1 billion writes per month
    • 12 TB of new content in 1 years
    • Assume most writes are from new content instead of updates to existing ones
  • 400 writes per second on average
  • 40,000 reads per second on average

Handy conversion guide:

  • 2.5 million seconds per month
  • 1 request per second = 2.5 million requests per month
  • 40 requests per second = 100 million requests per month
  • 400 requests per second = 1 billion requests per month

Databases

Cassandra

ScyllaDB

Elimination SPF

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.

Testing Tools

High Level Trade-offs