forked from uber/tchannel-go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
prefer.go
70 lines (60 loc) · 2.56 KB
/
prefer.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// Copyright (c) 2017 Uber Technologies, Inc.
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
package peers
import "github.com/uber/tchannel-go"
type hrwScoreCalc struct {
clientID uint32
}
// NewHRWScorer returns a ScoreCalculator based on Rendezvous or Highest Random Weight
// hashing.
// It is useful for distributing load in peer-to-peer situations where we have
// many clients picking from a set of servers with "sticky" semantics that will
// spread load evenly as servers go down or new servers are added.
// The clientID is used to score the servers, so each client should pass in
// a unique client ID.
func NewHRWScorer(clientID uint32) tchannel.ScoreCalculator {
return &hrwScoreCalc{mod2_31(clientID)}
}
func (s *hrwScoreCalc) GetScore(p *tchannel.Peer) uint64 {
server := mod2_31(fnv32a(p.HostPort()))
// These constants are taken from W_rand2 in the Rendezvous paper:
// http://www.eecs.umich.edu/techreports/cse/96/CSE-TR-316-96.pdf
v := 1103515245*((1103515245*s.clientID+12345)^server) + 12345
return uint64(mod2_31(v))
}
func mod2_31(v uint32) uint32 {
return v & ((1 << 31) - 1)
}
// This is based on the standard library's fnv32a implementation.
// We copy it for a couple of reasons:
// 1. Avoid allocations to create a hash.Hash32
// 2. Avoid converting the []byte to a string (another allocation) since
// the Hash32 interface only supports writing bytes.
func fnv32a(s string) uint32 {
const (
initial = 2166136261
prime = 16777619
)
hash := uint32(initial)
for i := 0; i < len(s); i++ {
hash ^= uint32(s[i])
hash *= prime
}
return hash
}