[ https://issues.apache.org/jira/browse/HBASE-28043?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17775901#comment-17775901 ]
Becker Ewing commented on HBASE-28043: -------------------------------------- I've done some benchmarking with the "hbase pe" tool to test whether 1-row reverse scans—specifically those done for meta lookups—to see how they regress with this change as this change focuses on improving throughput for reverse scans over many rows. I used the following methodology: # Start a local HBase cluster with "hbase master start --localRegionServers=1" # Prepare the meta table for benchmarking with table state for benchmarking with "hbase pe --nomapred=true metaWrite 1". Additionally, flush the meta table and run a major compaction on it (I did this to keep the benchmarking numbers as similar as I could s.t. they were already reading over a consistent single storefile). I used the following command sequence to flush & compact the meta: {code:java} $ hbase shell > flush ‘hbase:meta’ > major_compact ‘hbase:meta’ {code} # Run "hbase pe --nomapred=true metaRandomRead 10" to benchmark meta lookup performance by scanning over all test rows inserted into the meta w/ 10 concurrent threads I got the following results (averaged over all 10 threads): ||Benchmark||Revision||Avg Latency (us)||Avg Throughput (rows / sec)|| |metaRandomRead|master|839|11898| |metaRandomRead|patch|891|11203| If anyone is interested in looking at per-thread results/response time histograms, I've pasted the raw results output logs of "hbase pe --nomapred=true metaRandomRead 10" for this patch + master in [this gist|https://gist.github.com/jbewing/b06aaf71326c323e3dfd85157c3cfcde]. As expected, this patch does bring a slight regression to the single row lookup case. That regression looks to be about ~5%. I'm theorizing that we're not seeing a huge regression here as the "hbase:meta" table has RIV1 data-block encoding applied by default which makes the extra reseek pretty cheap. > Reduce seeks from beginning of block in StoreFileScanner.seekToPreviousRow > -------------------------------------------------------------------------- > > Key: HBASE-28043 > URL: https://issues.apache.org/jira/browse/HBASE-28043 > Project: HBase > Issue Type: Improvement > Reporter: Becker Ewing > Assignee: Becker Ewing > Priority: Major > Attachments: Current_SeekToPreviousRowBehavior.png, > Proposed_SeekToPreviousRowBehavior.png > > > Currently, for non-RIV1 DBE encodings, each call to > [StoreFileScanner.seekToPreviousRow|https://github.com/apache/hbase/blob/89ca7f4ade84c84a246281c71898543b6161c099/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java#L493-L506] > (a common operation in reverse scans) results in two seeks: > # Seek from the beginning of the block to before the given row to find the > prior row > # Seek from the beginning of the block to the first cell of the prior row > So if there are "N" rows in a block, a reverse scan through each row results > in seeking past 2(N-1)! rows. > > This is a particularly expensive operation for tall tables that have many > rows in a block. > > By introducing a state variable "previousRow" to StoreFileScanner, I believe > that we could modify the seeking algorithm to be: > # Seek from the beginning of the block to before the given row to find the > prior row > # Seek from the beginning of the block to before the row that is before the > row that was just seeked to (i.e. 2 rows back). _Save_ this as a hint for > where the prior row is in "previousRow" > # Reseek from "previousRow" (2 rows back from start) to 1 row back from > start (to the actual previousRow) > Then the rest of the calls where a "previousRow" is present, you just need to > seek to the beginning of the block once instead of twice, i.e. > # seek from the beginning of the block to right before the beginning of your > "previousRow" marker. Save this as the new "previousRow" marker > # Reseek to the next row (i.e. your previous "previousRow" marker) > > If there are "N" rows in a block, a reverse scan from row N to row 0 results > in seeking past approximately (N-1)! rows i.e. 50% less than the current > behavior. > > See the attached diagrams for the current and proposed behavior. > > -- This message was sent by Atlassian Jira (v8.20.10#820010)