1 Introduction
Alphabet
, Amazon
and Twitter
while share no weak investment signal in common. As a result, the HFT workloads interleave much contended operations with rarely contended ones, which reflect strong and weak investment signals, respectively.
update
on Alphabet
, determines the serializable order of the two transactions, i.e., \(T_1\) happens before \(T_2\). Then, any operation in \(T_2\) must follow this order; otherwise, the operation will be re-executed after a violation is detected. As Fig. 1a illustrates, this is equivalent to delaying the execution of any operation in \(T_2\) till the completion of its corresponding conflicting operation in \(T_1\). On the one hand, this allows \(T_2\) to perform update(Alphabet)
before \(T_1\) completes. Thus, transaction pipeline indeed outperforms all of 2PL, OCC and MVCC, which do not allow any overlapping execution because otherwise deadlock (2PL) or rollback (OCC and MVCC) will happen. On the other hand, the second update in \(T_2\) on Twitter must be delayed until the completion of \(T_1\). Compared to Fig. 1b, which reorders the execution of \(T_1\) and \(T_2\) according to Listing 2, we can see that the delay in Listing 1 unnecessarily compromises throughput and increases transaction latency.
-
We show the importance of reordering transaction execution for the state-of-the-art CC mechanism transaction pipeline under HFT applications.
-
We observe and formulate harmful ordering under transaction pipeline and propose to rearrange statements in decreasing order of contention to eliminate harmful ordering.
-
We propose two mechanisms to ensure the correctness of rearrangement of transaction statements and measure the degree of contention to enforce the elimination of harmful ordering.
-
We formulate the off-line reordering problem, prove it is NP-hard and present an approach to approximate the optimal reordering schedule.
-
We conduct experiments to demonstrate the effectiveness and practicality of PARE.
2 Preliminary and Related Works
2.1 Transaction Pipeline
2.2 Related Works
3 Pipeline-Aware Reordered Execution
3.1 Reordering Strategy
update(Alphabet)
of transaction \(T_2\) in Fig. 1. Because it is undefined to write to the same object simultaneously, such delay is inevitable. Fortunately, this kind of delays lasts for only one operation and thus can be neglected in transaction execution. The second kind of delays can last indefinitely long time, such as the update(Twitter)
of transaction \(T_2\) in Fig. 1a. We observe that such delay is formed when non-conflicting operations are encompassed by conflicting operations and formulate this observation as harmful ordering of conflict statements.update(Alphabet)
and update(Twitter)
of \(T_1\) and \(T_2\) are two conflicting operations. Condition 2 and condition 3 hold because there is no operations between update(Alphabet)
and update(Twitter)
in \(T_1\), while there are other operations between update(Alphabet)
and update(Twitter)
in \(T_2\).3.2 Reordering Block Extraction
read-after-write
dependency.write-after-read
dependency.write-after-write
dependency.if
-statement and loop
-statement as a whole statement, although sophisticated techniques such as loop fossil can make fine-grained dependency tracking [39, 42]. As for SQL queries, we precisely model the dependency relationships among the query input and output:where
clause. Empty where
clause leads to a universal read set. The write set is set to empty.where
clauses. If empty where
clause occurs in one of the sub-queries, the read set of the query is also a universal set. The write set is set to empty.3.3 Contention Estimation
update(Alphabet, 30)
is usually instantiated as update Stock set quantity -= 30, price = p where sid = Alphabet
, where p
is the latest price provided by user. Thus, many statements updating the same quantity and price fields are counted in different counters. (2) Estimating waiting time and its variance suffers from thrashing. This is because properly reordered highly contended operations will not wait for long time and thus are always categorized as less contended operations. Then, these operations will be placed to the end of the transaction and be considered as heavily contended operations again. To address these two issues, we propose an execution plan-based estimation which collects the occurrence of each object in a time sliding window.update(Alphabet, 30)
may update different prices, its corresponding physical operator will have the same type of update
and indicate the same fields of quantity
and price
. The only difference is the parameters for the target values. Because contention only occurs at the operator placed at the bottom level of the execution plan in form of a tree structure, it is sufficient to allocate a counter recording the occurrence frequency for each physical operator at the bottom level of the execution plan. Algorithm 2 details the counter implementation. The time sliding window size WS is discretized into time slots with granularity of g so that when the time flows, the time slots are recycled to reflect the latest count. Once one physical operator is created at the bottom level of the execution plan, the Increment
of the associated counter is invoked. Once we extract all reordering blocks, we invoke Get
for each counter within each reordering block and pick up the maximum count as the degree of contention for each reordering block.4 Off-line Reordering
4.1 Problem Formulation
4.2 GA-Based Approach
4.3 SA-Based Approach
5 Experiment
5.1 Experimental Setting
5.2 Performance Comparison
5.3 Detailed Performance
readSet
and writeSet
for SQL queries. Except for the Market-Feed transaction, which occupies 1% in TPC-E workload, the extraction of reordering blocks consumes less than 5% of the execution time. This demonstrates that the overhead of reordering block execution is limited and PARE is practical to typical OLTP workloads.Transaction type | Extraction time (ms) | Execution time (ms) | Ratio (%) |
---|---|---|---|
New-order | 0.28 | 7.1 | 3.9 |
Payment | 0.26 | 8.4 | 3.1 |
Order-status | 0.12 | 7.6 | 1.6 |
Delivery | 0.07 | 6.2 | 1.1 |
Stock-level | 0.02 | 12 | 0.2 |
Transaction type | Extraction time (ms) | Execution time (ms) | Ratio (%) |
---|---|---|---|
Broker-volume | 0.01 | 4.3 | 0.2 |
Market-feed | 0.21 | 3.8 |
5.5
|
Security-detail | 0.08 | 2.6 | 3.1 |
Trade-order | 0.36 | 7.4 | 4.8 |
Trade-status | 0.03 | 7.7 | 0.4 |
Customer-position | 0.05 | 4.9 | 1.0 |
Market-watch | 0.17 | 9.6 | 1.8 |
Trade-lookup | 0.07 | 9.4 | 0.7 |
Trade-result | 0.41 | 8.3 | 4.9 |
Trade-update | 0.15 | 13.9 | 1.1 |