The rsync algorithm

Modern computers are very powerful. These days, mobile phones are packed with multi core CPUs and even GPUs. Despite these advances in hardware, internet connections in most parts of the world are still surprisingly slow and unreliable. This creates a challenge: how can files be efficiently transferred between computers over a low-bandwidth, high latency network connection? In 1996, Andrew Tridgell and Paul Mackerras developed a simple solution which powers one of the most useful UNIX tools, rsync. The algorithm remains relevant 21 years after its invention because it solves a timeless problem.

This talk will take you step by step through the rsync algorithm. You will learn that PhD theses are not always scary or unapproachable. Hopefully, you will also leave with a better intuition about the inner workings of rsync, as well as ideas for how its principles can be building blocks for solving many other different problems.

Transcript

1. The rsync algorithm By Andrew Tridgell and Paul Mackerras Presented by Camilo Aguilar - @c4milo
3. Motivation
6. South Korea?
7. Designing a remote update algorithm
8. First attempt
9. A B Client Server
10. A B Client Server Sync file…
11. A B Client Server Σ OK Calculating block signatures…
12. A B Client Server Σ Σ Σ Σ Calculating block signatures…
13. A B Client Server Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Calculating block signatures…
14. A B Client Server Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Calculating block signatures…
15. A B Client Server Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Calculating block signatures… Sending block signatures to Client… done
16. A B Client Server Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Calculating block signatures… Sending block signatures to Client… done done
17. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ
18. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Finding differences with B…
19. A B Client Server Σ C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Finding differences with B…
20. A B Client Server Σ Lookup C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Finding differences with B…
21. A B Client Server Σ Match! C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Finding differences with B…
22. A B Client Server Σ Match! C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Finding differences with B…
23. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Finding differences with B…
24. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
25. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
26. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
27. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
28. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
29. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
30. A B Client Server C Σ Lookup Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
31. A B Client Server C Σ Not Found! Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
32. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
33. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
34. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
35. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
36. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… Finding differences with B…
37. A B Client Server C Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Σ Reconstructing C… done Finding differences with B… done
38. First attempt is not enough
39. Second Attempt
40. Solution: two signatures
41. Let’s run through an example
42. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B
43. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B
44. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B
45. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B
46. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B
47. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1
48. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1
49. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 strong: 1c2fb9a8 index: 2 →
50. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2
51. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3
52. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3
53. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3
54. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table
55. Server Block Size Block Match 2 Bytes False Weak 0 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table
56. Server Block Size Block Match 2 Bytes False Weak 13d00d6 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table
57. Server Block Size Block Match 2 Bytes False Weak 13d00d6 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Lookup…
58. Server Block Size Block Match 2 Bytes False Weak 13d00d6 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table ✘
59. Server Block Size Block Match 2 Bytes False Weak 13d00d6 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table ✘
60. Server Block Size Block Match 2 Bytes False Weak 13d00d6 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table
61. Server Block Size Block Match 2 Bytes False Weak 13d00d6 Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table
62. Server Block Size Block Match 2 Bytes False Weak 406019b Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations
63. Server Block Size Block Match 2 Bytes False Weak 406019b Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations Lookup…
64. Server Block Size Block Match 2 Bytes False Weak 406019b Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations ✘
65. Server Block Size Block Match 2 Bytes False Weak 406019b Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations ✘
66. Server Block Size Block Match 2 Bytes False Weak 406019b Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations
67. Server Block Size Block Match 2 Bytes False Weak 406019b Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations
68. Server Block Size Block Match 2 Bytes False Weak 406019b Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations
69. Server Block Size Block Match 2 Bytes False Weak 12e00cb Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations
70. Server Block Size Block Match 2 Bytes False Weak 12e00cb Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations Lookup…
71. Server Block Size Block Match 2 Bytes False Weak 12e00cb Strong EOF False 0 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations ✓
72. Server Block Size Block Match 2 Bytes False Weak 12e00cb Strong EOF False 5982e9e5 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations ✓
73. Server Block Size Block Match 2 Bytes False Weak 12e00cb Strong EOF False 5982e9e5 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations ✓
74. Server Block Size Block Match 2 Bytes False Weak 12e00cb Strong EOF False 5982e9e5 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations ✓ Lookup…
75. Server Block Size Block Match 2 Bytes False Weak 12e00cb Strong EOF False 5982e9e5 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations ✓ ✓
76. Server Block Size Block Match 2 Bytes True Weak 12e00cb Strong EOF False 5982e9e5 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations
77. Server Block Size Block Match 2 Bytes True Weak 12e00cb Strong EOF False 5982e9e5 Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1
78. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 0 0 True
79. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 0 0 True
80. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 13400d3 0 True
81. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 13400d3 0 True Lookup…
82. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 13400d3 0 True ✓
83. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 13400d3 1c2fb9a8 True ✓
84. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 13400d3 1c2fb9a8 True ✓ Lookup…
85. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 13400d3 1c2fb9a8 True ✓ ✓
86. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 13400d3 1c2fb9a8 True
87. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 13400d3 1c2fb9a8 True 2
88. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 0 0 True
89. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 0 0 True
90. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 13900cd 0 True
91. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 13900cd 0 True Lookup…
92. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 13900cd 0 True ✓
93. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 13900cd ab9e1994 True ✓
94. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 13900cd ab9e1994 True ✓ ✓
95. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 13900cd ab9e1994 True ✓ ✓
96. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 13900cd ab9e1994 True
97. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 13900cd ab9e1994 True 3
98. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 True 3 0 0
99. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 True 3 0 0
100. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 True 3 13d00d6 0
101. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 True 3 13d00d6 0
102. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 True 3 13d00d6 0 Lookup…
103. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 True 3 13d00d6 0 ✘
104. Server Block Size Block Match 2 Bytes Weak Strong EOF False Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 False 3 13d00d6 0
105. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 False 3 13d00d6 0
106. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 False 3 13d00d6 0
107. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 False 3 13d00d6 0
108. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 False 3 13d00d6 0 C
109. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 False 3 13d00d6 0 C
110. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 12 False 3 13d00d6 0 C
111. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 2 False 3 13d00d6 0 C
112. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 1 2 False 3 13d00d6 0 C
113. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 2 False 3 13d00d6 0 C
114. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 2 False 3 13d00d6 0 C
115. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations 2 False 3 13d00d6 0 C
116. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations False 3 13d00d6 0 C
117. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations False 3 13d00d6 0 C
118. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations False 3 13d00d6 0 C
119. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table Operations False 13d00d6 0 C
120. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table False 13d00d6 0 C
121. Server Block Size Block Match 2 Bytes Weak Strong EOF True Client A B 12e00cb → strong: 5982e9e5 index: 1 13400d3 → strong: 1c2fb9a8 index: 2 13900cd → strong: ab9e1994 index: 3 Signature table False 13d00d6 0
122. Recap
123. Rolling Checksum
124. Rolling Checksum const ( mod = 1 << 16 ) func rollingHash(block []byte) (uint32, uint32, uint32) { var a, b uint32 l := uint32(len(block)) for index, value := range block { a += uint32(value) b += (l - uint32(index)) * uint32(value) } r1 := a % mod r2 := b % mod r := r1 + (mod * r2) return r1, r2, r }
125. Rolling Checksum const ( mod = 1 << 16 ) func rollingHash(block []byte) (uint32, uint32, uint32) { var a, b uint32 l := uint32(len(block)) for index, value := range block { a += uint32(value) b += (l - uint32(index)) * uint32(value) } r1 := a % mod r2 := b % mod r := r1 + (mod * r2) return r1, r2, r }
126. Rolling Checksum const ( mod = 1 << 16 ) func rollingHash(block []byte) (uint32, uint32, uint32) { var a, b uint32 l := uint32(len(block)) for index, value := range block { a += uint32(value) b += (l - uint32(index)) * uint32(value) } r1 := a % mod r2 := b % mod r := r1 + (mod * r2) return r1, r2, r }
127. Rolling Checksum const ( mod = 1 << 16 ) func rollingHash(block []byte) (uint32, uint32, uint32) { var a, b uint32 l := uint32(len(block)) for index, value := range block { a += uint32(value) b += (l - uint32(index)) * uint32(value) } r1 := a % mod r2 := b % mod r := r1 + (mod * r2) return r1, r2, r }
128. Incremental Rolling Checksum
129. Incremental Rolling Checksum func rollingHash2(l, r1, r2, outgoingValue, incomingValue uint32) (uint32, uint32, uint32) { r1 = (r1 - outgoingValue + incomingValue) % mod r2 = (r2 - (l * outgoingValue) + r1) % mod r := r1 + (mod * r2) return r1, r2, r }
130. Incremental Rolling Checksum func rollingHash2(l, r1, r2, outgoingValue, incomingValue uint32) (uint32, uint32, uint32) { r1 = (r1 - outgoingValue + incomingValue) % mod r2 = (r2 - (l * outgoingValue) + r1) % mod r := r1 + (mod * r2) return r1, r2, r }
131. Incremental Rolling Checksum func rollingHash2(l, r1, r2, outgoingValue, incomingValue uint32) (uint32, uint32, uint32) { r1 = (r1 - outgoingValue + incomingValue) % mod r2 = (r2 - (l * outgoingValue) + r1) % mod r := r1 + (mod * r2) return r1, r2, r }
132. Incremental Rolling Checksum func rollingHash2(l, r1, r2, outgoingValue, incomingValue uint32) (uint32, uint32, uint32) { r1 = (r1 - outgoingValue + incomingValue) % mod r2 = (r2 - (l * outgoingValue) + r1) % mod r := r1 + (mod * r2) return r1, r2, r }
133. The Probability of Failure
134. What could be improved? • Adaptive block size based on file size • Whole file checksum client generation and verification at the server. • Pipelining to sync multiple files in parallel over the same network connection. • Block compression
135. Applications • Online data deduplication • File forensics • Incremental backup systems • Efficient software updates …
136. Main takeaway
137. Thanks! @c4milo Camilo Aguilar
138. Acknowledgments Thanks for all the invaluable feedback on early drafts to: • Catherine Lopez - @lopezcatherine • Elizabeth Ramírez - @eramirem • David Castillo - @castillobgr • Andrew Turley - @casio_juarez • Cameron Yick - @hydrosquall • Juan P. Osorio - @jpoo90
139. Acknowledgments For being so kind with his time answering all my questions about his PhD thesis. Andrew Tridgell
140. References • https://www.samba.org/~tridge/phd_thesis.pdf • https://www.andrew.cmu.edu/course/15-749/READINGS/required/cas/tridgell96.pdf • https://speakerdeck.com/ceejbot/hash-functions-and-you • https://en.wikipedia.org/wiki/Rabin_fingerprint • https://en.wikipedia.org/wiki/Rolling_hash • http://olstrans.sourceforge.net/release/OLS2000-rsync/OLS2000-rsync.html • http://preshing.com/20110504/hash-collision-probabilities/
141. Support Slides
142. Demo • Written in Go • Using gRPC Streaming • LZ4 Compression • Lookup table uses dynamic arrays for chaining • Pipelining possible by using more gRPC streams on the same TCP connection, one per file. • Block size: 6kb • Strong checksum algorithm: xxhash
144. Random Collision Probability
145. Random Collision Probability