Wait and See: A Delayed Transactions Partitioning Approach in Deterministic Database Systems for Better Performance

Deterministic databases are revolutionizing batch transaction processing in shared-nothing architectures, with efficiency largely hinging on minimizing cross-partition operations. However, achieving a universal data partition that eliminates cross-partition operations is often impractical. Thus, developing effective transaction partitioning strategies becomes crucial. Existing methods tend to partition and optimize transactions individually, neglecting the overarching commonalities between transactions within a batch. This oversight results in suboptimal partitioning of transactions that share similar read-write sets, ultimately missing opportunities for global batch execution optimization. In this paper, we present DelayPart, a deterministic database transaction engine that employs a ''wait and see'' strategy to address contextual conflicts between transactions within each batch. DelayPart models transaction batch partitioning as a k -cut problem based on transaction similarity and employs a LSH forest-based approach to approximate solutions efficiently in linear time, factoring in the global overhead of remote operations for each batch. By postponing the allocation and execution of individual transactions, DelayPart systematically analyzes inter-transaction relationships, enhancing overall performance without compromising execution efficiency. We evaluated DelayPart's performance against various benchmarks on a large-scale cluster, demonstrating that it significantly outperforms state-of-the-art transaction partitioning methods.