We implemented seven concurrency control algorithms on a main-memory DBMS and using computer simulations scaled our system to 1024 cores. Our analysis shows that all algorithms fail to scale to this magnitude but for different reasons. In each case, we identify fundamental bottlenecks that are independent of the particular database implementation and argue that even state-of-the-art DBMSs suffer from these limitations.
Our evaluation shows that all seven concurrency control schemes fail to scale to a large number of cores, but for different reasons and conditions. Table 2 summarizes the findings for each of the schemes. In particular, we identified several bottlenecks to scalability: (1) lock thrashing, (2) preemptive aborts, (3) deadlocks, (4) timestamp allocation, and (5) memory-to-memory copying.
Our results show that none of the algorithms are able to get good performance at such a high core count in all situations. For lower core configurations, we found that 2PL-based schemes are good at handling short transactions with low contention that are common in key-value workloads. Whereas T/O-based algorithms are good at handling higher contention with longer transactions that are more common in complex OLTP workloads
Software-hardware co-design is the only solution to address these issues. For certain functionalities, specialized hardware can significantly improve performance while reducing power consumption
We conclude that rather than pursuing incremental solutions, many-core chips may require a completely redesigned DBMS architecture that is built from ground up and is tightly coupled with the hardware.
Ask For Forgiveness Programming - Or How We'll Program 1000 Cores
Parallel Programming: When Amdahl’s law is inapplicable?
HAT, not CAP: Introducing Highly Available Transactions
Distributed systems designers face hard trade-offs between factors like latency, availability, and consistency. Perhaps most famously, the CAP Theorem dictates that it is impossible to achieve “consistency” while remaining available in the presence of network and system partitions.1 Further, even without partitions, there is a trade-off between response time and consistency. These fundamental limitations mean distributed databases can’t have it all, and the limitations aren’t simply theoretical: across datacenters, the penalties for strong consistency are on the order of hundreds of milliseconds(compared to single-digit latencies for weak consistency) and, in general, unavailability takes the form of a404 or Fail Whale on a website. Over twelve years after Eric Brewer first stated the CAP Theorem(and after decades of building distributed database systems), data store designers have taken CAP to heart, some choosing consistency and others choosing availability and low latency.
While the CAP Theorem is fairly well understood, the relationship between CAP and ACID transactionsis not. If we consider the current lack of highly available systems providing arbitrary multi-object operations with ACID-like semantics, it appears that CAP and transactions are incompatible. This is partly due to the historical design of distributed database systems, which typically chose consistency over high availability. Standard database techniques like two-phase locking andmulti-version concurrency controldo not typically perform well in the event of partial failure, and the master-based (i.e., master-per-shard) and overlapping quorum-based techniques often adopted by many distributed database designsare similarly unavailable if users are partitioned from the anointed primary copies.
No comments:
Post a Comment