MB-24244: Prevent duplicate items in an inMemoryBackfill 14/78014/9
authorJames Harrison <00jamesh@gmail.com>
Tue, 9 May 2017 11:07:40 +0000 (12:07 +0100)
committerDave Rigby <daver@couchbase.com>
Mon, 15 May 2017 17:10:59 +0000 (17:10 +0000)
commit004652b7addb599c34a0a13b4a4353df4de55a6a
tree3bba5b45508bde4838a23c9f3a576f04cc444e88
parentdd742177b65f93ee804f514d07ddc52597309604
MB-24244: Prevent duplicate items in an inMemoryBackfill

Have rangeRead ignore stale items if their replacement also appears in
the requested range, for example

 A₁  B₂  C₃           Initial items
[A₁  B₂  C₃]          rangeRead 1-3
[A₁  B₂  C₃] B₄       Update B
 A₁  B₂  C₃  B₄       RR ends
[A₁  B₂  C₃  B₄]      new RR 1-4, B₂ should be ignored because B₄ is
also in the snapshot
[A₁  B₂  C₃  B₄] B₅   Another update, but B₄ must still be sent as B₅ is
not in the range
 A₁  B₂  C₃  B₄  B₅   RR ends

To achieve this, when marking items as stale, we store in it a pointer
to its replacement. To avoid bloating the OSV, we reuse the UniquePtr
which points to the items successor when in the HashTable. Once the item
is stale, it will never be used for that purpose again, leaving it free
for reuse.

This is a basic solution. It would be better to not have to take the
writeLock, but improvements of that form will be done in a separate
patch.

Change-Id: Id743da606e009d17f5e5af6f9344223a95aa4a38
Reviewed-on: http://review.couchbase.org/78014
Reviewed-by: Dave Rigby <daver@couchbase.com>
Tested-by: Build Bot <build@couchbase.com>
src/ephemeral_tombstone_purger.cc
src/ephemeral_vb.cc
src/hash_table.cc
src/hash_table.h
src/linked_list.cc
src/linked_list.h
src/seqlist.h
src/stored-value.h
tests/module_tests/basic_ll_test.cc
tests/module_tests/ephemeral_vb_test.cc
tests/module_tests/vbucket_test.cc