search

buraksezer / consistent

Consistent hashing with bounded loads in Golang
https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html
MIT License
693 stars 69 forks source link

Possibly incorrect implementation #8

Closed shaqque closed 5 years ago

shaqque commented 5 years ago

I may be wrong, but there doesn't seem to be any place in the code where the load of a member (i.e. a node) is incremented. The only place where load distribution happens is when a new node is added or removed. This doesn't let the ring keep track of how much load each member has, especially once new clients/load are being allocated to the members. However, the point of bounded loads is that the load of each member is getting kept track of, so that if a new client comes in and would be allocated to a member with above-average load, the client will be added to another member instead.

In effect, I think your implementation may just be the classic consistent hash but not necessarily with bounded loads.

buraksezer commented 5 years ago

Hello,

This package is specifically designed for a key-value store called Olric. It's designed to distribute keys among partitions by using modulo operator and the partitions are distributed among members by the consistent package. So the consistent package knows nothing about keys. It manages partitions. The keys are distributed evenly among partitions by the modulo operator. Many of these design decisions are mentioned in README.md.

A member may has more partitions than the others. So it may has too many keys than the others but that's not a problem for Olric's design perspective.

Examples section should be useful to understand the concepts.

If you have any further questions about this package and Olric, please feel free ask questions.

shaqque commented 5 years ago

Thanks for getting back to me! I was confused by the readme talking about loads and partitions and assumed that load refers to keys. I'm guessing this means that load as defined in this package refers to the number of partitions per member then? If so, it may be a good idea to add this information explicitly in the readme for new readers.

buraksezer commented 5 years ago

Load is totally different than the number of partitions. You can find the proper definition of load in Google's paper and blog post.

I'll review the README file to clarify differences between load, partitions and keys.

asad-awadia commented 4 years ago

@buraksezer I had the same question - how does the load part work at all? The code seems disconnected

Does it do bounded load on the physical resources/servers/nodes or not?

jinq0123 commented 4 years ago

This is not "Consistent hashing with bounded loads".

buraksezer commented 4 years ago

@asad-awadia I'm so sorry for the late response. Would you like to expand your question? This package is designed to distribute partitions among nodes, not keys. In my use case*, it's okay to have a few more partitions. So if you have 71 partitions with 3 nodes, the algorithm distributes partitions like that NodeA: 27, NodeB: 22, NodeC: 22. Let's say that none of the nodes cannot has more than 30 partitions, so partition distribution may look like that NodeA: 30, NodeB: 30, NodeC: 11.

Thins kind of bounding is not a problem for my application. If you need to set a boundary against key count, you need a different implementation.

Olric manages partitions between hosts, it doesn't care about keys.

@jinq0123 I tried to explain the design again. If you have any further questions about this package, please feel free to ask.