Revision 6fbe96baf8a4539d800e7c124ca85443a0ca7876 authored by Andrew Kryczka on 18 October 2016, 19:04:56 UTC, committed by Andrew Kryczka on 18 October 2016, 19:04:56 UTC
Summary:
This diff introduces RangeDelAggregator, which takes ownership of iterators
provided to it via AddTombstones(). The tombstones are organized in a two-level
map (snapshot stripe -> begin key -> tombstone). Tombstone creation avoids data
copy by holding Slices returned by the iterator, which remain valid thanks to pinning.

For compaction, we create a hierarchical range tombstone iterator with structure
matching the iterator over compaction input data. An aggregator based on that
iterator is used by CompactionIterator to determine which keys are covered by
range tombstones. In case of merge operand, the same aggregator is used by
MergeHelper. Upon finishing each file in the compaction, relevant range tombstones
are added to the output file's range tombstone metablock and file boundaries are
updated accordingly.

To check whether a key is covered by range tombstone, RangeDelAggregator::ShouldDelete()
considers tombstones in the key's snapshot stripe. When this function is used outside of
compaction, it also checks newer stripes, which can contain covering tombstones. Currently
the intra-stripe check involves a linear scan; however, in the future we plan to collapse ranges
within a stripe such that binary search can be used.

RangeDelAggregator::AddToBuilder() adds all range tombstones in the table's key-range
to a new table's range tombstone meta-block. Since range tombstones may fall in the gap
between files, we may need to extend some files' key-ranges. The strategy is (1) first file
extends as far left as possible and other files do not extend left, (2) all files extend right
until either the start of the next file or the end of the last range tombstone in the gap,
whichever comes first.

One other notable change is adding release/move semantics to ScopedArenaIterator
such that it can be used to transfer ownership of an arena-allocated iterator, similar to
how unique_ptr is used for malloc'd data.

Depends on D61473

Test Plan: compaction_iterator_test, mock_table, end-to-end tests in D63927

Reviewers: sdong, IslamAbdelRahman, wanning, yhchiang, lightmark

Reviewed By: lightmark

Subscribers: andrewkr, dhruba, leveldb

Differential Revision: https://reviews.facebook.net/D62205
1 parent 257de78
History
File Mode Size
arcanist_util
build_tools
cmake
coverage
db
docs
examples
hdfs
include
java
memtable
port
table
third-party
tools
util
utilities
.arcconfig -rw-r--r-- 564 bytes
.clang-format -rw-r--r-- 138 bytes
.gitignore -rw-r--r-- 680 bytes
.travis.yml -rw-r--r-- 1.5 KB
AUTHORS -rw-r--r-- 247 bytes
CMakeLists.txt -rw-r--r-- 23.4 KB
CONTRIBUTING.md -rw-r--r-- 733 bytes
DEFAULT_OPTIONS_HISTORY.md -rw-r--r-- 1.1 KB
DUMP_FORMAT.md -rw-r--r-- 763 bytes
HISTORY.md -rw-r--r-- 36.8 KB
INSTALL.md -rw-r--r-- 3.9 KB
LANGUAGE-BINDINGS.md -rw-r--r-- 646 bytes
LICENSE -rw-r--r-- 1.6 KB
Makefile -rw-r--r-- 48.7 KB
PATENTS -rw-r--r-- 1.9 KB
README.md -rw-r--r-- 1.4 KB
ROCKSDB_LITE.md -rw-r--r-- 1.0 KB
USERS.md -rw-r--r-- 4.5 KB
Vagrantfile -rw-r--r-- 862 bytes
WINDOWS_PORT.md -rw-r--r-- 12.5 KB
appveyor.yml -rw-r--r-- 555 bytes
src.mk -rw-r--r-- 23.6 KB
thirdparty.inc -rw-r--r-- 7.8 KB

README.md

back to top