search

golang / groupcache

groupcache is a caching and cache-filling library, intended as a replacement for memcached in many cases.
Apache License 2.0
12.94k stars 1.39k forks source link

Added prefix match for consistent hash #103

Open bobhansen opened 6 years ago

googlebot commented 6 years ago

We found a Contributor License Agreement for you (the sender of this pull request), but were unable to find agreements for all the commit author(s) or Co-authors. If you authored these, maybe you used a different email address in the git commits than was used to sign the CLA (login here to double check)? If these were authored by someone else, then they will need to sign a CLA as well, and confirm that they're okay with these being contributed to Google. In order to pass this check, please resolve this problem and have the pull request author add another comment and the bot will run again. If the bot doesn't comment, it means it doesn't think anything has changed.

googlebot commented 6 years ago

We found a Contributor License Agreement for you (the sender of this pull request), but were unable to find agreements for all the commit author(s) or Co-authors. If you authored these, maybe you used a different email address in the git commits than was used to sign the CLA (login here to double check)? If these were authored by someone else, then they will need to sign a CLA as well, and confirm that they're okay with these being contributed to Google. In order to pass this check, please resolve this problem and have the pull request author add another comment and the bot will run again. If the bot doesn't comment, it means it doesn't think anything has changed.

googlebot commented 6 years ago

CLAs look good, thanks!

googlebot commented 6 years ago

CLAs look good, thanks!

bobhansen commented 6 years ago

Changes consistenthash's get() function from O(log n) to O(1), with a memory overhead of 6*n (where n is the number of virtual nodes).

On an AWS t3.2xlarge dedicated instance, this reduces the consistenthash benchmark times by 56% (8 nodes) to 72% (512 nodes). Data available at https://docs.google.com/spreadsheets/d/1K_kmk0_Lqk6iaSDUytjkT8RNGPTptBwBEWO8q4uAn3w/edit?usp=sharing

image

bobhansen commented 6 years ago

This is a breaking API change for anybody using this package. Also, this parameter isn't documented. Maybe make a new NewXxx func instead taking the new parameter and make the existing New default to 6 or whatever?

Done. I didn't know we had external consumers of the package.

document these fields now that they're non-obvious?

Done, and gladly. Let me know if the documentation is too verbose or unclear.

bhansen-uber commented 6 years ago

@bradfitz : ping

bradfitz commented 6 years ago

I'm not seeing any changes. Did you forget to push?

bobhansen commented 6 years ago

Oh, my. That's embarrassing. I got back to your comments in the hour after you made them, then forgot to push them up.

They're pushed now.

bobhansen commented 6 years ago

Oh, my. That doesn't inspire confidence in someone's changes, does it? I had run go test at the root of the project, assuming that it would run for the transitive projects.

Fixed the issues requested (in all instances). All of the tests pass now.

bobhansen commented 5 years ago

@bradfitz Requested changes made. Would love to see this change included so I can drop my forked repo.