reftable: explicitly store update_index per ref

Add an update_index to every reference in a reftable, storing the
exact transaction that last modified the reference.  This is necessary
to fix some merge race conditions.

Consider updates at T1, T3 are present in two reftables.  Compacting
these will create a table with range [T1,T3].  If T2 arrives during
or after the compaction its impossible for readers to know how to
merge the [T1,T3] table with the T2 table.

With an explicit update_index per reference, MergedReftable is able to
individually sort each reference, merging individual entries at T3
from [T1,T3] ahead of identically named entries appearing in T2.

Change-Id: Ie4065d4176a5a0207dcab9696ae05d086e042140

1 files changed, 5 insertions, 0 deletions

diff --git a/Documentation/technical/reftable.md b/Documentation/technical/reftable.md
index 34f752950d..47c61a350d 100644
--- a/Documentation/technical/reftable.md
+++ b/Documentation/technical/reftable.md
@@ -243,6 +243,7 @@ its value(s). Records are formatted as:
     varint( prefix_length )
     varint( (suffix_length << 3) | value_type )
     suffix
+    varint( update_index_delta )
     value?
 
 The `prefix_length` field specifies how many leading bytes of the
@@ -258,6 +259,10 @@ Recovering a reference name from any `ref_record` is a simple concat:
 The `suffix_length` value provides the number of bytes available in
 `suffix` to copy from `suffix` to complete the reference name.
 
+The `update_index` that last modified the reference can be obtained by
+adding `update_index_delta` to the `min_update_index` from the file
+header: `min_update_index + update_index_delta`.
+
 The `value` follows.  Its format is determined by `value_type`, one of
 the following: