Dear Wiki user, You have subscribed to a wiki page or wiki category on "Subversion Wiki" for change notification.
The "StarDelta" page has been changed by StefanFuhrmann: http://wiki.apache.org/subversion/StarDelta?action=diff&rev1=8&rev2=9 FSFS currently uses xdelta to store different version of the same node efficiently. Basically, we represent node {{attachment:x_i.gif}} as + {{attachment:xdelta_formula.gif}} - x_i = x_i-1 o \delta(x_i, x_i-1) - x_i-1 = x_i-2 o \delta(x_i-1, x_i-2) - ... - x_0 = x_0 and store x_0 plus the incremental \delta information. {{attachment:x_i.gif}} gets reconstructed by starting with x_0 and iteratively applying all deltas. Assuming that size(x_i) is roughly proportional to i and the deltas averaging around some constant value, this approach has the following properties: + {{attachment:xdelta_props.gif}} - storage size(N) = size(x_0) + sum_i=1^N(size(\delta(x_i, x_i-1))) - = O(N) - reconstruction time(N) ~ size(N) + sum_i=1^N(size(x_i))) - = O(N^2) with N being either the size of the node or the number of revisions to it. To mitigate the quadratic runtime behavior, we use skip-deltas: - x_i = x_k + \delta(x_i, x_base(i)) with base(i) being next "rounder" binary + {{attachment:skip_xdelta.gif}} with {{attachment:base_i.gif}} being next "rounder" binary Since we skip intermediate representations, we will repeat the respective change information (approx .5 log N times). Storage size and reconstruction time are now + {{attachment:skip_xdelta_props.gif}} - storage size(N) = size(x_0) + sum_i=1^N(size(\delta(x_i, x_base(i)))) - = O(N log N) - reconstruction time(N) ~ size(N) + sum_log N(size(x_base))) - = O(N log N) Please note that the actual implementation uses a hybrid scheme.
