Our Paper about Scalar DL is Accepted by PVLDB (VDLB’22)

We are thrilled to announce that our paper titled “Scalar DL: Scalable and Practical Byzantine Fault Detection for Transactional Database Systems” is accepted by PVLDB (regular research track), which is one of the top journals/conferences in the data management area. The paper proposes the Byzantine fault detection protocol that Scalar DL uses. It is a research paper but the protocol has been implemented in Scalar DL and has been used by our customers. The paper will be published soon, and we will be presenting it at VLDB 2022 in Sydney Australia. This blog post shares the abstract and the introduction of the paper. Please also take a look at the previous post to understand what Scalar DL is. (Japanese version)

Abstract

This paper presents Scalar DL, a Byzantine fault detection (BFD) middleware for transactional database systems. Scalar DL manages two separately administered database replicas in a database system and can detect Byzantine faults in the database system as long as either replica is honest (not faulty). Unlike previous BFD works, Scalar DL executes non-conflicting transactions in parallel while preserving a correctness guarantee. Moreover, Scalar DL is database-agnostic middleware so that it achieves the detection capability in a database system without either modifying the databases or using database-specific mechanisms. Experimental results with YCSB and TPC-C show that Scalar DL outperforms a state-of-the-art BFD system by 3.5 to 10.6 times in throughput and works effectively on multiple database implementations. We also show that Scalar DL achieves near-linear (91%) scalability when the number of nodes composing each replica increases.

Introduction

Dealing with malicious attacks such as tampering with data in database systems is becoming increasingly important. The reliance of industry and government on internet services based on database systems makes such attacks more attractive and the consequences of successful attacks more critical. Byzantine fault tolerance (BFT) techniques [1,2,3,4,5,6] have been widely explored to tolerate such attacks. There are several extensions [7,8,9] of the BFT techniques to handle database transactions where multiple operations are executed in an atomic and isolated manner while exploiting the parallelism of the transactions. The BFT techniques are designed for masking Byzantine faults, and the number of replicas to mask 𝑓 faulty replicas needs to be at least 3𝑓 +1.

Although the BFT techniques are elegant, there may be an administrative burden in practice. Specifically, when we assume malicious attacks including internal attacks, replicas need to be placed in different administrative domains (ADs) [10,11,12] because malicious attacks are likely to be dependent, i.e., if there is one Byzantine- faulty replica in an AD, the other replicas in the same AD are also Byzantine-faulty because one fully-privileged administrator of the AD could make any malicious attacks. We could diversify replica implementations [13,14,15] to avoid dependent software errors or bugs, but it is not necessarily effective for malicious attacks. Therefore, a BFT system requires at least four different ADs to guarantee correctness. Managing a database system with this constraint may impose too much administrative burden or may be impractical for some organizations because most organizations have managed database systems in a single AD.

The burden can be mitigated by applying Byzantine fault detection (BFD) techniques introduced in PeerReview [16,17]. PeerReview can only detect Byzantine faults; however, it can detect 𝑓 faulty replicas with only 𝑓 + 1 replicas, i.e., it requires only two replicas (ADs) to detect one faulty replica. It could be a more practical approach for database systems when detection is acceptable.

PeerReview is a general protocol but not designed to work for databases efficiently, i.e., it cannot execute transactions in parallel while preserving a correctness guarantee (strict serializability). PeerReview could be extended to run transactions in parallel by applying concurrency control in a primary replica, but a secondary replica (called witness) still needs to replay the hash-chained log of the primary sequentially to guarantee correctness, which would limit the overall parallelism of transaction execution.

This paper presents Scalar DL, a Byzantine fault detection middleware that executes non-conflicting database transactions in parallel while preserving a correctness guarantee. Scalar DL is specifically designed for managing two database replicas that are separately administered in two ADs in a database system. We focus on using two database replicas for the following reasons: (1) Two is the lower bound for the number of replicas to deal with Byzantine faults; thus, it is the most practical setting from an administrative perspective. (2) It could be a natural extension of the current enterprise database systems with an auditor server [18] where the auditor server is securely (and separately) managed in a remote location.

Scalar DL provides a view of a single-instance database system to users and internally runs two types of database servers in separate ADs: primary database servers that manage a primary database replica holding an application’s data and make all the commit decisions and secondary database servers that manage a secondary database replica holding the same data as the primary database replica for auditing purposes. Both servers separately manage the same set of deterministic functions to derive states and results on the basis of given inputs.

The key of the Byzantine-fault detection protocol of Scalar DL is that the primary and the secondary servers make an agreement on the partial ordering of transactions in a decentralized and concurrent way. The secondary first pre-orders a transaction given from a client partially on the basis of conflicts (ordering phase), and the primary executes and commits the transaction that is ordered by the secondary (execution phase), and then the secondary validates the ordering result given from the primary and executes the transaction (validation phase). The three-phase protocol makes both databases derive the same correct (strict serializable) states and results as long as both ADs are honest, i.e., if either is Byzantine-faulty, their states or results would be diverged, which makes it possible for clients to observe the divergence and detect the fault in the database system.

Scalar DL is database-agnostic middleware so that it achieves the detection capability in a database system without either modifying the databases or using database-specific mechanisms. Scalar DL can currently run on PostgreSQL, MySQL, Oracle Database, Microsoft SQL Server, Apache Cassandra, Apache HBase, Amazon DynamoDB, Amazon Aurora, Azure Cosmos DB, and their compatible databases.

Scalar DL has been used for real-world applications. The primary use case is making database records tamper-evident for digital evidence [19]. We provide solutions for regulations and laws that require tamper evidence of data. For example, regulations on data protection and privacy (e.g., GDPR and CCPA), laws of digital documents around finance and tax affairs, prior user right for intellectual property, and vehicle regulations around software updates with over-the-air (OTA) in WP.29 [20].

To the best of our knowledge, Scalar DL is the first scalable and practical approach that detects Byzantine faults in a database system that manages two database replicas separately in different ADs. This paper’s contributions are as follows:

1. It describes a new Byzantine fault detection protocol for a database system that manages two database replicas in different administrative domains. The detection protocol executes non-conflicting transactions in parallel (thus, achieving good scalability) while guaranteeing correctness.
2. It describes the design and implementation of Scalar DL that applies the detection protocol efficiently using a middleware approach. Scalar DL is general-purpose and database-agnostic middleware so that it can be used with a wide variety of applications and database implementations.
3. It provides experimental results with YCSB and TPC-C workloads to show that Scalar DL outperforms the state-of-the-art approach that extends PeerReview for database transactions when transaction concurrency can be exploited. It also presents that Scalar DL works effectively on multiple database implementations and achieves near-linear scalability when the number of nodes composing each replica increases.

Summary

This blog post shared the abstract and introduction of our Scalar DL paper that is accepted by PVLDB (VLDB’22). Scalar DL provides a new Byzantine fault detection protocol for a database system that manages two database replicas in different administrative domains. The detection protocol executes non-conflicting transactions in parallel (thus, achieving good scalability) while guaranteeing correctness. Once the paper is published, we will share the paper so please look forward to it.

References

1. A. Bessani, J. Sousa, and E. E. P. Alchieri. 2014. State Machine Replication for the Masses with BFT-SMART. In DSN. 355–362.
2. M. Castro and B. Liskov. 1999. Practical Byzantine Fault Tolerance. In OSDI. 173–186.
3. L. Lamport, R. Shostak, and M. Pease. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4, 3 (1982), 382–401.
4. M. Pease, R. Shostak, and L. Lamport. 1980. Reaching Agreement in the Presence of Faults. J. ACM 27, 2 (1980), 228–234.
5. Yin, J. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin. 2003. Separating Agreement from Execution for Byzantine Fault Tolerant Services. In SOSP. 253–267.
6. M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In PODC. 347–356.
7. R.Garcia, R.Rodrigues, and N.Preguiça. 2011. Efficient Middleware for Byzantine Fault Tolerant Database Replication. In EuroSys. 107–122.
8. F. Suri-Payer, M. Burke, Z. Wang, Y. Zhang, L. Alvisi, and N. Crooks. 2021. Basil: Breaking up BFT with ACID (Transactions). In SOSP. 1–17.
9. B. Vandiver, H. Balakrishnan, B. Liskov, and S. Madden. 2007. Tolerating Byzantine Faults in Transaction Processing Systems Using Commit Barrier Scheduling. In SOSP. 59–72.
10. T. Distler. 2021. Byzantine Fault-Tolerant State-Machine Replication from a Systems Perspective. ACM Comput. Surv. 54, 1, Article 24 (2021), 38 pages.
11. J. LiandD. Maziéres. 2007. Beyond One-Third Faulty Replicas in Byzantine Fault Tolerant Systems. In NSDI.
12. M. Vukolić. 2010. The Byzantine Empire in the Intercloud. SIGACT News 41, 3 (2010), 105–111.
13. A. Avizienis. 1985. The N-Version Approach to Fault-Tolerant Software. IEEE Trans. Softw. Eng. SE-11, 12 (1985), 1491–1501.
14. S. Forrest, A. Somayaji, and D.H. Ackley. 1997. Building Diverse Computer Systems. In HotOS. 67–72.
15. M. Garcia, A. Bessani, and N. Neves. 2019. Lazarus: Automatic Management of Diversity in BFT Systems. In Middleware. 241–254.
16. A. Haeberlen, P. Kouznetsov, and P. Druschel. 2006. The Case for Byzantine Fault Detection. In HotDep.
17. A. Haeberlen, P. Kouznetsov, and P. Druschel. 2007. PeerReview: Practical Accountability for Distributed Systems. In SOSP. 175–188.
18. Oracle. 2022. Oracle Audit Vault and Database Firewall. https://www.oracle.com/database/technologies/security/audit-vault-firewall.html.
19. E. Casey. 2011. Digital Evidence and Computer Crime: Forensic Science, Computers, and the Internet (3rd ed.).
20. United Nations Economic Commission for Europe. 2022. Vehicle Regulations. https://unece.org/transport/vehicle-regulations.