Ip-rsync runs out of space when the size of the buffered commands exceed the available space. Although buffered commands are much smaller than the original data, the algorithm must gracefully handle cases in which the buffered commands exhaust the available storage. This problem arises frequently when synchronizing block storage devices that may be orders of magnitude larger than a system's memory.
There is no trivial way to address buffer overflow by pruning the buffered commands and the graph they induce, nor by completing some commands early. Ip-rsync must retain all commands until the encoding is complete. Otherwise, if the algorithm were to discard a command, then dependencies between the discarded and subsequent commands remain undetected. Undetected dependencies cause an incomplete ordering and corrupt data.
We have designed, but not implemented, an overlapped windowing technique to address buffer overflow that organizes a file into multiple regions each of which are processed independently. It is an on-line process in which variable sized independent windows are created as ip-rsync approaches its memory limit. The read regions of the windows may overlap, but the write regions are disjoint.
During synchronization, the ip-rsync sender encodes data in an active window, which it uses until it exhausts memory. The active window has a start offset and goes to the highest byte in the file. When ip-rsync does not reach the memory limit, synchronization completes in a single window. When the memory limit is reached, the sender stops encoding data and completes processing on the buffered commands, i.e., commands are topologically sorted and sent to the receiver where they are applied. The buffered commands are discarded and processing begins in the next window, starting at the first un-encoded byte.
Ip-rsync defines independent windows based on read/write dependency information. The algorithm encodes commands that read data in the active window only.
Windowing can be expressed equivalently as rewriting the dependency graph used by ip-rsync. When the graph becomes too large, the buffered graph is rewritten as a single node that writes data to the region starting at offset 0 and ending at the highest encoded offset. Furthermore, the algorithm cannot reorder this rewritten node with respect to the subsequent commands, because the command that the node represents has already been completed.
The implementation of windowing offers an opportunity to further parallelize ip-rsync. Our current windowing design (described above) minimizes compression loss by transferring as much of the file as possible in a single window; frequently this means the whole file when memory is not exhausted. We have identified two alternative windowing designs that increase parallelism in exchange for compression. One design partitions the files into fixed-size windows before scanning. Then, ip-rsync operates on each window independently, treating each window as a separate pair of files and overlapping transfer between windows. This approach does degrade compression, because blocks that match in different windows cannot be encoded. Another design for large files implements two active windows that are sized dynamically. One at the front of the file and one at the end of the file. This allows two processes to execute concurrently on the same file. When the algorithm exhausts memory, one window (or both windows) are completed to reclaim space. The algorithm completes when the windows collide in the middle of the file. An experimental comparison of different windowing policies will help us understand compression versus parallelism tradeoffs in large files.
Overlapped windowing is somewhat similar to the windowing technique used in delta compression [8], in which files are partitioned into non-overlapping regions. Delta compression defines codeword formats for windows, but does not specify how they are constructed or evaluated. Overlapping windowing differs from the rolling window techniques commonly used in data compression. The ``Lempel-Ziv'' family of algorithms uses a fixed-sized buffer, discarding the oldest strings, in order to bound the amount of space used by the string library. Rolling windows create a compression versus memory tradeoff -- there are no correctness implications and the file is not ``partitioned''.