{"action":"created","issue":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/31997","repository_url":"https://api.github.com/repos/cockroachdb/cockroach","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/31997/labels{/name}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/31997/comments","events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/31997/events","html_url":"https://github.com/cockroachdb/cockroach/pull/31997","id":375332698,"node_id":"MDExOlB1bGxSZXF1ZXN0MjI2ODAwNzMy","number":31997,"title":"storage/spanlatch: create spanlatch.Manager using immutable btrees","user":{"login":"nvanbenschoten","id":5438456,"node_id":"MDQ6VXNlcjU0Mzg0NTY=","avatar_url":"https://avatars3.githubusercontent.com/u/5438456?v=4","gravatar_id":"","url":"https://api.github.com/users/nvanbenschoten","html_url":"https://github.com/nvanbenschoten","followers_url":"https://api.github.com/users/nvanbenschoten/followers","following_url":"https://api.github.com/users/nvanbenschoten/following{/other_user}","gists_url":"https://api.github.com/users/nvanbenschoten/gists{/gist_id}","starred_url":"https://api.github.com/users/nvanbenschoten/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nvanbenschoten/subscriptions","organizations_url":"https://api.github.com/users/nvanbenschoten/orgs","repos_url":"https://api.github.com/users/nvanbenschoten/repos","events_url":"https://api.github.com/users/nvanbenschoten/events{/privacy}","received_events_url":"https://api.github.com/users/nvanbenschoten/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":4,"created_at":"2018-10-30T05:58:32Z","updated_at":"2018-11-29T16:56:51Z","closed_at":null,"author_association":"MEMBER","pull_request":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/31997","html_url":"https://github.com/cockroachdb/cockroach/pull/31997","diff_url":"https://github.com/cockroachdb/cockroach/pull/31997.diff","patch_url":"https://github.com/cockroachdb/cockroach/pull/31997.patch"},"body":"Informs #4768.\r\nInforms #31904.\r\n\r\nThis change was inspired by #31904 and is a progression of the thinking started in #4768 (comment).\r\n\r\nThe change introduces `spanlatch.Manager`, which will replace the `CommandQueue` **in a future PR**. The new type isn't hooked up yet because doing so will require a lot of plumbing changes in that storage package that are best kept in a separate PR. The structure uses a new strategy that reduces lock contention, simplifies the code, avoids allocations, and makes #31904 easier to implement.\r\n\r\nThe primary objective, reducing lock contention, is addressed by minimizing the amount of work we perform under the exclusive \"sequencing\" mutex while locking the structure. This is made possible by employing a copy-on-write strategy. Before this change, commands would lock the queue, create a large slice of prerequisites, insert into the queue and unlock. After the change, commands lock the manager, grab an immutable snapshot of the manager's trees in O(1) time, insert into the manager, and unlock. They can then iterate over the immutable tree snapshot outside of the lock. Effectively, this means that the work performed under lock is linear with respect to the number of spans that a command declares but NO LONGER linear with respect to the number of other commands that it will wait on. This is important because `Replica.beginCmds` repeatedly comes up as the largest source of mutex contention in our system, especially on hot ranges.\r\n\r\nThe use of immutable snapshots also simplifies the code significantly. We're no longer copying our prereqs into a slice so we no longer need to carefully determine which transitive dependencies we do or don't need to wait on explicitly. This also makes lock cancellation trivial because we no longer explicitly hold on to our prereqs at all. Instead, we simply iterate through the snapshot outside of the lock.\r\n\r\nWhile rewriting the structure, I also spent some time optimizing its allocations. Under normal operation, acquiring a latch now incurs only a single allocation - that being for the `spanlatch.Guard`. All other allocations are avoided through object pooling where appropriate. The overhead of using a copy-on-write technique is almost entirely avoided by atomically reference counting immutable btree nodes, which allows us to release them back into the btree node pools when they're no longer needed. This means that we don't expect any allocations when inserting into the internal trees, even with the copy-on-write policy.\r\n\r\nFinally, this will make the approach taken in #31904 much more natural. Instead of tracking dependents and prerequisites for speculative reads and then iterating through them to find overlaps after, we can use the immutable snapshots directly! We can grab a snapshot and sequence ourselves as usual, but avoid waiting for prereqs. We then execute optimistically before finally checking whether we overlapped any of our prereqs. The great thing about this is that we already have the prereqs in an interval tree structure, so we get an efficient validation check for free.\r\n\r\n### Naming changes\r\n\r\n| Before                     | After                             |\r\n|----------------------------|-----------------------------------|\r\n| `CommandQueue`             | `spanlatch.Manager`               |\r\n| \"enter the command queue\"  | \"acquire span latches\"            |\r\n| \"exit the command queue\"   | \"release span latches\"            |\r\n| \"wait for prereq commands\" | \"wait for latches to be released\" |\r\n\r\nThe use of the word \"latch\" is based on the definition of latches presented by Goetz Graefe in https://15721.courses.cs.cmu.edu/spring2016/papers/a16-graefe.pdf (see https://i.stack.imgur.com/fSRzd.png). An important reason for avoiding the word \"lock\" here is that it is critical for understanding that we don't confuse the operational locking performed by the CommandQueue/spanlatch.Manager with the transaction-scoped locking enforced by intents and our transactional concurrency control model.\r\n\r\n### Microbenchmarks\r\n\r\nNOTE: these are single-threaded benchmarks that don't benefit at all from the concurrency improvements enabled by this new structure.\r\n\r\n```\r\nname                              old time/op    new time/op    delta\r\nReadOnlyMix/size=1-4                 706ns ±20%     404ns ±10%  -42.81%  (p=0.008 n=5+5)\r\nReadOnlyMix/size=4-4                 649ns ±23%     382ns ± 5%  -41.13%  (p=0.008 n=5+5)\r\nReadOnlyMix/size=16-4                611ns ±16%     367ns ± 5%  -39.83%  (p=0.008 n=5+5)\r\nReadOnlyMix/size=64-4                692ns ±14%     370ns ± 1%  -46.49%  (p=0.016 n=5+4)\r\nReadOnlyMix/size=128-4               637ns ±22%     398ns ±14%  -37.48%  (p=0.008 n=5+5)\r\nReadOnlyMix/size=256-4               676ns ±15%     385ns ± 4%  -43.01%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=0-4      12.2µs ± 4%     0.6µs ±17%  -94.85%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=1-4      7.88µs ± 2%    0.55µs ± 7%  -92.99%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=4-4      4.19µs ± 3%    0.58µs ± 5%  -86.26%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=16-4     2.09µs ± 6%    0.54µs ±13%  -74.13%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=64-4      875ns ±17%     423ns ±29%  -51.64%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=128-4     655ns ± 6%     362ns ±16%  -44.71%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=256-4     549ns ±16%     314ns ±13%  -42.73%  (p=0.008 n=5+5)\r\n\r\nname                              old alloc/op   new alloc/op   delta\r\nReadOnlyMix/size=1-4                  223B ± 0%      160B ± 0%  -28.25%  (p=0.079 n=4+5)\r\nReadOnlyMix/size=4-4                  223B ± 0%      160B ± 0%  -28.25%  (p=0.008 n=5+5)\r\nReadOnlyMix/size=16-4                 223B ± 0%      160B ± 0%  -28.25%  (p=0.008 n=5+5)\r\nReadOnlyMix/size=64-4                 223B ± 0%      160B ± 0%  -28.25%  (p=0.008 n=5+5)\r\nReadOnlyMix/size=128-4                217B ± 4%      160B ± 0%  -26.27%  (p=0.008 n=5+5)\r\nReadOnlyMix/size=256-4                223B ± 0%      160B ± 0%  -28.25%  (p=0.079 n=4+5)\r\nReadWriteMix/readsPerWrite=0-4      1.25kB ± 0%    0.16kB ± 0%  -87.15%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=1-4      1.00kB ± 0%    0.16kB ± 0%  -84.00%  (p=0.079 n=4+5)\r\nReadWriteMix/readsPerWrite=4-4        708B ± 0%      160B ± 0%  -77.40%  (p=0.079 n=4+5)\r\nReadWriteMix/readsPerWrite=16-4       513B ± 0%      160B ± 0%  -68.81%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=64-4       264B ± 0%      160B ± 0%  -39.39%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=128-4      221B ± 0%      160B ± 0%  -27.60%  (p=0.079 n=4+5)\r\nReadWriteMix/readsPerWrite=256-4      198B ± 0%      160B ± 0%  -19.35%  (p=0.008 n=5+5)\r\n\r\nname                              old allocs/op  new allocs/op  delta\r\nReadOnlyMix/size=1-4                  1.00 ± 0%      1.00 ± 0%     ~     (all equal)\r\nReadOnlyMix/size=4-4                  1.00 ± 0%      1.00 ± 0%     ~     (all equal)\r\nReadOnlyMix/size=16-4                 1.00 ± 0%      1.00 ± 0%     ~     (all equal)\r\nReadOnlyMix/size=64-4                 1.00 ± 0%      1.00 ± 0%     ~     (all equal)\r\nReadOnlyMix/size=128-4                1.00 ± 0%      1.00 ± 0%     ~     (all equal)\r\nReadOnlyMix/size=256-4                1.00 ± 0%      1.00 ± 0%     ~     (all equal)\r\nReadWriteMix/readsPerWrite=0-4        38.0 ± 0%       1.0 ± 0%  -97.37%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=1-4        24.0 ± 0%       1.0 ± 0%  -95.83%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=4-4        12.0 ± 0%       1.0 ± 0%  -91.67%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=16-4       5.00 ± 0%      1.00 ± 0%  -80.00%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=64-4       2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)\r\nReadWriteMix/readsPerWrite=128-4      1.00 ± 0%      1.00 ± 0%     ~     (all equal)\r\nReadWriteMix/readsPerWrite=256-4      1.00 ± 0%      1.00 ± 0%     ~     (all equal)\r\n```\r\n\r\nThere are a few interesting things to point about about these benchmark results:\r\n- The `ReadOnlyMix` results demonstrate a fixed improvement, regardless of size. This is due to the replacement of the hash-map with a linked-list for the readSet structure.\r\n- The `ReadWriteMix` is more interesting. We see that the spanlatch implementation is faster across the board. This is especially true with a high write/read ratio.\r\n- We see that the allocated memory stays constant regardless of the write/read ratio in the spanlatch implementation. This is due to the memory recylcing that it performs on btree nodes. It is not the case for the CommandQueue implementation.\r\n\r\nRelease note: None"},"comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments/442910319","html_url":"https://github.com/cockroachdb/cockroach/pull/31997#issuecomment-442910319","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/31997","id":442910319,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0MjkxMDMxOQ==","user":{"login":"nvanbenschoten","id":5438456,"node_id":"MDQ6VXNlcjU0Mzg0NTY=","avatar_url":"https://avatars3.githubusercontent.com/u/5438456?v=4","gravatar_id":"","url":"https://api.github.com/users/nvanbenschoten","html_url":"https://github.com/nvanbenschoten","followers_url":"https://api.github.com/users/nvanbenschoten/followers","following_url":"https://api.github.com/users/nvanbenschoten/following{/other_user}","gists_url":"https://api.github.com/users/nvanbenschoten/gists{/gist_id}","starred_url":"https://api.github.com/users/nvanbenschoten/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nvanbenschoten/subscriptions","organizations_url":"https://api.github.com/users/nvanbenschoten/orgs","repos_url":"https://api.github.com/users/nvanbenschoten/repos","events_url":"https://api.github.com/users/nvanbenschoten/events{/privacy}","received_events_url":"https://api.github.com/users/nvanbenschoten/received_events","type":"User","site_admin":false},"created_at":"2018-11-29T16:56:51Z","updated_at":"2018-11-29T16:56:51Z","author_association":"MEMBER","body":"bors r-"}}
{"actor":{"display_login":"nvanbenschoten"}}