Asymptotic and Constant-Factor Improvements in rsy File Synchronization
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} $$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 |
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.