Data fragmentation and replication schemes play an important role in making parallel and transactional databases scalable and reliable. Existing data schemes generally assume a trusted environment where a node may fail, but no node will act adversarially. Here, we present our vision for RLShard, a reinforcement learning-powered fragmentation and replication scheme for transactional databases in Byzantine environments capable of adapting to dynamic workloads. We first describe the implications of Byzantine environments on data fragmentation schemes. Then, we explore two diferent system architectures for RLShard: a centralized architecture that relies on a trusted administrative domain and a fully decentralized architecture that uses collaborative reinforcement learning. Based on our first-cut design, we outline open research challenges towards our vision of adaptive fault-tolerant sharded databases.
solve the problem in an adaptive way, moving data beDistributed systems rely on fault-tolerant protocols to tween fragments, and moving fragments between nodes, provide robustness and high availability [1, 2, 3, 4, 5, 6, 7]. in an online fashion, many are designed for analytical While trusted cloud systems (e.g., Google’s Spanner [3], OLAP [27, 28] workloads and might not efectively adapt Amazon’s Dynamo [4], Facebook’s Tao [5]) rely on crash to transactional OLTP applications that frequently exfault-tolerant (CFT) protocols, e.g., Paxos [8], to establish perience unpredictable demand shifts [26]. To the best consensus, trust-free systems (e.g., blockchains [9, 10, of our knowledge, none of these adaptive approaches 11, 12, 13, 14, 15], lock servers [16], certificate authority consider Byzantine environments [29, 30, 31]. Byzantine systems [17]) must use Byzantine fault-tolerant (BFT) environments bring a number of specific complications protocols to cope with untrustworthy infrastructure. to the data fragmentation problem:
Both CFT and BFT consensus protocols incur higher BFT vs. CFT Scalability. While all fragmentation latency when more nodes are involved. Thus, trusted schemes designed for transactional DBMSes hope to min(e.g., [3, 18, 19]) and trust-free (e.g., [20, 21, 22]) systems imize the number of cross-shard transactions, the cost fragment their data into shards, and each shard is repli- of a cross-shard transaction is significantly higher in cated on multiple nodes with the goal of minimizing the an adversarial context. A round of Paxos [8] consensus number of cross-node transactions. amongst nodes requires () messages, but a round
Approaches like SWORD [23] and Schism [24] find of (for example) PBFT [
Unfortunately, what was optimal yesterday may not nodes failing, data must be replicated 2 + 1 times. In a be optimal today: as workloads drift and new data is Byzantine environment, data must be replicated a miniadded, previously-optimal fragmentation schemes can mum of 3 +1 times in order to tolerate adversarial nodes. become arbitrarily poor. Several studies [25, 26] thus Additionally, a non-Byzantine system may label certain replicas as “primary” or “secondary”, allowing transactions to only write changes to the “primary” replica. Such JBoaisnets W(VoLrkDsBhWop’s2a3t) 4—9tWhoInrktesrhnoaptioonnaAlpCpolinefderAenIcfeoronDaVtearbyaLsaerSgyesDteamtas a strategy is not possible in a Byzantine environment: all and Applications (AIDB’23), August 28 - September 1, 2023, Vancouver, nodes must participate in every transaction to ensure no Canada adversarial node lies to the client. $ bhavanam@seas.upenn.edu (B. Mehta); neelca@seas.upenn.edu Non-trustworthy data. Traditional fragmented (mNj.aCm.iAri@);pseraassh.uipyer@nns.eeadsu.u(pMe.nJn..Aedmuir(iP).; Sb.oIoynelro);o@seas.upenn.edu databases can accurately observe nodes required for each (B. T. Loo); rcmarcus@seas.upenn.edu (R. Marcus) transaction. In a Byzantine environment, adversarial © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License nodes could lie about a cross-node transaction to induce CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) a particular fragmentation scheme. For example, an ad- GGrroouuppeedd PP9500 vacecrseassrieadl tnoogdeethceoru,lcdauresipnogrtatnhaaitvae sfreatgomf etunptaletisoanrsecnheevmeer cond 800 FFllaatt PP9500 to separate those tuples onto multiple nodes, potentially rsee 600 causing a denial-of-service attack. snp
This paper presents our initial design of RLShard, a itscoa 400 scalable distributed database system capable of tolerating rTan 200 Byzantine faults and adapting to dynamic workloads. We aim to develop a machine learning-based mechanism for optimizing shard assignments to nodes, based on work- 5 10 15# nodes20 25 30 load characteristics, to maximize system performance. Figure 1: Worst-case throughput (50th and 90th percentile)
We explore two system architectures to achieve this “oGf raouhpyepdo”tphuettiscanlode=s1inctolugstreorupwsitohf 4v,aurysiinngg 2nPoCdebectowuenetns. goal. The first is a centralized architecture with a trusted and PBFT within groups. “Flat” uses PBFT between all nodes. learner, assuming that the learning agent and the transaction router are within a trusted Administrative Do- of each tuple such that no query ever needs to synchromain (AD) [33, 34, 35], immune to attacks. It uses a cen- nize with more than 4 “primary” nodes. In a Byzantine tralized learner for shard allocation decisions, ensuring context, a client accessing a particular tuple must comByzantine fault tolerance. The second is fully decentral- municate directly with all active nodes containing that ized, with no trusted components, and using collabo- tuple. In the worst case, an adversarial client might need rative reinforcement learning (CRL). This architecture consensus from the emtire cluster, referred to as “Flat” aims to overcome reliance on a central entity by enabling layout. To alleviate this worst-case scenario, we sacrifice node collaboration. Through reinforcement learning (RL), some flexibility in the replication strategy. In RLShard, nodes collectively determine shard allocation to optimize we create groups of 3 + 1 nodes that each contain the performance, triggering resharding when needed, and exact same set of data. Now, if a client must commit a enhancing resilience and adaptability without external transaction that touches every node, the client can use a intervention. two-phase commit strategy: first, a prepare message is
Our contributions comprise RLShard’s design, explo- sent to each group of 3 + 1 nodes. If all groups can comration of two architectures for sharding assignments, and mit, the client issues a commit message to each group. development of adaptive and fault-tolerant mechanisms Within each group, a BFT algorithm is used to ensure an to optimize performance. By addressing the limitations of adversarial node cannot interfere with the transaction. existing solutions, RLShard aims to provide an efective We refer to this layout as “Grouped”. sharding assignment strategy for distributed databases, This approach might compromise consistency if a node capable of withstanding Byzantine attacks and dynami- group fails between sending a prepare message and the cally adjusting to changing workloads. ifnal commit. But the scalability benefits are significant – Figure 1 shows the worst-case (all nodes involved in 2. RLShard a transaction) throughput for the “Grouped“ and “Flat” RLShard is designed for an asynchronous network con- layouts. While the “Grouped” layout shows higher varisisting of a set of servers. We assume that the cluster’s ance than the “Flat” layout, the “Grouped” layout has total storage capacity is at least 3 + 1 times the database significantly better throughput for larger cluster sizes. size for Byzantine fault tolerance, and while any server In RLShard, an agent uses RL for adaptive partitioning can experience adversarial faults, at most might fail and directs client transactions via a router. The expericoncurrently. All client requests are equally important; mental setup for Figure 1 used a simulated distributed i.e., if a client is adversarial, we still need to accurately system on Linode’s 16-vCPU Dedicated instance with answer their valid queries. an AMD EPYC 7713 64-Core Processor and 32 GB RAM,
Section 2.1 describes the grouped data layout used implemented using Python over TCP. by RLShard which can tolerate Byzantine failures and mitigates the performance impact of adversarial clients.
Section 2.2 describes RLShard’s hypergraph-based model for finding fragmentation strategies.
Traditional distributed database systems may replicate diferent fragments on diferent nodes, allowing each node to hold a unique combination of data. Thus, one could design a replication strategy with = 4 replicas
To partition data, we leverage hypergraph partitioning techniques [23, 24, 36] where data are represented as a hypergraph. Nodes within the hypergraph represent individual data fragments, and hyperedges represent relationships or dependencies between diferent data elements. The hypergraph partitioning algorithm considers data locality, cost, and balance to optimize partitioning, aiming to maximize parallelism and scalability by re
ture design for RLShard, consisting of a centralized router and learning agent, as shown in Figure 2. We assume that the centralized components operate within a trusted environment, ensuring protection against attacks [18].
RLShard has three components: (i) A transaction router directing client requests and consulting the shard catalog, (ii) A learning agent deciding when to reshard, and (iii) Clusters storing shards with fault tolerance. Data in clusters is replicated 3 + 1 times (where denotes maximum faulty nodes), with consensus protocols for synchronization.
We choose RL for sharding assignments instead of heuristics like SWORD[23] and Schism[24] because heuristics often fail to capture the dynamic nature of distributed database systems. RL, on the other hand, can handle the dynamic nature of cross-shard transactions and varying • is potential gains from throughput and latency. • denotes the resharding-related costs, calculated by the data volume (in megabytes) required to be moved. • signifies the overhead incurred from resharding, computed by the number of shards involved. • is a linear weighting factor learned from experimentation, employed to combine these parameters. It is adaptable to diferent trade-ofs in the system. Using this reward function, the learning agent is incentivized to reshard when anticipated benefits surpass costs, efectively balancing immediate costs against long-term performance gains. The agent aims to learn an optimal policy (|), which determines the action to be taken given a particular state. Through ongoing interaction with the environment and reward-driven feedback, the agent iteratively refines its policy to maximize cumulative expected rewards over time.
The centralized architecture, however, has two drawbacks. First, there is a single point of failure. If the learning system or the transaction router experienced failures or becomes compromised (in the absence of trusted hardware), it can significantly impact the performance and reliability of the entire system. Second, the centralized nature may introduce scalability limitations as the system grows in terms of workload and network size.
collaborative reinforcement learning (CRL) to address the limitations inherent in the centralized architecture. This design eliminates trusted components, distributing decision-making across clusters.
Traditional RL algorithms tend to optimize for individual rewards, leading to convergence at trivial equilibrium points[40, 41]. In contrast, our decentralized approach promotes cooperation amongst shards to maximize the system’s collective reward. Through CRL, agents adjust their strategies to eficiently distribute fragments among shards, optimizing database performance [42].
In our decentralized configuration (Figure 3), the client sends requests to each cluster. Clusters with the relevant fragments respond, eliminating the need for a centralized router. Each cluster features its own learning agent, which collaborates through CRL. These agents exchange insights and refine decisions based on local feedback, ensuring eficient fragment distribution.
The goal is collective training for optimal fragment assignments. To formulate this, we define local components for each learner: State: Represents fragments within the agent’s local shard and others.
Action: Agents propose fragment exchanges to other shards and decide on the acceptance or rejection of proposals received from other shards. The collaborative decision-making process involves identifying beneficial exchanges for the entire system.
Reward: The reward is analogous to the centralized architecture but the decentralized approach presents two complications: firstly, in a decentralized setting, each node must act independently to lower the global function, unlike the centralized case where a global solution can be computed. Secondly, the agents know the throughput of the queries on their node but lack knowledge of others’ throughput resulting in diferences in mechanisms and input outputs, unlike the centralized architecture.
Learning agents across shards iteratively interact for rewards, updating policies to maximize cumulative expected rewards based on cluster observations. Through CRL, agents collaborate for eficient shard fragment distribution. The ultimate objective is optimizing system throughput, minimizing latency, and enhancing overall database performance by learning the optimal fragment movement strategies.
To centralize or to distribute? Our first-cut solution requires clients to either deploy a transaction router or broadcast requests to all shards. The former may not be feasible for large datasets (not to mention cloud providers are unlikely to expose data placement to clients), while a broadcast-based approach may add significant overhead in the presence of a large number of shards. One possibility is a hybrid approach, where the transaction router remains centralized, while the learning and monitoring are decentralized (i.e., each shard runs its own learning agent). Such a hybrid approach may achieve a good balance between security and performance. Cooperative RL with local rewards: Traditional cooperative RL presumes a universal reward. For example, three robots might collaborate in order to win a game against humans, and each robot has access to objective information about the score of the game. In our setting, each shard has access to a “local” reward signal, the number of cross-shard transactions that one particular shard was involved with. Adapting these algorithms to a system’s context will require careful research to maintain the theoretical benefits of prior work.
Exploration and exploitation in an adversarial environment. A major downside to using RL for systems is the need for exploration: the algorithm must test unknown policies that have the potential to be good or bad. Balancing exploration and exploitation in an adversarial environment is even more dificult than in nonadversarial domains, since a smart attacker may try to induce exploration into particularly bad parts of the policy space. We plan to explore techniques to mitigate these attacks, as well as come up with techniques that allow us to balance exploration and exploitation.
Byzantine fault-tolerant sharded database, proposing both centralized and decentralized architectural solutions.
While the centralized architecture relies on a trusted administrative domain to learn optimal sharding, in the decentralized architecture, diferent clusters communicate with each other to learn the best sharding layout through collaborative reinforcement learning. We laid out our research plan, open research challenges that we aim to tackle. [25] R. Marcus, O. Papaemmanouil, S. Semenova, S. Gar- puting Surveys (CSUR) 54 (2021) 1–38. ber, NashDB: An End-to-End Economic Method for [34] J. Li, D. Maziéres, Beyond one-third faulty replicas Elastic Database Fragmentation, Replication, and in byzantine fault tolerant systems., in: Symposium Provisioning, in: Proceedings of the 37th ACM on Networked Systems Design and Implementation Special Interest Group in Data Management, SIG- (NSDI), USENIX Association, 2007. MOD ’18, Houston, TX, 2018. doi:https://doi. [35] M. Vukolić, The byzantine empire in the intercloud, org/10.1145/3183713.3196935. ACM Sigact News 41 (2010) 105–111. [26] R. Taft, E. Mansour, M. Serafini, J. Duggan, [36] I. Kabiljo, B. Karrer, M. Pundir, S. Pupyrev, A. J. Elmore, A. Aboulnaga, A. Pavlo, M. Stone- A. Shalita, A. Presta, Y. Akhremtsev, Social hash braker, E-Store: Fine-grained Elastic Partitioning partitioner: a scalable distributed hypergraph partifor Distributed Transaction Processing Systems, tioner, arXiv preprint arXiv:1707.06665 (2017). PVLDB 8 (2014) 245–256. URL: http://dx.doi.org/10. [37] J. Gray, A transaction model, in: Autonmata, Lan14778/2735508.2735514. doi:10.14778/2735508. guages and Programming: Seventh Colloquium No2735514. ordwijkerhout, the Netherlands July 14–18, 1980 7, [27] B. Hilprecht, C. Binnig, U. Röhm, Learning a parti- Springer, 1980, pp. 282–298. tioning advisor for cloud databases, in: Proceedings [38] Z. Yang, R. Yang, F. R. Yu, M. Li, Y. Zhang, Y. Teng, of the 2020 ACM SIGMOD International Confer- Sharded blockchain for collaborative computing in ence on Management of Data, 2020, pp. 143–157. the internet of things: Combined of dynamic clus[28] P. Parchas, Y. Naamad, P. Van Bouwel, C. Faloutsos, tering and deep reinforcement learning approach, M. Petropoulos, Fast and efective distribution-key IEEE Internet of Things Journal 9 (2022) 16494– recommendation for amazon redshift, Proceedings 16509.
of the VLDB Endowment 13 (2020) 2411–2423. [39] H. Huang, X. Peng, J. Zhan, S. Zhang, Y. Lin, [29] X. Zhou, G. Li, J. Feng, L. Liu, W. Guo, Grep: A Z. Zheng, S. Guo, Brokerchain: A cross-shard graph learning based database partitioning system, blockchain protocol for account/balance-based Proceedings of the ACM on Management of Data 1 state sharding, in: IEEE INFOCOM 2022-IEEE Con(2023) 1–24. ference on Computer Communications, IEEE, 2022, [30] K. Rzadca, P. Findeisen, J. Swiderski, P. Zych, pp. 1968–1977.
P. Broniek, J. Kusmierek, P. Nowak, B. Strack, P. Wi- [40] J. K. Gupta, M. Egorov, M. Kochenderfer, Cooperatusowski, S. Hand, et al., Autopilot: workload au- tive multi-agent control using deep reinforcement toscaling at google, in: Proceedings of the Fifteenth learning, in: Autonomous Agents and Multiagent European Conference on Computer Systems, 2020, Systems: AAMAS 2017 Workshops, Best Papers, pp. 1–16. São Paulo, Brazil, May 8-12, 2017, Revised Selected [31] D. Golovin, G. Bartok, E. Chen, E. Donahue, Papers 16, Springer, 2017, pp. 66–83.
T.-K. Huang, E. Kokiopoulou, R. Qin, N. Sarda, [41] J. Dowling, V. Cahill, Self-managed decentralised
J. Sybrandt, V. Tjeng, Smartchoices: Augment- systems using k-components and collaborative
reing software with learned implementations, arXiv inforcement learning, in: Proceedings of the 1st
preprint arXiv:2304.13033 (2023). ACM SIGSOFT Workshop on Self-managed
Sys[
erance, in: Proceedings of the third symposium [42] L. Matignon, G. J. Laurent, N. Le Fort-Piat, Hyson Operating systems design and implementation, teretic q-learning: an algorithm for decentralized OSDI ’99, USENIX Association, USA, 1999, pp. 173– reinforcement learning in cooperative multi-agent 186. teams, in: 2007 IEEE/RSJ International Conference [33] T. Distler, Byzantine fault-tolerant state-machine on Intelligent Robots and Systems, IEEE, 2007, pp. replication from a systems perspective, ACM Com- 64–69.