[
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.
HDDS-8655 identified the redundant initial seek in the narrower OBS
{{listKeys}} path. This issue addresses the root cause in the shared DB
iterator layer, covers both raw iterator implementations, and includes a
separate exact count-one {{getRangeKVs}} optimization.
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;
** {{prefix}} is null, or {{startKey}} is longer than {{prefix}} (so {{startKey
== prefix}} retains lower-bound range semantics); and
** {{startKey}} starts with {{prefix}} when a prefix is supplied.
* 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 (M5 Pro, macOS 26.6.2) 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 780x |
| 100,000 | 8.76 ms | 1.1 microseconds | approximately 8,000x |
| 500,000 | 97.3 ms | 1.3 microseconds | approximately 75,000x |
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. No prominent production path was
found that consistently satisfies every fast-path condition, so this is
primarily a method-level improvement unless callers issue exact one-entry range
requests.
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 (M5 Pro, macOS 26.6.2) 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.
> 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
> Components: db
> 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.
> HDDS-8655 identified the redundant initial seek in the narrower OBS
> {{listKeys}} path. This issue addresses the root cause in the shared DB
> iterator layer, covers both raw iterator implementations, and includes a
> separate exact count-one {{getRangeKVs}} optimization.
> 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;
> ** {{prefix}} is null, or {{startKey}} is longer than {{prefix}} (so
> {{startKey == prefix}} retains lower-bound range semantics); and
> ** {{startKey}} starts with {{prefix}} when a prefix is supplied.
> * 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 (M5 Pro, macOS 26.6.2) 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 780x |
> | 100,000 | 8.76 ms | 1.1 microseconds | approximately 8,000x |
> | 500,000 | 97.3 ms | 1.3 microseconds | approximately 75,000x |
> 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. No prominent production path was
> found that consistently satisfies every fast-path condition, so this is
> primarily a method-level improvement unless callers issue exact one-entry
> range requests.
> 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]
