Architecture of a Database System

http://blog.acolyer.org/2015/01/20/architecture-of-a-database-system/

by adamnemecek • 12 years ago

88 17 12 years ago

blog.acolyer.org

Due to the number of years required to design and implement a solid database architecture, database design principles in current systems always tend to be a bit different than what you would build if you were starting today (whenever "today" actually is). Database designs are always fighting the last war, based on assumptions about resource balance, hardware behaviors, and system architectures that may not be strictly true anymore.

Some related comments, with respect to the article:

- Modern database models are one process per physical core regardless of how many sessions, queries, connections, etc that there are. These cores own the part of the data they work with. This has several advantages on modern computing architectures. It also makes for a pretty elegant implementation.

- Related to the first point, new database kernels are increasingly "shared nothing" even within a single server. As in, physical resources will be cut up between cores / processes and rarely shared. It is like running a cluster within a machine. Again, this has some significant performance advantages on modern machines.

- The key advantage of SSDs, which was not true for spinning disk, is that you can usually guarantee effective disk I/O bandwidth is always significantly greater than the full-duplex network bandwidth to the server no matter what the workload. This has an interesting technical implication: if the I/O scheduler is correctly designed and implemented, an in-memory database engine should never be faster than a disk-backed database. In-memory was only an optimization that made sense for spinning disk; with SSD, if you aren't compute-bound, you can always saturate the network (and if you are compute-bound, in-memory does not help).

falcolas2• 12 years ago

if the I/O scheduler is correctly designed and implemented, an in-memory database engine should never be faster than a disk-backed database.

If, and only if, you are returning all/most of the data fetched from disk, and not just a fractional portion of the data (which is the most common use case for DBs, especially when you use stored procedures).

In the worst case, you have to scan the entire contents of a several terabyte table from disk just to get metadata about that table. The worst case is usually refactored away, but there are always cases where it is simply not possible.

I've seen some pretty silly speedups with flash (such as attaching the flash memory to DIMM slots with custom kernel drivers), but data served out of memory was still faster (if only because it doesn't require a context switch to read).

jandrewrogers2• 12 years ago

To be clear, I am assuming the same hardware budget for both the on-disk and in-memory case. Ceteris paribus and all that. An in-memory model has no inherent advantages in that case because the same memory is potentially available to both for a given workload. Another way of stating it is that SSD won't slow you down.

Ironically, in practice relative performance between these two models is all over the map. Quality of implementation has much bigger impact than the abstract model. I've seen high-quality disk-backed database engines wipe the floor with in-memory implementations on the same hardware and vice versa.

jamii4• 12 years ago

Some of the more exciting ideas I've seen recently:

http://arxiv.org/abs/1310.3314 - Understanding the core difficulty in answering relational queries and examples of problems for which current query optimisers always produce plans which are asymptotically suboptimal

http://arxiv.org/abs/1404.0703 - The first theoretical analysis which can relate the choice of indexes to worst-case bounds. Presents a single join algorithm which is asymptotically optimal on every problem without even using cardinality estimates.

http://arxiv.org/abs/1210.0481 - A join algorithm that meets some of the bounds of the above paper and is also fast in practice and can be incrementally maintained.

https://infosys.uni-saarland.de/projects/octopusdb.php - Treating index creation, query optimising, view materialisation, incremental maintenance etc as one large optimisation problem.

http://www.vldb.org/pvldb/vol4/p539-neumann.pdf - Compiling query plans to LLVM because the query plans / indexes are good enough to make the plan cpu-bound instead of memory-bound

http://hyper-db.de/HyperTechReport.pdf - Running OLAP and OLTP workloads on the same database without interference

It seems possible that in the future, far from having a Cambrian explosion of specialised databases, we will be able to store everything in a single db and treat questions of data layout, partitioning, indexing etc as a direct optimisation problem.

fspeech• 12 years ago

Do you know if HyPer is open source? The name makes searching a bit of a challenge.

acolyer• 12 years ago

@jamil, thanks for the pointers! I will store some of these away for future editions of The Morning Paper :)

adamnemecek• 12 years ago

Those look awesome, thanks for posting them. Quick question, how do you learn about all these papers? They all seem very recent.

pmalynin• 12 years ago

Saturating an Infiniband (40 Gbps) link with disk I/O might be somewhat complicated.

justincormack2• 12 years ago

A few PCIe SSDs should get you there (again if not CPU bound). You can put quite a lot in a single machine, they come in normal SSD form factor with backplanes. It would still be a bit higher latency than RAM, but much more capacity.

sacheendra• 12 years ago

I think, he was assuming commodity 1Gbit/10Gbit on which most databases are run. Does anybody use Infiband to interact with their database? It would be interesting to hear from them.

PublicEnemy111• 12 years ago

Database designs are always fighting the last war, based on assumptions about resource balance, hardware behaviors, and system architectures that may not be strictly true anymore.

I've been studying cache-oblivious data structures recently and have been wondering why they don't seem to be taken seriously in modern database design. COLAs and shuttle trees both seem to considerably outperform traditional B-Trees in terms of random inserts while suffering only a slight slowdown for searches and sorted inserts[1]

[1]http://supertech.csail.mit.edu/papers/sbtree.pdf

dman• 11 years ago

Great post.

Architecture of a Database System

Related Stories