Redwood page splitting/building refactor #4616

sfc-gh-satherton · 2021-04-05T02:05:09Z

When pages overflow, two or more replacement pages are built. This refactor avoids some problems with the previous logic that could result in many under-filled pages being generated. The new logic will split 1 page into 2 more evenly, and if more than 2 pages are being generated then page boundaries will be selected to maximize space usage in all but the final two pages which will share the remaining slack between them.

Previously it was unclear how much space used by Redwood was due to the remap cleanup window and how much was caused by excessive page slack addressed by this PR, so StorageBytes now includes a temporary space concept. Also, logging of storage bytes has been moved to a more efficient place where it is called 4x or 8x less often without any loss of detail.

Passed 100k correctness of only RedwoodCorrectnessBTree 20210404-084601-satherton_redwood-99a5a8607c0ca3ef
Passed 100k full correctness, there were errors but they seem similar to recent nightly_master errors.

Code-Reviewer Section

The general guidelines can be found here.

Please check each of the following things and check all boxes before accepting a PR.

The PR has a description, explaining both the problem and the solution.
The description mentions which forms of testing were done and the testing seems reasonable.
Every function/class/actor that was touched is reasonably well documented.

For Release-Branches

If this PR is made against a release-branch, please also check the following:

This change/bugfix is a cherry-pick from the next younger branch (younger release-branch or master if this is the youngest branch)
There is a good reason why this PR needs to go into a release branch and this reason is documented (either in the description above or in a linked GitHub issue)

…s more evenly.

…mprovements

foundationdb-ci · 2021-04-05T02:26:58Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 684ae96
Result: FAILED
Build Logs (available for 7 days)

foundationdb-ci · 2021-04-05T02:30:07Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 5c93e68
Result: FAILED
Build Logs (available for 7 days)

…improvements

foundationdb-ci · 2021-04-05T17:13:56Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 5c93e68
Result: FAILED
Build Logs (available for 7 days)

foundationdb-ci · 2021-04-05T18:31:52Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 5c93e68
Result: FAILED
Build Logs (available for 7 days)

…improvements

…ing file, and whether or not to insert new records.

foundationdb-ci · 2021-04-06T09:54:01Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 5f89640
Result: FAILED
Build Logs (available for 7 days)

foundationdb-ci · 2021-04-06T10:11:30Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: aacee06
Result: FAILED
Build Logs (available for 7 days)

sfc-gh-satherton · 2021-04-06T10:11:33Z

This PR includes #4617 and should be merged after it.

…nt readers.

foundationdb-ci · 2021-04-06T10:49:48Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 394e562
Result: FAILED
Build Logs (available for 7 days)

…est.

…improvements # Conflicts: # fdbserver/VersionedBTree.actor.cpp

foundationdb-ci · 2021-04-08T03:22:45Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: f8786da
Result: FAILED
Build Logs (available for 7 days)

foundationdb-ci · 2021-04-08T03:28:58Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 27de8e3
Result: FAILED
Build Logs (available for 7 days)

foundationdb-ci · 2021-04-08T03:47:37Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 5074ac6
Result: FAILED
Build Logs (available for 7 days)

foundationdb-ci · 2021-04-08T07:04:24Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 5e6655f
Result: FAILED
Build Logs (available for 7 days)

…newest TLog version only). Moved StorageBytes detail from SpecialCounters to the traceCounters() decorator callback to avoid calling getStorageBytes(), which makes a system call, four extra times on storage servers and eight extra times on logs.

foundationdb-ci · 2021-04-08T08:16:20Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: cbd77fe
Result: FAILED
Build Logs (available for 7 days)

…improvements

sfc-gh-satherton · 2021-04-15T01:26:09Z

This PR includes #4617

foundationdb-ci · 2021-04-15T02:10:23Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 3aa237b
Result: SUCCEEDED
Build Logs (available for 7 days)

…improvements

foundationdb-ci · 2021-04-15T23:47:46Z

AWS CodeBuild CI Report

CodeBuild project: foundationdb-pull-request-build
Commit ID: 561dfc0
Result: SUCCEEDED
Build Logs (available for 7 days)

sfc-gh-ngoyal · 2021-05-03T18:23:28Z

fdbserver/VersionedBTree.actor.cpp

+			// This is a loop because the first expansion may increase per-node overhead which could
+			// then require a second expansion.
+			while (bytesLeft < 0) {
+				int newBlocks = (-bytesLeft + blockSize - 1) / blockSize;


Maybe add a comment about this math as we discussed.

sfc-gh-ngoyal · 2021-05-03T18:24:16Z

fdbserver/VersionedBTree.actor.cpp

+		             upperBound->toString(false).c_str());
+		ASSERT(!records.empty());
+
+		// Leaves can have just one record if it's large, but internal pages should have at least 4


Worth adding a comment on choosing this number for internal nodes.

sfc-gh-ngoyal · 2021-05-03T18:31:15Z

fdbserver/VersionedBTree.actor.cpp

+				--p.count;
+				debug_printf("Skipping first null record, new count=%d\n", p.count);
+
+				// If the page is now empty then it must be the last page in pagesToBuild, otherwise there would


As per discussion, please add a slide or an ascii picture to make it clear visually whenever you get a chance.

sfc-gh-ngoyal

Looks great.

I know you already plan to make the naming consistent. So looking forward to the page/block/node naming to be made consistent. It can be a bit confusing while reading the code as the Pager also uses page as its building block and it's different from what BTree treats as pages.

Backport changes made to TLogServer in apple#4616 back to old TLog implementations. Old implementations were using SpecialCounter, which is string. The new type is int64_t. Without the change, we can have many events like: <Event Severity="30" Time="1658165532.958152" DateTime="2022-07-18T17:32:12Z" Type="ScopeEventFieldTypeMismatch" ID="0000000000000000" EventType="TraceEvent.TLogMetrics" FieldName="QueueDiskBytesUsed" OldType="Int64" NewType="String" ThreadID="2451559325190099131" Machine="10.242.248.26:4703" LogGroup="xxxx" Roles="TL" />

Backport changes made to TLogServer in #4616 back to old TLog implementations. Old implementations were using SpecialCounter, which is string. The new type is int64_t. Without the change, we can have many events like: <Event Severity="30" Time="1658165532.958152" DateTime="2022-07-18T17:32:12Z" Type="ScopeEventFieldTypeMismatch" ID="0000000000000000" EventType="TraceEvent.TLogMetrics" FieldName="QueueDiskBytesUsed" OldType="Int64" NewType="String" ThreadID="2451559325190099131" Machine="10.242.248.26:4703" LogGroup="xxxx" Roles="TL" />

Backport changes made to TLogServer in apple#4616 back to old TLog implementations. Old implementations were using SpecialCounter, which is string. The new type is int64_t. Without the change, we can have many events like: <Event Severity="30" Time="1658165532.958152" DateTime="2022-07-18T17:32:12Z" Type="ScopeEventFieldTypeMismatch" ID="0000000000000000" EventType="TraceEvent.TLogMetrics" FieldName="QueueDiskBytesUsed" OldType="Int64" NewType="String" ThreadID="2451559325190099131" Machine="10.242.248.26:4703" LogGroup="xxxx" Roles="TL" />

sfc-gh-satherton added 3 commits April 3, 2021 19:54

Refactored page rebuild logic to bulk build pages full and split page…

90ebf90

…s more evenly.

Merge branch 'master' of github.com:apple/foundationdb into redwood-i…

684ae96

…mprovements

Added comments.

5c93e68

Merge commit 'e7573d546f094bd96e1b2fca0914c6e8d61c77e4' into redwood-…

f8711cf

…improvements

sfc-gh-satherton added 2 commits April 6, 2021 02:40

Merge commit 'b4e42476b726a18b196a31db338db960f2e99c81' into redwood-…

4f9d01b

…improvements

Added performance unit test options for read parallelism, using exist…

5f89640

…ing file, and whether or not to insert new records.

Applied clang-format.

aacee06

Added seek and scan counts, parallel reads divide count over concurre…

394e562

…nt readers.

Removed btree cleanup parameter override.

60e5955

sfc-gh-satherton assigned sfc-gh-ngoyal Apr 8, 2021

sfc-gh-satherton added 2 commits April 7, 2021 20:14

Added StorageByte::toString() and printed it in Redwood direct perf t…

f8786da

…est.

Merge commit '60e59555a729a8227da903d65a6a264de4d97629' into redwood-…

27de8e3

…improvements # Conflicts: # fdbserver/VersionedBTree.actor.cpp

Missed file from previous merge commit.

5074ac6

Added temp space to StorageBytes.

5e6655f

sfc-gh-satherton requested a review from sfc-gh-ngoyal April 8, 2021 14:14

sfc-gh-satherton unassigned sfc-gh-ngoyal Apr 8, 2021

Merge commit 'd51f94f16ee903aa249ddaac0047c88cafac1e89' into redwood-…

3aa237b

…improvements

sfc-gh-satherton assigned sfc-gh-ngoyal Apr 15, 2021

sfc-gh-satherton marked this pull request as ready for review April 15, 2021 01:26

Merge commit 'a445e09c2dce3443ca2ccf78363c5e90a1ea417c' into redwood-…

561dfc0

…improvements

sfc-gh-satherton mentioned this pull request Apr 17, 2021

Redwood - Skip page copy for update if page wasn't already cached #4678

Merged

5 tasks

sfc-gh-ngoyal reviewed May 3, 2021

View reviewed changes

sfc-gh-ngoyal approved these changes May 3, 2021

View reviewed changes

sfc-gh-ngoyal merged commit 63d82b9 into apple:master May 3, 2021

jzhou77 mentioned this pull request Jul 20, 2022

Fix ScopeEventFieldTypeMismatch error for TLogMetrics #7638

Merged

5 tasks

jzhou77 mentioned this pull request Jul 20, 2022

Fix ScopeEventFieldTypeMismatch error for TLogMetrics [release-7.1] #7640

Merged

5 tasks

Redwood page splitting/building refactor #4616

Redwood page splitting/building refactor #4616

Uh oh!

Conversation

sfc-gh-satherton commented Apr 5, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code-Reviewer Section

For Release-Branches

Uh oh!

foundationdb-ci commented Apr 5, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 5, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 5, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 5, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 6, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 6, 2021

AWS CodeBuild CI Report

Uh oh!

sfc-gh-satherton commented Apr 6, 2021

Uh oh!

foundationdb-ci commented Apr 6, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 8, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 8, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 8, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 8, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 8, 2021

AWS CodeBuild CI Report

Uh oh!

sfc-gh-satherton commented Apr 15, 2021

Uh oh!

foundationdb-ci commented Apr 15, 2021

AWS CodeBuild CI Report

Uh oh!

foundationdb-ci commented Apr 15, 2021

AWS CodeBuild CI Report

Uh oh!

sfc-gh-ngoyal May 3, 2021

Choose a reason for hiding this comment

Uh oh!

sfc-gh-ngoyal May 3, 2021

Choose a reason for hiding this comment

Uh oh!

sfc-gh-ngoyal May 3, 2021

Choose a reason for hiding this comment

Uh oh!

sfc-gh-ngoyal left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

sfc-gh-satherton commented Apr 5, 2021 •

edited

Loading