stathat/consistent

Consistent hash package for Go.

consistent's Issues

Consistent.hashKey: Why do we need the if statement?

https://github.com/stathat/consistent/blob/master/consistent.go#L239
I don't see any difference when the 'if' statement is absence.

Found slice index can't be greater than the slice's length

consistent/consistent.go

Lines 161 to 164 in 30ea17e

	i = sort.Search(len(c.sortedHashes), f)
	if i >= len(c.sortedHashes) {
	i = 0
	}

seems like i is never greater than len(c.sortedHashes)

 i = sort.Search(len(c.sortedHashes), f) 
 if i == len(c.sortedHashes) { 
 	i = 0 
 } 

go get faild

Get https://stathat.com/c/consistent?go-get=1: x509: certificate has expired or is not yet valid

Distribution is not uniform

Please see strava/go.serversets#7 for more details. That library uses a vendored version of this consistent hash library. What I'm seeing is a distribution like:

  58856 - 10.0.16.69:11211
  18389 - 10.0.22.188:11211
  22755 - 10.0.26.214:11211

(count - server for 10k random strings)

This uneven distribution is what we're seeing in production so I don't think it's an issue with the random key generation. Have you guys encountered this before? Am I using the code wrong?

failed go get

I failed go get stathat.com/c/consistent.
Do you have a problem about this?

Why copy string to [64]byte slice instead of converting it ?

consistent/consistent.go

Lines 238 to 245 in 75142be

	func (c *Consistent) hashKey(key string) uint32 {
	if len(key) < 64 {
	var scratch [64]byte
	copy(scratch[:], key)
	return crc32.ChecksumIEEE(scratch[:len(key)])
	}
	return crc32.ChecksumIEEE([]byte(key))
	}

for performances reasons ?

( hi ! )

what is the meaning of reallocate for hashes

i can not find the meaning of reallocating and what is the judgement about.
Can someone explain it?

    //reallocate if we're holding on to too much (1/4th)
    if cap(c.sortedHashes)/(c.NumberOfReplicas*4) > len(c.circle) {
        hashes = nil
    }

https certificate has expired or is not yet valid

Hi patrickxb
I guess your SSL certificate is expired ?
Today I try to update consistent package and go the error below ~
Fetching https://stathat.com/c/consistent?go-get=1
https fetch failed: Get https://stathat.com/c/consistent?go-get=1: x509: certificate has expired or is not yet valid
Thank you

I have a confuse with the code, why 1/4th ?

I have a confuse that Line 265 in consistent.go.

//reallocate if we're holding on to too much (1/4th)
if cap(c.sortedHashes)/(c.NumberOfReplicas*4) > len(c.circle) {
hashes = nil
}

You stated that it is 1/4, how about this bellow.

if cap(c.sortedHashes)/4 > len(c.circle) {
hashes = nil
}

fail

$ go get -v -d stathat.com/c/consistent
Fetching https://stathat.com/c/consistent?go-get=1
https fetch failed.
import "stathat.com/c/consistent": https fetch: Get https://stathat.com/c/consistent?go-get=1: dial tcp 50.17.204.11:443: getsockopt: connection refused
package stathat.com/c/consistent: unrecognized import path "stathat.com/c/consistent"

Provide a idempotent Add|Remove method?

If add or remove method called.
it updates the members map and the cycle map by the node names, buy count filed increase or decrease every times.
if add or remove called multi times for a same node, the count value is incorrect.

crc32 hash value conflict in add function

i think we should take crc32 hash value conflict in add function, as shown in

// need c.Lock() before calling
func (c *Consistent) add(elt string) {
    for i := 0; i < c.NumberOfReplicas; i++ {
    c.circle[c.hashKey(c.eltKey(elt, i))] = elt
    }
    c.members[elt] = true
    c.updateSortedHashes()
    c.count++
}

the c.hashKey(c.eltKey(elt, i)) may return a conflict, i.e., a duplicate crc32 hash value and in such a situation we can not guarantee that we can have specified NumberOfReplicas for each node.

For more info, an example can be get in carbon

def add_node(self, node):
    self.nodes.add(node)
    for i in range(self.replica_count):
      replica_key = "%s:%d" % (node, i)
      position = self.compute_ring_position(replica_key)
      while position in [r[0] for r in self.ring]:
        position = position + 1
      entry = (position, node)
      bisect.insort(self.ring, entry)

Cerificate expired.

Hi! I got this error when I tried to go get. Would you mind taking a look?

package stathat.com/c/consistent: unrecognised import path "stathat.com/c/consistent" (https fetch: Get https://stathat.com/c/consistent?go-get=1: x509: certificate has expired or is not yet valid)```

go.mod and release tag should present

Hi, please adding go.mod and release a version at your convenience.

Provide link to godoc in README

Please instead of “Look at godoc” provide a link to hosted package documentation in the README.
http://godoc.org/github.com/stathat/consistent

This would allow people to check out the examples as well as documentation without the necessity of a running go environment and cloning the library, then opening their local godoc.

Cert expired, cannot go `get this` package

The cert for https://stathat.com/ has expired, so go get stathat.com/c/consistent fails.

Dependency sucks

First I cannot get your package when I turn on my proxy in http://www.stathat.com/c/consistent
It get 500 Error
if I turn off proxy , I can get your package，but I cannot get other important dependency
I don't know why you put the import path not from github
whatever it sucks

GetN method may fall into infinite loop

When I only have 2 elements, but execute Add 3 times, at this time c.count == 3, after that GetN(3) is executed, if start == 0, then the for loop will fall into an infinite loop, because i can never Return to 0, which means that the exit condition of start != i cannot be met, because the minimum value of i is 1, and len(res) is 2, which is always less than n, and the loop cannot exit.

Https Certificate expired again

This issue came up earlier #24

Seems like the https certificate expired again. I tried the following command as suggested in the previous issue but get the same error

$: go get github.com/stathat/consistent@master
go: stathat.com/c/[email protected]: unrecognized import path "stathat.com/c/consistent" (https fetch: Get https://stathat.com/c/consistent?go-get=1: x509: certificate has expired or is not yet valid)
go: error loading module requirements

Bug: hash collision leads to inconsistent sharding

A hash collision is possible at /consistent.go#L76. That means the consistency of results is dependent on the order of Add() calls.

I think the easiest fix is to get rid of Consistent.circle altogether and just use .sortedHashes to keep something like struct {hash uint32, key string}.
search() would have to be updated to compare not just the hashes but key values too.

Regardless of this bug, Consistent.circle adds unnecessary complexity.

https certificate has expired today,

Hello, your https certificate has expired today, the package is no longer available, can you fix it?

Excellent, but i have a confuse with the code

what a nice code!
I have a confuse that Line 248 in consistent.go

hashes := c.sortedHashes[:0]

it seems that this line is not necessary ,maybe we could replace like the code below directly?

 hashes := []uint32