Mathematical Notes on rsy Transfer Improvements

# Asymptotic and Constant-Factor Improvements in rsy File Synchronization

Pranav Gundu
Technical Note, Version 1.0
Abstract

We present a compact mathematical account of recent implementation changes to rsy, a parallel file synchronization tool. The analysis models traversal, whole-file copying, atomic replacement, and delta synchronization. The primary result is not a change in worst-case computational class, but a reduction in dominant constant factors for common cold-copy and whole-file workloads.

## 1. Model

Let $F$ denote the number of regular files, $D$ the number of directories, $L$ the number of symbolic links, and $B = \sum_{i=1}^{F} b_i$ the total number of bytes in the source corpus. Let $T_{old}$ be the pre-optimization runtime and $T_{new}$ be the optimized runtime. We decompose runtime as

$$ T = T_{walk} + T_{meta} + T_{copy} + T_{delta} + T_{verify} + T_{ui}. \tag{1} $$

For a cold synchronization, no destination basis exists for most files, so

$$ T_{delta} \approx 0, \qquad T_{copy} \gg T_{walk} + T_{meta}. \tag{2} $$

## 2. Traversal Improvement

The previous file-list construction performed one name-order traversal and then a final deterministic sort. This is modeled by

$$ T_{walk}^{old}(N) = c_w N + c_s N\log N + c_p N + c_s' N\log N, \tag{3} $$

where $N = F + D + L$, $c_s N\log N$ is the traversal-level sort, and $c_s' N\log N$ is the final sort. After removing the redundant traversal sort,

$$ T_{walk}^{new}(N) = c_w N + c_p N + c_s' N\log N. \tag{4} $$

Hence the direct improvement is

$$ \Delta T_{walk}(N) = T_{walk}^{old}(N) - T_{walk}^{new}(N) = c_s N\log N. \tag{5} $$
Proposition 1. For any corpus with $N > 1$, removing one full ordering pass yields a strictly positive traversal saving proportional to $N\log N$. $$ \forall N > 1,\quad \Delta T_{walk}(N) = c_s N\log N > 0. \tag{6} $$

## 3. Cold-Copy Path

For a new file of size $b_i$, the former path created a temporary file, copied bytes through userspace, flushed, and renamed. A simplified model is

$$ T_{copy,i}^{old} = \alpha_{open} + \alpha_{tmp} + \alpha_{rw} b_i + \alpha_{flush} + \alpha_{rename} + \alpha_{mtime}. \tag{7} $$

The new cold-file path copies directly with the platform copy primitive:

$$ T_{copy,i}^{new} = \beta_{copy} b_i + \beta_{open} + \beta_{mtime}. \tag{8} $$

Summing over all cold files gives

$$ T_{copy}^{old} = \sum_{i=1}^{F} \left(\alpha_{open} + \alpha_{tmp} + \alpha_{rw} b_i + \alpha_{flush} + \alpha_{rename} + \alpha_{mtime}\right), \tag{9} $$ $$ T_{copy}^{new} = \sum_{i=1}^{F} \left(\beta_{copy} b_i + \beta_{open} + \beta_{mtime}\right). \tag{10} $$

The expected speedup factor for cold copies is therefore

$$ S_{cold} = \frac{T_{copy}^{old}}{T_{copy}^{new}} = \frac{F(\alpha_{open}+\alpha_{tmp}+\alpha_{flush}+\alpha_{rename}+\alpha_{mtime}) + \alpha_{rw}B} {F(\beta_{open}+\beta_{mtime}) + \beta_{copy}B}. \tag{11} $$

## 4. Whole-File Fast Path

In whole-file mode, the old execution could still enter read or mapping setup before concluding that no delta computation was needed. Let $m_i$ represent mmap setup cost and $r_i$ represent avoidable read-preparation cost. Then

$$ T_{whole,i}^{old} = m_i + r_i + T_{copy,i}^{atomic}, \tag{12} $$

while the optimized path is

$$ T_{whole,i}^{new} = T_{copy,i}^{atomic}. \tag{13} $$

Thus the removed overhead is

$$ \Delta T_{whole} = \sum_{i=1}^{F}(m_i + r_i). \tag{14} $$

## 5. Delta Synchronization

For modified files with an existing basis, rsy uses a rolling weak checksum and a strong checksum. Let block size be $q$, number of blocks be $K = \lceil b/q\rceil$, and source length be $b$. Basis summarization is

$$ T_{sum}(b,q) = \gamma_1 Kq + \gamma_2 K = \gamma_1 b + \gamma_2\left\lceil\frac{b}{q}\right\rceil. \tag{15} $$

Rolling search is approximately linear in source bytes:

$$ T_{roll}(b,q) = \rho b + \sigma M, \tag{16} $$

where $M$ is the number of candidate strong-check verifications. With a hash table of weak sums,

$$ \mathbb{E}[M] = \sum_{j=1}^{b-q+1}\Pr[h_w(x_j) \in H] \approx \frac{(b-q+1)K}{2^{32}}. \tag{17} $$

The total delta cost is therefore

$$ T_{delta}(b,q) = \gamma_1 b + \gamma_2\left\lceil\frac{b}{q}\right\rceil + \rho b + \sigma\frac{(b-q+1)}{2^{32}}\left\lceil\frac{b}{q}\right\rceil. \tag{18} $$

## 6. Safety-Preserving Dry Run

A dry run should approximate the planning phase without applying filesystem mutations. Let $\mathcal{M}$ be the set of mutating operations:

$$ \mathcal{M} = \{ mkdir, symlink, unlink, rmdir, write, rename, chmod, chown, utime \}. \tag{19} $$

The desired dry-run property is

$$ dry\_run = 1 \implies \forall m \in \mathcal{M},\; count(m)=0. \tag{20} $$

The implementation now excludes directory creation, symlink creation, and delete operations from dry-run execution, moving the local behavior closer to (20).

## 7. Summary Table

Component | Old Cost | New Cost | Saving
--- | --- | --- | ---
Traversal sort | $c_sN\log N + c_s'N\log N$ | $c_s'N\log N$ | $c_sN\log N$
New-file copy | $\alpha_{rw}B + O(F)$ | $\beta_{copy}B + O(F)$ | $(\alpha_{rw}-\beta_{copy})B + O(F)$
Whole-file mode | $T_{copy}+\sum(m_i+r_i)$ | $T_{copy}$ | $\sum(m_i+r_i)$
Dry run | $count(\mathcal{M}) \ge 0$ | $count(\mathcal{M}) \to 0$ | Safety improvement
Table 1. Simplified cost comparison of the optimized implementation.

## 8. Conclusion

The revised implementation preserves the same high-level asymptotic behavior for synchronization while removing redundant ordering work and reducing copy-path overhead. In the common cold-copy regime, the practical improvement is governed by Equation (11). In whole-file mode, the improvement is the eliminated setup term in Equation (14). These changes favor large corpora, many-file workloads, and cases where filesystem copy primitives outperform manual userspace copying.