Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

perf: reconsider crypto/rand use in UUID allocation for txn IDs #30236

Closed
nvanbenschoten opened this issue Sep 14, 2018 · 3 comments
Closed

perf: reconsider crypto/rand use in UUID allocation for txn IDs #30236

nvanbenschoten opened this issue Sep 14, 2018 · 3 comments
Assignees
@ajwerner @nvanbenschoten
Labels
A-kv-client Relating to the KV client and the KV interface. C-performance Perf of queries or internals. Solution not expected to change functional behavior.

Comments

@nvanbenschoten
Copy link
Member

We currently use V4 UUIDs as transaction IDs. Our UUID library, github.com/satori/go.uuid, uses a cryptographically secure random number generator (crypto/rand) to populate the UUID. In #30233, we observed that this was responsible for 77% of mutex contention during a kv95 --concurrency=64 run on my laptop:

screen shot 2018-09-14 at 1 18 20 pm

I ran an experiment where I swapped this over to a cryptographically insecure math/rand rng (which still uses a global lock) and saw this lock contention completely disappear. I also saw throughput jump by about 2.1%.

screen shot 2018-09-14 at 1 18 29 pm

I don't think we need a cryptographically secure random byte generator for our transaction IDs, so we should consider making this change for real. github.com/satori/go.uuid won't let us swap out the rng, but github.com/google/uuid will, and we already have an open issue to replace our uuid library:
#26332.

Also, FWIW in the long run, we might be replacing UUID txn ids entirely. See #24194.

@m-schneider this got me thinking about #26178. If/once #30233 is merged, we should take a look at mutex profiles before and after the throughput cliff we're observing in that issue.
@nvanbenschoten nvanbenschoten added C-performance Perf of queries or internals. Solution not expected to change functional behavior. A-kv-client Relating to the KV client and the KV interface. labels Sep 14, 2018
@nvanbenschoten nvanbenschoten added this to the 2.1 milestone Sep 14, 2018
@nvanbenschoten nvanbenschoten self-assigned this Sep 14, 2018
@jordanlewis
Copy link
Member

Yes!! Really happy to see this - I've noticed UUID generation taking a lot of time in profiles but I didn't think we could fix it.

@petermattis
Copy link
Collaborator

I seem to recall looking at this in the past and discovering that crypto generation on Mac OS X was super slow in comparison to Linux. You might want to verify the perf increase on a Linux box.

@nvanbenschoten nvanbenschoten mentioned this issue Sep 17, 2018
Merged
@nvanbenschoten nvanbenschoten modified the milestones: 2.1, 2.2 Oct 1, 2018
@petermattis petermattis removed this from the 2.2 milestone Oct 5, 2018
@nvanbenschoten
Copy link
Member Author

I looked into this at the time and confirmed that uuid.NewV4 did not have the same impact on mutex profiles on Linux machines as it does Mac.

However, I'm now seeing it come up on a single node m5d.12xlarge (48 vCPU) cluster in CPU profiles. It's responsible for a little under 2% of the total CPU utilization. All of the time is spent in internal/syscall/unix.GetRandom's getrandom(2) syscall. I don't know anything about the /dev/urandom device's implementation, but posts like http://drsnyder.us/2014/04/16/linux-dev-urandom-and-concurrency.html and https://news.ycombinator.com/item?id=7610273 paint a clear enough picture that it's going to be a concurrency bottleneck, especially on larger machines. Since it doesn't sound like there's any reason why we need a cryptographically secure random byte generator for these IDs, I think we should make the change.

This was referenced Nov 12, 2018
Closed
Closed
@ajwerner ajwerner mentioned this issue Nov 12, 2018
Merged
ajwerner added a commit to ajwerner/cockroach that referenced this issue Nov 13, 2018
@ajwerner
util/uuid: fork gofrs, generate txn IDs with math/rand instead of cry…
41fee30 
…pto/rand

Fixes cockroachdb#30236
Copies the source from github.com/gofrs/uuid into util/uuid at 7077aa61129615a0d7f45c49101cd011ab221c27.
Remove github.com/satori/go.uuid dep
Modifies the copyright notice to refer to the license at licenses/MIT-gofrs.txt.
Renames the spurious Bytes method to bytes.
Adds the ability to create a Gen with a random byte Reader.
Add FastMakeV4() which uses a generator which draws from a math/rand.Rand.
Use FastMakeV4 in roachpb.MakeTransaction.

Release note (performance improvement): Use faster randomness source to generate transaction IDs.
ajwerner added a commit to ajwerner/cockroach that referenced this issue Nov 14, 2018
@ajwerner
util/uuid: support generation of fast but non-cryptographically secur…
fd9705b 
…e UUIDs

Replace our UUID library, github.com/satori/go.uuid, which was unmaintained and did not provide a facility for customizing the source of randomness. The new library is based upon the MIT-licensed github.com/gofrs/uuid library (at 7077aa61129615a0d7f45c49101cd011ab221c27), which is a better maintained fork of the previous dependency. Because the code is so simple, copy and paste it wholesale rather than vendoring it to ease modification. Modify the forked library to allow customization of the source of randomness and remove problematic Bytes method on the UUID object which complicates its use inside protobuf generated structs.

The new library exposes a fast UUID generation function, FastMakeV4, that uses a non-cryptographically secure function for generating UUIDs. For now, only transaction ID generation uses the new fast generation function, as transaction IDs are only used internally and therefore do not need a cryptographically-secure source of randomness. Other calls to UUID generation, like the SQL builtins, continue to use a cryptographically-secure source of randomness.

Fixes cockroachdb#30236

Release note (performance improvement): Use faster randomness source to generate transaction IDs.
craig bot pushed a commit that referenced this issue Nov 14, 2018
@ajwerner
Merge #32238
ebd357c 
32238: util/uuid: fork gofrs, generate with math/rand instead of crypto/rand r=ajwerner a=ajwerner

Fixes #30236
Copies the source from github.com/gofrs/uuid into util/uuid at 7077aa61129615a0d7f45c49101cd011ab221c27.
Modifies the copyright notice to refer to the license at licenses/MIT-gofrs.txt.
Renames the spurious Bytes method to bytes.
Adds the ability to create a Gen with a random byte Reader.
Add FastMakeV4() which uses a generator which draws from a math/rand.Rand.
Use FastMakeV4 in roachpb.MakeTransaction.

Release note (performance improvement): Use faster randomness source to generate transaction IDs.

Co-authored-by: Andrew Werner <ajwerner@cockroachlabs.com>
@craig craig bot closed this as completed in #32238 Nov 14, 2018
@srosenberg srosenberg mentioned this issue Aug 24, 2023
Closed
@rafiss rafiss mentioned this issue Sep 12, 2023
Merged
18 tasks
rafiss added a commit to rafiss/cockroach that referenced this issue Sep 13, 2023
@rafiss
*: add back non-test usages of math/rand
15cebf9 
78fee99 moved usages of math/rand to
crypto/rand. This has performance implications, as described in
cockroachdb#30236 (comment).

Rather than forcing a change, we mark the existing non-test usages of
math/rand as ignored by the linter so the appropriate engineering teams
can decide what to do.

Release note: None
This was referenced Sep 13, 2023
Merged
Open
Closed
rafiss added a commit to rafiss/cockroach that referenced this issue Sep 13, 2023
@rafiss
*: add back non-test usages of math/rand
08e11c4 
78fee99 moved usages of math/rand to
crypto/rand. This has performance implications, as described in
cockroachdb#30236 (comment).

Rather than forcing a change, we mark the existing non-test usages of
math/rand as ignored by the linter so the appropriate engineering teams
can decide what to do.

Release note: None
craig bot pushed a commit that referenced this issue Sep 13, 2023
@rafiss
Merge #110561 #110601
7a452d9 
110561: *: add back non-test usages of math/rand r=rafiss a=rafiss

78fee99 moved usages of math/rand to
crypto/rand. This has performance implications, as described in
#30236 (comment).

Rather than forcing a change, we mark the existing non-test usages of
math/rand as ignored by the linter so the appropriate engineering teams
can decide what to do.

informs #110597
informs #110599
Release note: None

110601:     changefeedccl: Fix setting propagation flake r=miretskiy a=miretskiy

Setting changes are asynchronous, particularly in tenants.
Set the feature setting directly instead.

Fixes #110300

Release note: None

Co-authored-by: Rafi Shamim <rafi@cockroachlabs.com>
Co-authored-by: Yevgeniy Miretskiy <yevgeniy@cockroachlabs.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@ajwerner ajwerner

@nvanbenschoten nvanbenschoten

Labels
A-kv-client Relating to the KV client and the KV interface. C-performance Perf of queries or internals. Solution not expected to change functional behavior.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@jordanlewis @ajwerner @nvanbenschoten @petermattis