↓Skip to main content
  1. posts/

OLTP through the looking glass

·8 mins
Databases Papers
Table of Contents

Paper: OLTP Through the Looking Glass, and What We Found There by Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker (SIGMOD 2008).

OLTP features #

  • On-disk data structures for table storage
  • Heap files and B-tree support
  • Multiple concurrent queries via locking-based concurrency control
  • Log-based recovery
  • Efficient buffer management

This was in the 70s where the main memory was little compared to the DB and it was so expensive to run, costing hundreds of thousands or millions.

In today’s situation, it is trivial to get a good system for cheap and mostly the full OLTP DB can be in the memory. Institutions have their own network-clustered machines operating with hundreds of gigabytes of memory.

OS and network conferences: with the rise of the internet, there are more database-like system proposals than the full suite.

alternative DBMS architectures #

Optimizing OLTP for main memory is a good idea when it fits in the RAM.

  • Log-less DB: recovery is not needed or it recovers from other sites in a cluster (Harp, Harbor and C-Store)
  • Single-threaded databases
  • Transaction-less databases: transactions are not needed in many systems. Most distributed systems prefer eventual consistency than actual. Or lightweight forms of transaction like all reads are done before writing

How well will all of this perform if built?

measuring the overheads of OLTP #

Shore (DB). Benchmarked with a subset of TPC-C benchmark. In their environment, the initial transactions per second (TPS) is 640.

They try to remove features to check the increase in performance. At the end, they had a tiny kernel with query processing code that could process around 12.7K TPS. The kernel is single-threaded, lock-free, main memory DB without recovery.

What did they remove to get this jump:

  • Logging: helps in recovery and slows things down but if there are other means of recovery then we can remove it
  • Locking: traditional two-phase locking poses a sizeable overhead since all accesses to DB are governed by lock manager
  • Latching: in a multi-threaded DB, many data structures have to be latched before access. Removing this feature and going to a single-threaded approach has a noticeable performance impact
  • Buffer management: main memory DB does not need to access pages through a buffer pool

Cluster computing: RDBMS were originally written for shared memory multi-process systems. And added support for shared disk architecture. Gamma-style shared-nothing DBs.

Memory-resident databases: because of increase in RAM capacity in these systems, we have more room to play with and most of the OLTP systems fit within a clustered system’s RAM. Optimized indices, eschewing disk-optimized tuple formats and page layouts.

Single threading in OLTP systems: dig on transactions and it is fast now compared to earlier and latching commands slowing down the performance. Making it single-threaded will help with latching reduction to zero and it will affect transactions, but they argue if there are no disk writes because of memory-resident systems, it will be fast as there will just be index lookups and etc. The other idea was to consider each DB in each thread with other threads in the same systems as clusters to stand for throughput concerns for transaction systems.

HA vs logging

Transaction variants: this is about eventual consistency and that is preferred in most systems for performance to trade off availability. Less strict forms are available and if the two-phase requirement is stripped down to their exact needs it would be like perform all of their reads before any of their writes.

MIT H-Store: remove these features and there was two order of magnitude speedup in transaction throughput.

Shore #

Scalable Heterogeneous Object Repository. To be typed, persistent object system borrowing from both file system and object-oriented DB.

Layers: type system, Unix compatibility, language heterogeneity.

The storage manager SSM had all the features of a DBMS like concurrency control and recovery with two-phase locking and WAL and B-trees. The project ended in the 1990s but the SSM was developed more and updated.

Shore architecture #

It has managers for everything: lock manager, log manager, buffer manager.

All invocations happen through a concurrency layer. Shared objects are accessed through latching. Latch is similar to locks and lightweight and comes with no deadlock detection mechanism.

Thread support: Shore used its own user-level, non-preemptive thread package derived from NewThreads, providing a portable OS interface API. Since it is user-level it is single process and multiplexes the threads. For this performance experiment, we are using single-threaded process and removing the multi-threads feature.

Locking and logging: two-phase locking, transactions with ACID. Supports hierarchical locking. WAL. LSN (Log Sequence Number).

Buffer manager: other modules read and write pages through this. A page read is issued by the fix method call to buffer manager.

Recording a record involves:

  • Locking the record (and page, per hierarchical locking)
  • Fixing the page in the buffer pool
  • Computing the offset within the page of the record’s tag

Reading a record is performed by issuing a pin/unpin method call.

removing Shore components #

Modifications:

  • Remove logging: log-less architecture
  • Remove locking (when applicable): partitioning, commutativity
  • Single thread, remove locking and latching: one transaction at a time
  • Remove buffer manager, directory: main memory resident
  • Avoid transaction bookkeeping: transaction-less databases

Steps taken:

  1. Removing logging
  2. Removing locking or latching
  3. Removing latching or locking
  4. Removing core related to buffer manager
  5. Optimizations: B-tree key evaluation, accelerate directory lookups, increase page size to avoid frequent allocation, remove transactional sessions

Removals are done through code block removal or with if-else statements. If it adds too much overhead, then they rewrite the methods.

performance study #

OLTP workload #

Benchmark is derived from TPC-C: models the wholesale parts supplier operating out of a number of warehouses and their associated sales districts. Each database for each warehouse is 100 MB. Involves mix of 5 concurrent transactions of different types and complexity (NewOrder, Payments, Delivering Orders, Checking Status of Orders, Monitoring Stock). This paper experimented with the first 2 transactions.

New Order: places an order for 5-15 items, the ask was changed a little bit than the mandate of 90% local warehouse + 10% remote. Eased to 100% local warehouses. We don’t abort any transaction and if we find an invalid one, we abort without redoing changes in DB.

Payment: lightweight transaction that updates balances and creates a history record.

setup and measurement methodology #

Single-core Pentium 4, 3.2 GHz with 1 MB L2 cache, hyperthreading disabled, 1 GB RAM running Linux 2.6. Use iostat to monitor disk activity and verify main memory residency of the DB.

For detailed instruction and cycle count, they instrument the benchmark application code with calls to PAPI library which gives access to performance counters.

Micro-architectural behavior:

  • Instruction count: deterministic
  • Cycle count: susceptible to various parameters

experimental results #

Shore platform: single-threaded executing one transaction at a time, memory-resident, never flushed to disk.

11 different switches to remove functionality from Shore.

Effect on throughput:

  • No I/O: avg of 80 microseconds per transaction or 12,700 TPS
  • The useful work in this is about 22 microseconds per transaction or 46,500 TPS. This difference is because of the complexity in code removal and some parts of the transaction code is left within the call stack.
  • Out of the box Shore: with logging, 620 TPS. Without logging, 1,700 TPS.
  • Modifications yield a significant improvement by a factor of 20.

Payment transaction #

Reduction in instructions as we optimized:

  • B-tree key eval: standard practice in high-performance DBMS
  • Removed logging: affects mainly commits and updates. These two removed 18% of the instruction count
  • Locking: removed 25% instruction count, for pin and unpin
  • Latching: 13% instructions, create record and B-tree lookups
  • Buffer management: 30% total instruction count, now directly uses malloc

Operations:

  • 3 B-tree lookups
  • 3 pin/unpin ops
  • 3 updates (through B-tree)
  • 1 record creation
  • Commit call

After the optimizations, the remaining kernel requires about 5% of the total initial instruction count, which is about 6 times the total instructions of the optimal system.

  1. All 6 components are significant
  2. Until all optimizations are applied, the reduction in instruction count is not dramatic

New Order transaction #

Operations:

  • 13 B-tree inserts
  • 12 record creations
  • 11 updates
  • 23 pin/unpin ops
  • 23 B-tree lookups

Optimizations:

  • B-tree key eval: 16% of the total instructions
  • Logging and locking: 12% and 16% of the instructions
  • Buffer management: 14% reduction in total instructions. Biggest win. Tuning the page size so that frequency of page allocation decreases and B-tree depth is reduced.

implications for future OLTP #

Concurrency control: 19% of cycles of the overhead from this, and we need to find the best way to do this as the simulated methods in the past had disk-based loads with disk stalls in mind. Redoing the simulation for newer systems and hardware might help the case.

Multi-core support: many-core machines are prevalent, to handle the transactions with concurrent cores with a single site. For this, latching is required. The overhead for latching is 10%. You can make it better with new implementations. Or virtualize each core as its own machine at DBMS or OS layer, or exploit intra-query parallelism.

Replication management: active-active approach, nearly instantaneous failovers. Two-phase commits and transaction consistency causes a lot of latency and leads to more failover time because of active-passive.

Weak consistency: eventual consistency and paying for consistency errors in a non-technical way.

Cache-conscious B-trees: they did not use this and this would yield a modest performance boost.

conclusion #

Performance impact of Shore components under the TPC-C benchmark while being stripped of instructions and functionalities yielded serious performance gains up to a factor of 20. Major contributors are buffer management, logging and latching optimization.

  1. The performance of a memory database without transactions or logging is better than a conventional database that could fit in RAM.
  2. When you provide a stripped-down system (single-threaded, fits in memory, reduced functionality), the performance is orders of magnitude better than an unmodified system.