[
https://issues.apache.org/jira/browse/HDDS-16250?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Siyao Meng updated HDDS-16250:
------------------------------
Description:
h3. Problem
{{RDBStoreByteArrayIterator}} and {{RDBStoreCodecBufferIterator}} currently
position their native RocksDB iterator at the table or prefix start during
construction. Many callers immediately reposition the iterator with
{{seek(startKey)}} or {{seek(continuationKey)}}.
These callers perform two native RocksDB positioning operations:
# seek to the table or prefix start during iterator construction;
# seek to the caller's requested key.
The first seek is redundant. It can be expensive when it crosses a large run of
uncompacted tombstones, even when the requested start or continuation key is
beyond that region.
{{RDBTable#getRangeKVs}} also constructs and positions an iterator for some
exact single-entry requests. When the caller requests one known start key
without a filter, ordered iteration is unnecessary.
This is a performance issue. No incorrect results or metadata corruption have
been identified.
h3. Proposed change
* Continue creating the native RocksDB iterator immediately, preserving its
existing database view and lifetime.
* Defer the initial table-start or prefix positioning until ordinary iteration
begins.
* Make an explicit {{seek()}}, {{seekToFirst()}}, or {{seekToLast()}} the only
positioning operation when it is the caller's first iterator operation.
* Preserve current behavior for callers that begin with {{hasNext()}},
{{next()}}, or {{removeFromDB()}} by positioning them at the table or prefix
start on first use.
* Apply the behavior in {{RDBStoreAbstractIterator}} so that the byte-array and
{{CodecBuffer}} implementations remain consistent.
* Use a RocksDB point Get in {{RDBTable#getRangeKVs}} only when:
** {{startKey}} is non-null;
** {{count}} is exactly one;
** no key filter is present;
** the range contract requires the exact start key to exist; and
** the start key belongs to the requested prefix.
* Retain ordered iteration for prefix-boundary, filtered, multi-entry, and
other range requests.
RocksDB requires an iterator to be positioned before reading an entry or
calling {{next()}}, but it does not require {{seekToFirst()}} before
{{seek(target)}}. A direct {{seek(target)}} on a newly created iterator is a
complete positioning operation.
The change does not modify any public API, wire format, RocksDB schema, or
metadata layout.
h3. Expected benefit
The change eliminates one native RocksDB positioning operation whenever a
caller creates an iterator and immediately seeks elsewhere. The absolute
latency reduction equals the cost of the eliminated table-start or prefix seek.
Expected production beneficiaries include:
* {{listKeys}} and S3 {{ListObjects}}
** OM creates a full key-table iterator and then seeks to the requested bucket,
prefix, or continuation marker.
** The first page benefits when the target bucket sorts after a tombstone-heavy
region near the beginning of the table.
** Later pages benefit when the continuation marker is beyond tombstones left
by deleted keys in the bucket.
* OzoneFS {{listStatus}}
** FSO listing creates prefix iterators for the directory and file tables and
may seek them to a later start key.
** Paginated directory listings can eliminate one redundant seek from each
affected table iterator.
** The largest benefit is expected after bulk deletion, rename, or
temporary-directory cleanup.
** LEGACY and OBJECT_STORE listing use a full key-table iterator followed by a
start-key seek and receive the same optimization.
* {{listOpenFiles}}
** OM creates a full open-key-table iterator and then seeks to the requested
path or continuation token.
** Listings avoid an initial traversal over tombstones left by completed,
expired, or recovered open keys.
* {{ListMultipartUploads}}
** OM creates a bucket-prefix iterator and then seeks to the key and upload-ID
marker.
** Later pages avoid an initial prefix seek through tombstones left by
completed or aborted multipart uploads.
* Key lifecycle scans
** A resumed scan can seek directly to its saved last-scanned key without first
positioning at the bucket or directory prefix.
** This improves background scan progress after suspension, restart, or
leadership transfer.
* Snapshot and Recon pagination
** Snapshot listings, pending-deletion endpoints, OM DB insight endpoints, and
other table queries using start or previous-key markers eliminate the same
redundant positioning operation.
A local synthetic benchmark used RocksDB 10.10.1.1, a warm cache, one thread,
disabled automatic compaction, and consecutive point tombstones before a live
target.
When the requested continuation key was beyond the tombstone band:
|| Tombstones || Before || After || Iterator-positioning speedup ||
| 10,000 | 863 microseconds | 1.1 microseconds | approximately 767x |
| 100,000 | 8.76 ms | 1.1 microseconds | approximately 8,000x |
| 500,000 | 97.3 ms | 1.3 microseconds | approximately 77,800x |
These figures isolate iterator positioning. They are not expected end-to-end
RPC speedups.
For example, the 100,000-tombstone case removes approximately 8.76 ms from each
affected iterator. If a {{listKeys}} request also spends 10 ms on cache
merging, decoding, and RPC processing, its approximate total would change from
18.76 ms to 10 ms, or about 1.9x. An FSO {{listStatus}} request can use both
directory-table and file-table iterators, so savings can accumulate when both
tables have a similar tombstone distribution.
When the initial and requested seeks both cross the same tombstone region, the
change removes one of two similarly expensive seeks:
|| Tombstones || Before || After || Iterator-positioning speedup ||
| 10,000 | 1.72 ms | 0.87 ms | approximately 2x |
| 100,000 | 17.3 ms | 8.7 ms | approximately 2x |
| 500,000 | 196 ms | 98 ms | approximately 2x |
Exact count-one {{getRangeKVs}} requests were approximately 3x faster at the
method level with a warm cache, saving roughly 1-2 microseconds per call by
avoiding iterator creation and positioning.
Little or no improvement is expected when:
* tables are already compacted;
* tombstone counts are low;
* callers iterate from the beginning without a later explicit seek; or
* result decoding, cache processing, storage I/O, or RPC work dominates the
request.
was:
h3. Problem
{{RDBStoreByteArrayIterator}} and {{RDBStoreCodecBufferIterator}} currently
position their native RocksDB iterator at the table or prefix start during
construction. Many callers immediately reposition the iterator with
{{seek(startKey)}} or {{seek(continuationKey)}}.
These callers perform two native RocksDB positioning operations:
# seek to the table or prefix start during iterator construction;
# seek to the caller's requested key.
The first seek is redundant. It can be expensive when it crosses a large run of
uncompacted tombstones, even when the requested start or continuation key is
beyond that region.
{{RDBTable#getRangeKVs}} also constructs and positions an iterator for some
exact single-entry requests. When the caller requests one known start key
without a filter, ordered iteration is unnecessary.
This is a performance issue. No incorrect results or metadata corruption have
been identified.
h3. Proposed change
* Continue creating the native RocksDB iterator immediately, preserving its
existing database view and lifetime.
* Defer the initial table-start or prefix positioning until ordinary iteration
begins.
* Make an explicit {{seek()}}, {{seekToFirst()}}, or {{seekToLast()}} the only
positioning operation when it is the caller's first iterator operation.
* Preserve current behavior for callers that begin with {{hasNext()}},
{{next()}}, or {{removeFromDB()}} by positioning them at the table or prefix
start on first use.
* Apply the behavior in {{RDBStoreAbstractIterator}} so that the byte-array and
{{CodecBuffer}} implementations remain consistent.
* Use a RocksDB point Get in {{RDBTable#getRangeKVs}} only when:
** {{startKey}} is non-null;
** {{count}} is exactly one;
** no key filter is present;
** the range contract requires the exact start key to exist; and
** the start key belongs to the requested prefix.
* Retain ordered iteration for prefix-boundary, filtered, multi-entry, and
other range requests.
RocksDB requires an iterator to be positioned before reading an entry or
calling {{next()}}, but it does not require {{seekToFirst()}} before
{{seek(target)}}. A direct {{seek(target)}} on a newly created iterator is a
complete positioning operation.
The change does not modify any public API, wire format, RocksDB schema, or
metadata layout.
h3. Expected benefit
The change eliminates one native RocksDB positioning operation whenever a
caller creates an iterator and immediately seeks elsewhere. The absolute
latency reduction equals the cost of the eliminated table-start or prefix seek.
Expected production beneficiaries include:
* {{listKeys}} and S3 {{ListObjects}}
** OM creates a full key-table iterator and then seeks to the requested bucket,
prefix, or continuation marker.
** The first page benefits when the target bucket sorts after a tombstone-heavy
region near the beginning of the table.
** Later pages benefit when the continuation marker is beyond tombstones left
by deleted keys in the bucket.
* OzoneFS {{listStatus}}
** FSO listing creates prefix iterators for the directory and file tables and
may seek them to a later start key.
** Paginated directory listings can eliminate one redundant seek from each
affected table iterator.
** The largest benefit is expected after bulk deletion, rename, or
temporary-directory cleanup.
** LEGACY and OBJECT_STORE listing use a full key-table iterator followed by a
start-key seek and receive the same optimization.
* {{listOpenFiles}}
** OM creates a full open-key-table iterator and then seeks to the requested
path or continuation token.
** Listings avoid an initial traversal over tombstones left by completed,
expired, or recovered open keys.
* {{ListMultipartUploads}}
** OM creates a bucket-prefix iterator and then seeks to the key and upload-ID
marker.
** Later pages avoid an initial prefix seek through tombstones left by
completed or aborted multipart uploads.
* Key lifecycle scans
** A resumed scan can seek directly to its saved last-scanned key without first
positioning at the bucket or directory prefix.
** This improves background scan progress after suspension, restart, or
leadership transfer.
* Snapshot and Recon pagination
** Snapshot listings, pending-deletion endpoints, OM DB insight endpoints, and
other table queries using start or previous-key markers eliminate the same
redundant positioning operation.
A local synthetic benchmark used RocksDB 10.10.1.1, a warm cache, one thread,
disabled automatic compaction, and consecutive point tombstones before a live
target.
When the requested continuation key was beyond the tombstone band:
|| Tombstones || Before || After || Iterator-positioning speedup ||
| 10,000 | 863 microseconds | 1.1 microseconds | approximately 767x |
| 100,000 | 8.76 ms | 1.1 microseconds | approximately 8,000x |
| 500,000 | 97.3 ms | 1.3 microseconds | approximately 77,800x |
These figures isolate iterator positioning. They are not expected end-to-end
RPC speedups.
For example, the 100,000-tombstone case removes approximately 8.76 ms from each
affected iterator. If a {{listKeys}} request also spends 10 ms on cache
merging, decoding, and RPC processing, its approximate total would change from
18.76 ms to 10 ms, or about 1.9x. An FSO {{listStatus}} request can use both
directory-table and file-table iterators, so savings can accumulate when both
tables have a similar tombstone distribution.
When the initial and requested seeks both cross the same tombstone region, the
change removes one of two similarly expensive seeks:
|| Tombstones || Before || After || Iterator-positioning speedup ||
| 10,000 | 1.72 ms | 0.87 ms | approximately 2x |
| 100,000 | 17.3 ms | 8.7 ms | approximately 2x |
| 500,000 | 196 ms | 98 ms | approximately 2x |
Exact count-one {{getRangeKVs}} requests were approximately 3x faster at the
method level with a warm cache, saving roughly 1-2 microseconds per call by
avoiding iterator creation and positioning.
Little or no improvement is expected when:
* tables are already compacted;
* tombstone counts are low;
* callers iterate from the beginning without a later explicit seek; or
* result decoding, cache processing, storage I/O, or RPC work dominates the
request.
h3. Regression coverage
Tests verify that:
* constructing an iterator performs no native seek;
* {{hasNext()}} and direct {{next()}} still initialize at the table or prefix
beginning;
* repeated {{hasNext()}} calls do not repeat initialization;
* an explicit seek on a prefixed iterator performs exactly one native seek;
* {{seekToLast()}} does not first seek to the beginning;
* {{removeFromDB()}} preserves its implicit-start behavior;
* byte-array and {{CodecBuffer}} iterators have the same behavior;
* present and absent exact count-one ranges use a point Get without creating an
iterator;
* a returned key does not alias the caller's start-key array;
* a start key equal to the prefix retains lower-bound range semantics;
* filtered requests continue iterating until a matching key is found;
* multi-entry and out-of-prefix requests retain ordered-range semantics.
A wall-clock performance assertion is intentionally not included in the unit
suite because its result would depend on RocksDB compaction state, cache
temperature, storage, and host timing. Deterministic tests instead verify the
number and order of native positioning calls.
h3. Validation
* Targeted {{hdds-server-framework}} tests:
** 52 tests passed;
** 0 failures;
** 0 errors.
* Broader {{hdds-server-framework}} suite, excluding the independently
reproducible {{TestDU}} macOS baseline failure:
** 598 tests passed;
** 0 failures;
** 0 errors;
** 1 skipped.
* Repository-wide checkstyle:
** all 58 modules passed.
> Improve RocksDB read performance by reducing unnecessary iterator positioning
> -----------------------------------------------------------------------------
>
> Key: HDDS-16250
> URL: https://issues.apache.org/jira/browse/HDDS-16250
> Project: Apache Ozone
> Issue Type: Improvement
> Reporter: Siyao Meng
> Assignee: Siyao Meng
> Priority: Major
>
> h3. Problem
> {{RDBStoreByteArrayIterator}} and {{RDBStoreCodecBufferIterator}} currently
> position their native RocksDB iterator at the table or prefix start during
> construction. Many callers immediately reposition the iterator with
> {{seek(startKey)}} or {{seek(continuationKey)}}.
> These callers perform two native RocksDB positioning operations:
> # seek to the table or prefix start during iterator construction;
> # seek to the caller's requested key.
> The first seek is redundant. It can be expensive when it crosses a large run
> of uncompacted tombstones, even when the requested start or continuation key
> is beyond that region.
> {{RDBTable#getRangeKVs}} also constructs and positions an iterator for some
> exact single-entry requests. When the caller requests one known start key
> without a filter, ordered iteration is unnecessary.
> This is a performance issue. No incorrect results or metadata corruption have
> been identified.
> h3. Proposed change
> * Continue creating the native RocksDB iterator immediately, preserving its
> existing database view and lifetime.
> * Defer the initial table-start or prefix positioning until ordinary
> iteration begins.
> * Make an explicit {{seek()}}, {{seekToFirst()}}, or {{seekToLast()}} the
> only positioning operation when it is the caller's first iterator operation.
> * Preserve current behavior for callers that begin with {{hasNext()}},
> {{next()}}, or {{removeFromDB()}} by positioning them at the table or prefix
> start on first use.
> * Apply the behavior in {{RDBStoreAbstractIterator}} so that the byte-array
> and {{CodecBuffer}} implementations remain consistent.
> * Use a RocksDB point Get in {{RDBTable#getRangeKVs}} only when:
> ** {{startKey}} is non-null;
> ** {{count}} is exactly one;
> ** no key filter is present;
> ** the range contract requires the exact start key to exist; and
> ** the start key belongs to the requested prefix.
> * Retain ordered iteration for prefix-boundary, filtered, multi-entry, and
> other range requests.
> RocksDB requires an iterator to be positioned before reading an entry or
> calling {{next()}}, but it does not require {{seekToFirst()}} before
> {{seek(target)}}. A direct {{seek(target)}} on a newly created iterator is a
> complete positioning operation.
> The change does not modify any public API, wire format, RocksDB schema, or
> metadata layout.
> h3. Expected benefit
> The change eliminates one native RocksDB positioning operation whenever a
> caller creates an iterator and immediately seeks elsewhere. The absolute
> latency reduction equals the cost of the eliminated table-start or prefix
> seek.
> Expected production beneficiaries include:
> * {{listKeys}} and S3 {{ListObjects}}
> ** OM creates a full key-table iterator and then seeks to the requested
> bucket, prefix, or continuation marker.
> ** The first page benefits when the target bucket sorts after a
> tombstone-heavy region near the beginning of the table.
> ** Later pages benefit when the continuation marker is beyond tombstones left
> by deleted keys in the bucket.
> * OzoneFS {{listStatus}}
> ** FSO listing creates prefix iterators for the directory and file tables and
> may seek them to a later start key.
> ** Paginated directory listings can eliminate one redundant seek from each
> affected table iterator.
> ** The largest benefit is expected after bulk deletion, rename, or
> temporary-directory cleanup.
> ** LEGACY and OBJECT_STORE listing use a full key-table iterator followed by
> a start-key seek and receive the same optimization.
> * {{listOpenFiles}}
> ** OM creates a full open-key-table iterator and then seeks to the requested
> path or continuation token.
> ** Listings avoid an initial traversal over tombstones left by completed,
> expired, or recovered open keys.
> * {{ListMultipartUploads}}
> ** OM creates a bucket-prefix iterator and then seeks to the key and
> upload-ID marker.
> ** Later pages avoid an initial prefix seek through tombstones left by
> completed or aborted multipart uploads.
> * Key lifecycle scans
> ** A resumed scan can seek directly to its saved last-scanned key without
> first positioning at the bucket or directory prefix.
> ** This improves background scan progress after suspension, restart, or
> leadership transfer.
> * Snapshot and Recon pagination
> ** Snapshot listings, pending-deletion endpoints, OM DB insight endpoints,
> and other table queries using start or previous-key markers eliminate the
> same redundant positioning operation.
> A local synthetic benchmark used RocksDB 10.10.1.1, a warm cache, one thread,
> disabled automatic compaction, and consecutive point tombstones before a live
> target.
> When the requested continuation key was beyond the tombstone band:
> || Tombstones || Before || After || Iterator-positioning speedup ||
> | 10,000 | 863 microseconds | 1.1 microseconds | approximately 767x |
> | 100,000 | 8.76 ms | 1.1 microseconds | approximately 8,000x |
> | 500,000 | 97.3 ms | 1.3 microseconds | approximately 77,800x |
> These figures isolate iterator positioning. They are not expected end-to-end
> RPC speedups.
> For example, the 100,000-tombstone case removes approximately 8.76 ms from
> each affected iterator. If a {{listKeys}} request also spends 10 ms on cache
> merging, decoding, and RPC processing, its approximate total would change
> from 18.76 ms to 10 ms, or about 1.9x. An FSO {{listStatus}} request can use
> both directory-table and file-table iterators, so savings can accumulate when
> both tables have a similar tombstone distribution.
> When the initial and requested seeks both cross the same tombstone region,
> the change removes one of two similarly expensive seeks:
> || Tombstones || Before || After || Iterator-positioning speedup ||
> | 10,000 | 1.72 ms | 0.87 ms | approximately 2x |
> | 100,000 | 17.3 ms | 8.7 ms | approximately 2x |
> | 500,000 | 196 ms | 98 ms | approximately 2x |
> Exact count-one {{getRangeKVs}} requests were approximately 3x faster at the
> method level with a warm cache, saving roughly 1-2 microseconds per call by
> avoiding iterator creation and positioning.
> Little or no improvement is expected when:
> * tables are already compacted;
> * tombstone counts are low;
> * callers iterate from the beginning without a later explicit seek; or
> * result decoding, cache processing, storage I/O, or RPC work dominates the
> request.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
