Data replication plays a crucial role in decentralized systems by enhancing durability and availability. The ADR algorithm is a dynamic replication method that optimizes communication costs by adaptively adjusting the number of replicas. However, it overlooks workload costs, which are critical in real-world applications, leading to suboptimal performance, especially in parallel processing environments. To address this limitation, we propose an enhanced ADR algorithm that incorporates both communication and computational costs. Our method refines the cost model by considering the maximum-cost execution path in update transactions, ensuring a more accurate workload estimation. Additionally, we introduce an improved expansion-contraction test that eficiently optimizes replication placement. Experimental evaluations across various network topologies demonstrate that the proposed method achieves up to 12% higher throughput than the existing ADR algorithm, particularly in read-heavy environments. These results indicate that our approach provides a more balanced and eficient replication strategy, adapting to diverse workload patterns in decentralized systems.
Data replication is a fundamental technique in decentralized systems, where data is replicated and stored across multiple processors. When writing data, transactions synchronize update transactions on the replicas across multiple processors to ensure durability. When reading data, the data can be retrieved from any processor holding the latest version, thereby maintaining consistency.
The number of processors where the latest data is replicated (we call replication processors) is a critical factor in data replication and can significantly impact system performance; e.g., in systems with read-heavy workloads, if the number of replication processors is small, it leads to frequent data retrieval from remote replication processors, degrading performance. In contrast, in systems with update-heavy workloads, if the number of replication processors is large, it increases the update load and degrades performance. Thus, for read-heavy workloads, the number of replication processors should be large to reduce the number of data retrievals from remote replication processors, while for update-heavy workloads, the number of replication processors should be small to decrease the update loads.
The optimal number of replication processors typically
depends on the frequency of read and update transactions
on each processor. In many decentralized systems, system
designers must define the number of replication processors
statically during the design phase, and then manually adjust
it during the production phase [
To overcome the above issues, we propose an enhanced ADR algorithm. Specifically, in addition to communication costs, we consider processor computational costs, allowing for a more accurate estimation of overall workload cost. Furthermore, since the execution time of update transactions in parallel environments is determined by the heaviest computational path, we redefine update transaction cost by focusing only on the maximum cost path, rather than summing up the weights of all paths.
In decentralized systems, minimizing the workload cost
across the entire system is a critical factor. We focus on
applications that perform system-wide operations with the
objective of reducing overall workload cost. Various dynamic
replication algorithms have been proposed [
A replication scheme represents the set of processors that hold the latest replicas and forms a variable-sized “amoeba” that shifts toward the center of the network of read/write (read/update) requests. is created for each data object. When the number of read requests increases, the ADR algorithm expands to reduce the communication cost by responding to read requests from a local processor or nearby CEUR
ceur-ws.org p3 p4 p5 2.2. Expansion and Contraction is periodically adjusted through expansion and contraction1 every fixed period. Expansion occurs in systems with read-intensive workloads, increasing the size of (i.e., adding more processors to ) to reduce the communication cost between the requesting processor and the processors. In contrast, contraction occurs in systems with writeintensive workloads, decreasing the size of (i.e., removing processors from ) to reduce the communication cost between the processors. Whether to expand or contract is determined by executing the expansion and contraction tests, respectively.
The ADR algorithm focuses solely on optimizing communication cost and does not consider workload cost, which is more critical in real-world applications. As a result, it fails to consider disparities in processing costs among processors or disparities in the execution times of transactions between read and write operations.
Additionally, in parallel processing environments, there are cases where communication time increases, but trans1There is also an operation called “Switch”. However, since the main algorithm consists primarily of expansion and contraction, it is omitted here for simplicity. action execution time decreases. In such situations, the ADR algorithm prioritizes minimizing communication cost, which can inadvertently prolong overall transaction execution time.
This section introduces an improved version of the ADR algorithm. As noted earlier, the ADR algorithm optimizes only communication cost, neglecting workload cost, which is more crucial in real-world applications. To overcome this issue, the proposed method modifies the cost function of the ADR algorithm and redefines the optimization equation for a more realistic workload representation.
Specifically, in addition to communication costs, the proposed method considers processor computational costs, allowing for a more accurate estimation of overall workload cost. Furthermore, since update transaction processing time in parallel execution environments is determined by the heaviest computational path, the proposed method redefines update transaction cost by focusing only on the maximum cost path, rather than summing up the weights of all paths.
We revise the ADR algorithm to optimize the workload cost across the entire system. To optimize the workload cost rather than the communication cost, we extend the objective formula using not only the number of communications but also its associated read/update cost.
The workload cost and optimization formulation are deifned as follows:
Cworkload() ∶= ∑(#U( , ) ×
Cu( , ) ∈ + #F( , ) ×
Cr( , )) argmin Cworkload() where denotes a processor in the network, denotes the set of all processors, denotes the replication scheme, #U( , ) denotes the number of update transactions, Cu( , ) denotes the cost of an update transaction, #F( , ) ber of fetch transactions, and Cr( , ) denotes the numdenotes the cost of a read transaction. The goal of the optimization formula is to ifnd the replication scheme that minimizes the workload cost. In practice, is gradually adjusted to progressively reduce the workload cost as much as possible.
In the proposed method, #F( , ) , Cr( , ) , and Cu( , ) are defined as follows:
Cu( , ) ∶= #F( , ) ∶= # Cr( , ) ∶= allowing local reads with zero cost. Therefore, the workload cost at a processor considers only the read costs incurred by fetch operations, which is determined by multiplying the number of read transactions #R( , ) ( , ) , resulting in #F( , ) . by the cache miss rate
The workload cost is optimized through an expansioncontraction test, which is executed after every successfully completed transactions. In the expansion-contraction test, for each expansion-contraction pattern, the system determines whether to expand expandable processors or shrink shrinkable processors by calculating the diferential workload cost.
Similar to the ADR algorithm, each expansioncontraction test restricts operations such as expanding or contracting beyond one hop and forming a discontinuous . These restrictions are imposed due to computational complexity concerns and the potential excessive fluctuation in #F( ) and #U( ) before and after expansion-contraction.
Next, we explain the method for computing () , the optimal expansion-contraction pattern set that minimizes the diferential workload cost. () is calculated as follows: () = argmin Cworkload( , ) − Cworkload() ⊆, ⊆ = argmin ∑ #U( , , ) × Lu( , , ) ⊆, ⊆ ∈ + ∑ #F( , ) × Δ , Lr( , ))
∈ − ∑ #U( , ) × ∈ where denotes the set of expandable processors, and represents the set of contractible processors. , denotes the replication scheme after expanding processors and contracting processors . Δ , () denotes ( , ) − () . Here, assuming that Δ , = , − is suficiently small, it is approximated that #U( , ) = # U( , , ) and #F( , ) = # F( , , ).
Equation 1 requires evaluating all possible patterns, where each expandable processor can either be expanded or not, leading to 2|| possibilities, and each contractible processor can either be contracted or not, leading to 2|| possibilities. A straightforward computation results in an exponential search space of (2 ||+|| ), which is impractical for scalability. Thus, reducing the search space is necessary.
Figure 2 illustrates the concept of reducing the search space (processors and nodes are treated as equivalent in this ifgure). For simplicity, assume that updates originate only from the center processor of the -tree (we call -center processor) and that all processor-to-processor distances are 1. After expansion-contraction, processors can be grouped based on their distance from the -center processor, referred to as the maximum -center distance in this paper. Graphs with identical maximum -center distances exhibit the same update costs, making total cost dependent solely on read operations. Since read costs decrease as expands, only the case with the largest set within each group needs to be considered. Thus, the number of such groups determines the search space, which corresponds to the possible values of the maximum -center distance after expansion-contraction, resulting in a complexity of (|| + ||) .
Only -leaf processors can become maximum -center processors after expansion-contraction. The number of possible types of -leaf processors after expansion-contraction consists of the original -leaf processors (|| ), newly expanded -leaf processors (|| ), and processors that became -center node 2
Distance from
Enumerate of -center node is 1 expansion-contraction The one with the most
pattern node is optimal
Assume that updates occur only from the -center node Di-scteanncteerfnroomde is 2 -leaf processors due to contraction (|| ). Since all preexpansion -leaf processors must be contractible, there are exactly || such processors. Consequently, the worst-case search space is (|| + || + ||) = (|| + ||) . In Figure 2, there are only two groups based on the maximum -center distance: 1 and 2, meaning that only these two groups need to be considered for optimal expansion-contraction patterns.
However, in real scenarios, updates originate from multiple processors, not just the center processor. In such cases, even if the maximum -center distance remains unchanged, the -eccentric distance (the maximum shortest distance from an processor to any other processor) may vary, requiring separate calculations. By treating these separately, the search space is proven (proof omitted) to be ((|| + ||) 2| ( )|) where ( ) denotes neighboring processors of the -center processor. Additionally, using tree dynamic programming (DP) and the sliding window technique, the expansion-contraction test can be computed in (| | + | ( )|(|| + ||) log(|| + ||)) time.
This section presents experimental evaluations comparing the proposed method 2 with the ADR algorithm across three characteristic topologies.
We conducted the experiments on an EC2 m5.16xlarge
instance using Dejima [
We consider two types of transactions: (1) Update that
modifies a column in a record, and (2) Read that reads all
columns of a record. The table structure, update method,
and read method in the RDBMS adhered to the YCSB [
Line(9)
General(10) When generating the initial records for each table, record insertions into the base table of each processor were propagated to multiple processors via Dejima’s data-sharing mechanism. In this experiment, 100 records were inserted into each processor as initial records, and these records were propagated across the entire system. For example, in General(10), 100 records are initially inserted into each processor, resulting in a total of 1,000 records.
4.2.1. Star Topology The experimental results for the star topology are shown in Table 1 and Table 2. Table 1 compares the case where the replication scheme is minimized, meaning only the center processor is part of , and the case where is maximized, meaning updates are propagated to all processors. Table 2 shows the results of the existing method (the ADR algorithm) and the proposed method, along with their ratio (relative throughput).
For Star(4), as shown in Table 1, as the read ratio increases, max || achieves higher throughput than min || , with the performance gap widening at higher read ratios. As the proportion of read transactions increases, their impact becomes greater than that of update transactions, making it more efective to expand to reduce workload cost.
A comparison of the existing method and the proposed method in Star(4) is shown in Table 2. In the existing method, performance remains stable when the read ratio is low but degrades significantly as the read ratio increases. This is because the existing method tends to overestimate update costs in parallel processing environments, leading to an unnecessarily small || and performance degradation in readheavy environments. This overestimation occurs because the existing method only considers communication cost, ignoring cases where updates can be executed concurrently without increasing execution time.
In contrast, the proposed method mitigates performance degradation due to its consideration of parallel execution costs. However, a slight performance decline was still observed, possibly due to the small value, which afects the accuracy of statistical data in the expansion-contraction test. Increasing could improve the accuracy and lead to better performance. The experimental results for Linear(9) and General(10) topologies are shown in Table 3 and Table 4.
In Linear(9), as shown in Table 3, as the read ratio increases, the throughput gap between min || and max || widens, favoring min || . This is because a lower read ratio results in a higher proportion of update transactions, making a smaller || more advantageous. Table 4 shows that both methods achieve performance close to the optimal min || case, demonstrating successful optimization. The reason for the lack of a significant diference between the two methods is that, unlike Star topology, Linear topology has a lower degree of parallelism, which reduces the performance gap between the methods.
In General(10), similar to Linear(9), as shown in Table 3, as the read ratio increases, the throughput gap between min || and max || widens, favoring min || . Additionally, at a 10% read ratio, Table 4 shows that both methods achieve optimal values with no notable diference. At 50% and 90% read ratios, the proposed method achieves higher throughput than the existing method. This result, as in Star topology, is attributed to the consideration of parallel computation and per-processor costs. At a 90% read ratio, the existing method underperforms both min || and max || , while the proposed method surpasses both. This indicates that the ADR algorithm sometimes converges to a worse solution than either min || or max || , whereas the proposed method has the potential to reach an optimal solution that is neither the smallest nor the largest || .
This work is supported by JSPS Kakenhi JP23K17456, JP23K25157, JP23K28096, and JST CREST JPMJCR22M2.