Currently the hash ring has 3 replicas per node, that can cause statistical imbalances of key distribution, especially with low number of machines.

The number of replicas should be configurable. For example, a similar Python hash ring library has 40 replicas per node. From tests I made, this is indeed the vicinity of the replicas number where the distribution stabilizes, regardless of the number of nodes.

I made a few benchmarks directly on the consistent hash to illustrate this (I can post the code to generate this if you want, it uses random "ip addrsses" and keys). The bars are the number of random keys out of 10k keys that mapped to each random node. all tests on the same number of nodes were made with the same node "ips".

2 Nodes X  3 Replicas:
    36.75% | ####################################
    63.25% | ###############################################################

2 Nodes X  33 Replicas:
    49.77% | #################################################
    50.23% | ##################################################

3 Nodes X  3 Replicas:
    23.05% | #######################
    33.45% | #################################
    43.50% | ###########################################

3 Nodes X  33 Replicas:
    31.50% | ###############################
    31.14% | ###############################
    37.36% | #####################################

7 Nodes X  3 Replicas:
    30.08% | ##############################
    11.24% | ###########
    6.44% | ######
    7.29% | #######
    27.42% | ###########################
    9.26% | #########
    8.27% | ########

7 Nodes X  43 Replicas:
    13.53% | #############
    16.00% | ################
    16.92% | ################
    10.31% | ##########
    14.78% | ##############
    12.74% | ############
    15.72% | ###############

Reproduce steps

pool := groupcache.NewHTTPPool("http://127.0.0.1:"+os.Getenv("PORT"))
cache := groupcache.NewGroup("cacher", 64<<20, someGetterFunc)
pool.Set("http://127.0.0.1:50000", "http://127.0.0.1:50001")

and run it in two port :50000 and :50001 Now, if use /xxx as a key, then the groupcacher will act like there is no any peer. i.e. It will only get data from locally, instead of getting from peers.

The problem is the slash in the head of the key (i.e. if the key is xxx then everything goes right), and I still can't figure out why.

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

The default constructor NewHTTPPool is making too many assumptions about how people would use the library. For example, for security purpose I'd want groupcache to listen on a different port by calling Handle on a different ServeMux other than the http.DefaultServeMux. Others have also requested to be able to specify the basePath perhaps to shorter paths for performance reasons https://github.com/golang/groupcache/issues/22 ?

Description

The groupcache node canot download content from peer when peer has the right content When use groupcache.HTTPPool

Details

URL like http://10.246.14.51:5100/_groupcache/thumbnail/%2Fapi%2Fapks will return http status(301)

client has to request to http://10.246.14.51:5100/_groupcache/thumbnail/api/apks again.

But tr.RoundTrip cannot follow http redirect. So use http.Client will fix this problem.

My question is a bit similar to issue https://github.com/golang/groupcache/issues/3.

I have a map that is currently managed in the RAM of the go application on a single instance. I want to share this map between multiple instances for scaling. I am already using consul for discovery of peer instances and I am currently solving this with redis, however I am not happy with the fact that I am not leveraging each machine's RAM (so in that sense I feel that redis is more a DB than a cache). This is one reason why I love groupcache.

I have a constraint though: my map changes all the time (I'm getting requests to update it via http). So for a key K1 in the map, it is likely that m[K1] will be updated very frequently (possibly every one second or less).

So my questions are:

1. Am I choosing the wrong architecture? Should I use something like Redis or memecached instead?
2. If groupcache is a good solution for my use case, do I have to constantly remove and add (say in an LRU cache) or is there a smarter way?

Thanks!

Currently found in the use of HttpPool groupcache, key to "/" at the beginning of the peer can not exchange data between bug hope to solve the next? thinks

The binary search quickly out-paces the linear search, even for a small number of shards and replicas.

benchmark old ns/op new ns/op delta BenchmarkGet8 122 122 +0.00% BenchmarkGet32 471 137 -70.91% BenchmarkGet128 5619 254 -95.48% BenchmarkGet512 90302 406 -99.55%

would be very handy. based on the docs, it looks like it could run in the same application on app engine too.

Anyway, has anyone gotten this far with this ?

this PR implements GRPCPool which follows PeerPicker interface but the implementation is based on google's grpc. there are some issues which haven't been addressed in this PR, we could have them in a separated PR

==1. interface: grpc uses protobuf version 3, the generated stub is different with the one generated before. Like v2:

type GetRequest struct {
        Group            *string `protobuf:"bytes,1,req,name=group" json:"group,omitempty"`
        Key              *string `protobuf:"bytes,2,req,name=key" json:"key,omitempty"`
        XXX_unrecognized []byte  `json:"-"`
}

v3:

type GetRequest struct {
       Group string `protobuf:"bytes,1,opt,name=group" json:"group,omitempty"`
       Key   string `protobuf:"bytes,2,opt,name=key" json:"key,omitempty"`
}

If we switched to protoc 3 directly, we may break something. so we just workaround this. The interface is untouched.

==2. Context: right now the context used in groupcache is self-defined Context

// ProtoGetter is the interface that must be implemented by a peer.
type ProtoGetter interface {
        Get(context Context, in *pb.GetRequest, out *pb.GetResponse) error
}

and grpc use "golang.org/x/net/context" as default context. so we can pick one.

==3. performance comparison: we will do that after the implementation sounds good.

Hello! First of all, thanks a lot for this project.

My issue is: Is it possible to spread updates of the peers list initiated in one node to others automatically? You have this implementation

func (p *HTTPPool) Set(peers ...string) {
    p.mu.Lock()
    defer p.mu.Unlock()
    p.peers = consistenthash.New(defaultReplicas, nil)
    p.peers.Add(peers...)
    p.httpGetters = make(map[string]*httpGetter, len(peers))
    for _, peer := range peers {
        p.httpGetters[peer] = &httpGetter{transport: p.Transport, baseURL: peer + p.basePath}
    }
}

I don't see anything to make it happens in code above. Or is it inconsistent with goals of the groupcache project? And if so why? Thanks!

1.add default replicas groupcache/consistenthash.go: line 34. replicas must has a default value. if replicas <=0, then it will do nothing when call func (m *Map) Add(keys ...string)

and i suggest the default replicas value is 23

2.add sync.Mutex. when call Add and Get，we can lock the kes and hashMap

The Add function does not add the hash value of the string key itself to the list keys, so what is the meaning of 'Direct match' in the sentence "Direct matches should always return the same entry", I think this is a bug in the test code, Does 'Direct match' mean that the queried string directly corresponds to a replicated node? So I made some changes to the code.