Modern applications are often built on top of many-core OLTP databases. In such systems, concurrency control is an essential component in achieving high performance. Graph-based concurrency control was historically deemed nonviable due to concerns over the computational costs of maintaining an acyclic conflict graph. This conventional wisdom has been refuted by recent research. The work conducted in this PhD has sought to further investigate the usefulness of graph-based concurrency control. Specifically, we propose mixed serialization graph testing (MSGT), a concurrency control protocol that allows transactions to concurrently execute at diferent isolation levels whilst minimizing unnecessary aborts. MSGT combines a recently proposed concurrent graph data structure with Adya's mixing-correct theorem. The practical utility of MSGT is illustrated by a survey of isolation levels supported by 24 ACID databases. MSGT has been implemented in a prototype many-core database and a preliminary evaluation using an augmented YCSB workload performed. Initial results indicate the eficacy of MSGT at leveraging transactions specified with weaker isolation requirements. In such workloads, MSGT is able to outperform serializable graph-based concurrency control by up to 23%. We cast further doubt on the notion that graph-based concurrency control in many-core OLTP databases is impractical.
1. Introduction ing the efects of concurrently executing transactions are isolated from each other. This is captured by the correctness criteria serializability [1]. Implementing serializable transaction processing eficiently is a challenging task cently, graph-based concurrency control was discounted as a viable strategy, despite possessing the theoretically optimal property of accepting all conflict serializable schedules [1]. Graph-based concurrency control directly uses the conflict graph theorem by maintaining an acyclic conflict graph. The computational costs of this were perceived to be intolerable. However, this was refuted in [3] who, using a concurrent data structure to represent the conflict graph, demonstrated graph-based concurrency control can achieve comparable, and often higher, performance in a many-core database when compared to alternative strategies.
ing performance, it often remains unsuitable for application demands. Another tool at databases’ disposal to achieve improved performance is to execute transactions at weaker isolation levels [4, 5]. Central to this PhD Proceedings of the VLDB 2022 PhD Workshop, September 5, 2022. 0000-0002-6649-2744 (J. Waudby) 2.
mixed graph-based concurrency control we surveyed the isolation levels ofered by 24 ACID databases. Classiifcation was performed based on each database’s public documentation. We found 7 isolation levels represented: and Serializable. Note, the exact behavior of each isolation level is highly system-dependent. Interestingly, we found 18 databases supported multiple isolation levels. . wr 2 wr ww 3 1 wr 2 ww
3 Serializable
Read Uncommitted (b) Direct serialization graph, () . (c) Mixed serialization graph, () .
was the most common; these were typically NewSQL [7] systems, e.g., CockroachDB [8]. This may suggest a trend away from mixed databases, however, TiDB [9] recently added support for Consistent Read isolation indicating the utility of weaker isolation remains.
Graph-based concurrency control, also known as serialization graph testing (SGT), directly utilizes the conflict graph theorem [1] by maintaining an acyclic conflict graph. An execution of transactions can be represented by a schedule. Consider transactions 1, 2, and 3 shown in schedule below; a write on item by transaction is denoted by [] , a read by [] , and a commit operation by .
= 1[] 2[] 2[ ] 1[ ] 2[] 3[] 3[] 1 3 2 This schedule can be represented by a conflict graph () , shown in Figure 1a. Nodes represent transactions and conflicting operations of and of such that [] < [] , where ≠ , are represented by an edge → ; possible conflict pairs are (, ) ∈ [( , ), ( , ), ( , )] . For example, in , 2 reads after 1 writes to , thus there exists an edge from 1 to 2 in Figure 1a. Changing the order of conflicting operations could alter the behavior of at least one transaction. Therefore, an execution of transactions is conflict serializable if a serial ordering of transactions that satisfies all conflict edges can be found. Such a serial ordering exists if the conflict graph is acyclic. This is known as the conflict graph theorem [ 1]. Note, is not conflict serializable because () in Figure 1a contains a cycle. Theorem 1 (Conflict Graph Theorem). A schedule is conflict serializable if its corresponding conflict graph () is acyclic.
Our survey’s findings are corroborated by a 2017 sur- lficts are determined and edges inserted into the graph. vey of database administrators on how applications use After edge insertion, a cycle check is performed before databases [4], the survey found the majority of transac- executing the operation; in [3] a reduced depth-first search tions execute at Read Committed. In short, this evidence (DFS) is used for cycle checking, which starts from the illustrates the ubiquity of mixed databases and motivates validating node, searching only the necessary portion of the work to be conducted in this PhD. the graph. If executing the operation would introduce a cycle the ofending transaction is aborted and its edges re3. Background moved. At commit time, a transaction delays until it has no incoming edges, at which point it cannot be involved This section describes serializable graph-based concur- in a cycle. When the transaction terminates it removes rency control, the many-core optimizations made in [3], its outgoing edges. In short, SGT provides serializability and introduces a correctness criteria for mixed databases. by ensuring the acyclic invariant and thus accepting all valid conflict serializable schedules.
In a many-core database, common sources of performance degradation are, (i) reliance on a global timestamp allocator for transaction ids [2], (ii) use of a singlethread validation phase [10], and (iii) when conflicts are common, optimistic protocols exhibit a high number of aborts [11]. In the SGT implementation in [3], a concurrent graph data structure is developed which uses a node-level locking protocol to avoid using a global lock for graph operations. To avoid a global counter bottleneck, graph nodes double up as transaction ids. Lastly, owing to SGT’s acceptance of all valid conflict serializable schedules, aborts are naturally minimized.
serialization graph, , which annotates a conflict graph with the ways transactions have directly conflicted: write- Theorem 2 (Mixing-Correct Theorem). A schedule depends (ww), read-depends (wr), and anti-depends (rw). is mixing-correct if () is acyclic and phenomena G1a The corresponding of is given in Figure 1b. Non- and G1b do not occur for Read Committed and Serializable serializable behaviour (anomalies) are defined by stating transactions. properties about the , and isolation levels by which anomalies they prevent. For brevity, in this paper we consider 3 isolation levels, for a full enumeration see [6].
1. Write-depends edges (ww) are relevant to all transactions regardless of isolation level thus always included.
incoming to Read Committed and Serializable transactions.
transaction is provided the isolation guarantees that pertain to its level, leading to the mixing-correct theorem [6, p.54–56]. Figure 1c illustrates the diferences between and representations of a schedule with the non-relevant and non-obligatory edges removed.
Then to define a correctness criteria for a mixed database, Adya uses a variant referred to as a mixed serialization graph, . A includes a transaction’s declared isolation level and only includes relevant and obligatory conflicts. A relevant conflict is a conflict that is pertinent to a given isolation level, e.g., read-depends (wr) edges are relevant to Read Committed transactions but not Read Uncommitted transactions. An obligatory conflict is a conflict that is relevant to one transaction but not the other, e.g., an anti-depends (rw) edge between a Read Committed transaction and a Serializable transaction is relevant to the Serializable transaction and not the Read Committed transaction but still must be included in the . Adya defines the edge inclusion rules for an as follows: • Read Uncommitted: proscribes anomaly Dirty
Write (G0), the cannot contain cycles con- In this section, we describe mixed serialization graph sisting entirely of ww edges. testing, focusing on the adjustments to the SGT algorithm • Read Committed: proscribes G0 and anomalies, (sketched in 3.1) and the concurrent graph data structure; (i) Aborted Read (G1a), transactions cannot read we direct the reader to [3] for their original in-depth data item versions created by aborted transac- description. tions, (ii) Intermediate Reads (G1b), transactions For MSGT we use the graph data structure in [3] to cannot read intermediate data item versions, and represent an , which requires one alteration: nodes (iii) Circular Information Flow (G1c), the can- include transactions’ required isolation levels. MSGT not contain cycles consisting of ww and wr edges. proceeds in the same manner as SGT, with one key exception: for each operation, edge insertion of a detected • Serializable: proscribes anomalies G0, G1, and conflict is subject to MSG’s edge inclusion rules enumerG2, the cannot contain any cycles. ated in Section 3.2. MSGT’s edge insertion algorithm is given in Algorithm 1. First, if an edge already exists for this conflict type no further action is needed, else a cascading abort check if performed. If the parent node has aborted and the inserting node is Serializable or Read Committed it must also abort to avoid G1a anomalies.
Then, the edge is inserted if it satisfies MSG’s inclusion rules, before a cycle check is executed. If a cycle is found the transaction must abort. At commit time the transaction delays until it has no incoming edges.
1.7 ) s /n1.6 o iill m t(1.5 p h t 1.4 (b) Abort rate . . (c) Average latency . .
Cloud Serving Benchmark (YCSB) [12]. YCSB has 1 table with a primary key and 10 additional columns each with 100B of random characters; we use a table with 100K rows. There are 2 transaction types: read or update, each contains 10 independent operations accessing 10 distinct items. Update transactions consist of 5 reads and 5 writes that occur in random order. Read transactions consists of solely read operations. The proportion of update transactions is controlled by the parameter, . Data access follows a Zipfian distribution, where the frequency of access to hot records is tuned using a skew parameter, . When = 0 , data is accessed with uniform frequency, and when = 0.9 it is extremely skewed; increasing the probability of conflicts between transactions. To measure the impact of transactions running at weaker isolation we introduce an additional parameter, , which controls the proportion of transactions running at Serializable isolation. The remainder are split between Read Committed (90%) and Read Uncommitted (10%).
Due to space constraints we report only the results of the experiment which measures the impact of increasing the proportion of transactions executing at Serializable isolation from 0% to 100%. This aims to test MSGT’s ability to leverage its theoretical properties to ofer increased performance when transactions are run at weaker isolation levels. For this experiment, is fixed to 50%, medium contention is used ( = 0.8 ) and the framework is conifgured to use 40 cores. Prior to experiments, tables are loaded, followed by a warm-up period, before a measurement period; both are configurable, we use 60 seconds and 5 minutes respectively. We measure the following metrics: (i) throughput: committed transactions per second, (ii) abort rate: proportion of transactions aborted, and (iii) average latency: latency time of committed transactions (in ) averaged across the measurement period.
In Figure 2a, SGT’s throughput is invariant to , as it is unable to take advantage of transactions’ declared isolation levels, in efect, executing all transactions at Serializable. Meanwhile, the throughput of MSGT decreases as is increased, converging towards SGT’s throughput. When there are no Serializable transactions ( = 0.0 ) MSGT achieves a 23% increases in throughput. At = 0.4 , this drops to a 10% increase and at = 0.8 a 2.5% gain. When = 1.0 , all transactions are executed at Serializable which allows us to ascertain the overheads of MSGT compared to SGT. SGT outperforms MSGT however the diference in throughput is less than 1%.
In this paper, we presented MSGT, a graph-based scheduler that leverages Adya’s mixing-correct theorem to permit transactions to execute at diferent isolation levels. When workloads contain transactions running at weaker isolation levels, MSGT is able to outperform SGT by up to 23%. Like SGT, MSGT minimizes the number of aborted transactions, accepting all useful schedules many-core system, in: 35th IEEE International Conunder the mixing-correct theorem. In summary, this pa- ference on Data Engineering, ICDE 2019, Macao, per strengthens recent work refuting the assumption that China, April 8-11, 2019, IEEE, 2019, pp. 734–745. graph-based concurrency control is impractical. The next [4] A. Pavlo, What are we doing with our lives?: Nosteps of this PhD projects are: body cares about our concurrency control research, in: Proceedings of the 2017 ACM International Con1. MSGT Optimizations: we have identified two op- ference on Management of Data, SIGMOD Confertimizations to improve MSGT’s performance: rele- ence 2017, Chicago, IL, USA, May 14-19, 2017, ACM, vant reduced DFS and early commit. The first is based 2017, p. 3. on the observation that under the current scheme [5] P. Bailis, A. Davidson, A. D. Fekete, A. Ghodsi, J. M. transactions can unnecessarily abort from detecting Hellerstein, I. Stoica, Highly available transactions: a non-relevant cycle. The second allows weak iso- Virtues and limitations, Proc. VLDB Endow. 7 (2013) lation transactions to commit with incoming edges, 181–192. provided none are relevant to their isolation level, [6] A. Adya, Weak Consistency: A Generalized Thereducing latency. ory and Optimistic Implementations for Distributed 2. Additional Experiments: we will quantify MSGT’s Transactions, PhD Thesis (1999). performance under various application-level bench- [7] A. Pavlo, M. Aslett, What’s really new with marks, e.g., TPC-C [13], and analyze their isolation NewSQL?, SIGMOD Rec. (2016). requirements to help understand where various trans- [8] R. Taft, I. Sharif, A. Matei, N. VanBenschoten, action types occur in practice. J. Lewis, T. Grieger, K. Niemi, A. Woods, A. Birzin, R. Poss, P. Bardea, A. Ranade, B. Darnell, B. Gruneir, 3. Supporting Additional Isolation Levels: this PhD J. Jafray, L. Zhang, P. Mattis, Cockroachdb: The project will explore how MSGT can support additional resilient geo-distributed SQL database, in: Proisolation levels, e.g., Snapshot Isolation [14], and quan- ceedings of the 2020 International Conference on tify the overheads. Management of Data, SIGMOD Conference 2020, June 14-19, 2020, ACM, 2020, pp. 1493–1509. 4. Distributed MSGT: this thesis will explore how [9] D. Huang, Q. Liu, Q. Cui, Z. Fang, X. Ma, F. Xu, MSGT can be integrated into a distributed shared- L. Shen, L. Tang, Y. Zhou, M. Huang, W. Wei, C. Liu, nothing database. Specifically, how isolation levels, J. Zhang, J. Li, X. Wu, L. Song, R. Sun, S. Yu, L. Zhao, e.g., Read Committed, can be highly available [5] in N. Cameron, L. Pei, X. Tang, Tidb: A raft-based the presence of concurrent transactions executing at HTAP database, Proc. VLDB Endow. 13 (2020) isolation levels that are provably unavailable, e.g., Se- 3072–3084. rializable. [10] H. T. Kung, J. T. Robinson, On optimistic methods for concurrency control, ACM Trans. Database Syst.
Acknowledgments 6 (1981) 213–226. [11] Y. Yuan, K. Wang, R. Lee, X. Ding, J. Xing, S. Blanas, J. Waudby was supported by the Engineering and Physi- X. Zhang, BCC: reducing false aborts in optimistic cal Sciences Research Council, Centre for Doctoral Train- concurrency control with low cost for in-memory ing in Cloud Computing for Big Data [grant number databases, Proc. VLDB Endow. 9 (2016) 504–515. EP/L015358/1]. We would like to thank Paul Ezhilchel- [12] B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishvan and Jim Webber for their valuable discussions. nan, R. Sears, Benchmarking cloud serving systems with YCSB, in: Proceedings of the 1st ACM Symposium on Cloud Computing, SoCC 2010, IndianapoReferences lis, Indiana, USA, June 10-11, 2010, ACM, 2010, pp. 143–154. [1] P. A. Bernstein, V. Hadzilacos, N. Goodman, Concur- [13] TPC, Benchmark C, revision 5.11, Technical Report, rency Control and Recovery in Database Systems, TPC, 2010. http://www.tpc.org/tpc_documents_ Addison-Wesley, 1987. current_versions/pdf/tpc-c_v5.11.0.pdf. [2] X. Yu, G. Bezerra, A. Pavlo, S. Devadas, M. Stone- [14] H. Berenson, P. A. Bernstein, J. Gray, J. Melton, braker, Staring into the abyss: An evaluation of E. J. O’Neil, P. E. O’Neil, A Critique of ANSI SQL concurrency control with one thousand cores, Proc. Isolation Levels, in: M. J. Carey, D. A. Schneider VLDB Endow. 8 (2014) 209–220. (Eds.), Proceedings of the 1995 ACM SIGMOD Inter[3] D. Durner, T. Neumann, No false negatives: Ac- national Conference on Management of Data, San cepting all useful schedules in a fast serializable Jose, California, USA, May 22-25, 1995, ACM Press, 1995, pp. 1–10.