Lines Matching refs:a
13 Deleting a range of keys is a common pattern in RocksDB. Most systems built on top of
14 RocksDB have multi-component key schemas, where keys sharing a common prefix are
17 MyRocks is a MySQL fork using RocksDB as its storage engine. Each key's first
19 a table or index involves deleting all the keys with that prefix.
21 Rockssandra is a Cassandra variant that uses RocksDB as its storage engine. One
26 and it stores various data associated with the product in separate keys. When a
29 When we decide what to improve, we try to find a use case that's common across
30 users, since we want to build a generally useful system, not one that has many
32 illustrated above, so from this perspective it's a good target for optimization.
37 through the to-be-deleted range, and issue a `Delete` for each key. This is
39 it creates many tombstones, which slows down iterators and doesn't offer a deadline
42 Another common pattern is using a custom compaction filter that drops keys in
46 because compaction cannot detect whether dropping a key would cause an older
47 version at a lower level to reappear.
62 complicated to reason about and implement. In an ideal world, deleting a range
63 of keys would be (1) simple, i.e., a single API call; (2) synchronous, i.e.,
65 latency so it can be used in critical paths; and (4) a first-class operation
73 We could not think of a good way to do it, however, since the start of a range
74 tombstone covering a key could be anywhere, making binary search impossible.
82 also has no way to detect when a range tombstone no longer covers anything and
83 is droppable. Further, it'd be possible for keys above a range tombstone to disappear
86 A third candidate is using a separate column family. This has similar problems
87 to the manifest approach. That is, we cannot easily detect when a range
88 tombstone is obsolete, and seqnum zeroing can cause a key
89 to go from above a range tombstone to below, i.e., disappearing. The upside is
92 The problems with the second and third solutions indicate a need for range
95 the first solution. So, we introduced a separate meta-block for range tombstones.
98 that newer versions of a key are always in a higher level to prevent the seqnum
100 tombstones seen during reads to ones in a similar key-range.
105 *When there are range tombstones in an SST, they are segregated in a separate meta-block*
117 then applied to a dedicated range tombstone memtable during `Write`. Later in
119 are flushed together into a single SST with a range tombstone meta-block. SSTs
123 We chose to use a dedicated memtable for range tombstones. The memtable
125 case, which is the memtable contains zero or a small number of range tombstones.
126 The range tombstones are segregated to a separate memtable for the same reason
128 interleave the range tombstone with point data in a way that we would be able to
138 tombstones unsorted. Sorting by a single dimension is easy to implement, but
141 However, a couple of concerns cause doing this in flush and compaction to feel
146 side, hoping a good caching strategy could optimize this at some future point.
152 search through live memtable, immutable memtables, and then SSTs. When a key is
153 found that matches the lookup key, we do a scan through the vector, checking
156 In iterators, we aggregate range tombstones into a skyline as we visit live
157 …d SSTs. The skyline is expensive to construct but fast to determine whether a key is covered. The …
171 delete (optionally within a transaction) pattern. `DeleteRange` only logs to WAL
174 Since range tombstones have a dedicated skiplist memtable, the complexity of inserting is O(log(T))…
177 in a database where scan-and-delete has happened, due to the linear scan over
180 Iterating in a database with v1 range tombstones is usually slower than in a
182 When an iterator is first created and seeked, we construct a skyline over its
186 a constant-time operation (excluding edge cases, e.g., many range tombstones
191 `DeleteRange`’s negative impact on read perf is a barrier to its adoption. The
192 root cause is range tombstones are not stored or cached in a format that can be
217 the lookup key. Unlike the old design, once we find a tombstone, we no longer need to
223 tombstones and store them in a list, seeking each one to cover the start key of the range
225 advancing range tombstone iterators as necessary. In effect, we implicitly create a skyline.
228 possibly iterator increments) for several iterators (as opposed to v1, where we had a global
229 collapsed representation of all range tombstones). As a result, very long range scans may become
242 In these benchmarks, we used a database with 5 million data keys, and 10000 range tombstones (ignor…
248 Point lookup benchmarks read 100000 keys from a database using `readwhilewriting`. Range scan bench…
252 different SHAs for v1 benchmarks are due to a new `db_bench` flag that was added in order to compar…
280 after it passes a threshold). In the future, a specialized data structure can be used for storing
283 Another future optimization is to create a new format version that requires range tombstones to
284 …be stored in a fragmented form. This would save time when opening SST files, and when `max_open_fi…