Interleaved deltas

Interleaved deltas is a method used by the Source Code Control System from Marc Rochkind^[1] to store all revisions of a file in a way that makes every revision accessible with the same effort. Interleaved deltas are also known as the weave as all lines from all revisions are "woven" together in a single block of data, with interspersed control instructions indicating which lines are included in which revisions of the file. Interleaved deltas are traditionally implemented with line oriented text files in mind, although nothing prevents the method from being applied to binary files as well.

Implementation in SCCS

In SCCS, the following weave block

 ^AI 1
 ^AD 2
 foo
 ^AE 2
 bar
 ^AI 2
 baz
 ^AE 2
 ^AE 1

represents a file that contains the lines "foo" and "bar" in the first release and the lines "bar" and "baz" in the second revision. The string "^A" denotes a control-A character.

The control lines in the interleaved delta block have the following meaning:^[2]

• ^AI serial Start a block of lines that was inserted with the named serial number.
• ^AD serial Start a block of lines that was removed with the named serial number.
• ^AE serial Block end for a corresponding ^AI or ^AD statement that uses the same serial number.

Advantages

The time it takes to extract any revision from such an interleaved delta block is proportional to the size of the archive. The size of the archive is the sum of the size of all different lines in all revisions.

In order to extract a specific revision, an array of structures needs to be constructed, telling whether a specific block, tagged by a serial number in the interleaved deltas, will be copied to the output or not. The original SCCS implementation needs approx. 100 bytes of storage for each different serial number in the deltas in order to know how to extract a specific revision. A SCCS history file with one million deltas would thus need 100MBytes of virtual memory to unpack. The size could be reduced by approx. 32 bytes per delta if no annotated file retrieval is needed.

The advantages of the weave method are the following:

• Uniform retrieval time for all revisions of a file.
• The possibility to annotate all lines of a file with revision of last change, author of last change and time of last change at no extra costs.
• The possibility to merge in non-overlapping branches at no extra costs.

Software using interleaved deltas

• Source Code Control System
• Sun WorkShop TeamWare
• BitKeeper
• Bazaar intended to use interleaved deltas in the future^[3]

See also

Delta encoding

References