diff options
author | Christopher Speller <crspeller@gmail.com> | 2017-07-31 08:15:23 -0700 |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-07-31 08:15:23 -0700 |
commit | 09b49c26ddfdb20ced61e7dfd4192e750ce40449 (patch) | |
tree | 1288d069cc8a199b8eb3b858935dffd377ee3d2d /vendor/github.com/go-redis/redis/internal/consistenthash/consistenthash.go | |
parent | 6f4e38d129ffaf469d40fc8596d3957ee94d21e9 (diff) | |
download | chat-09b49c26ddfdb20ced61e7dfd4192e750ce40449.tar.gz chat-09b49c26ddfdb20ced61e7dfd4192e750ce40449.tar.bz2 chat-09b49c26ddfdb20ced61e7dfd4192e750ce40449.zip |
PLT-5308 Caching layer part 2 (#6973)
* Adding Reaction store cache layer example
* Implementing reaction store in new caching system.
* Redis for reaction store
* Adding redis library
* Adding invalidation for DeleteAllWithEmojiName and other minor enhancements
Diffstat (limited to 'vendor/github.com/go-redis/redis/internal/consistenthash/consistenthash.go')
-rw-r--r-- | vendor/github.com/go-redis/redis/internal/consistenthash/consistenthash.go | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/vendor/github.com/go-redis/redis/internal/consistenthash/consistenthash.go b/vendor/github.com/go-redis/redis/internal/consistenthash/consistenthash.go new file mode 100644 index 000000000..a9c56f076 --- /dev/null +++ b/vendor/github.com/go-redis/redis/internal/consistenthash/consistenthash.go @@ -0,0 +1,81 @@ +/* +Copyright 2013 Google Inc. + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +// Package consistenthash provides an implementation of a ring hash. +package consistenthash + +import ( + "hash/crc32" + "sort" + "strconv" +) + +type Hash func(data []byte) uint32 + +type Map struct { + hash Hash + replicas int + keys []int // Sorted + hashMap map[int]string +} + +func New(replicas int, fn Hash) *Map { + m := &Map{ + replicas: replicas, + hash: fn, + hashMap: make(map[int]string), + } + if m.hash == nil { + m.hash = crc32.ChecksumIEEE + } + return m +} + +// Returns true if there are no items available. +func (m *Map) IsEmpty() bool { + return len(m.keys) == 0 +} + +// Adds some keys to the hash. +func (m *Map) Add(keys ...string) { + for _, key := range keys { + for i := 0; i < m.replicas; i++ { + hash := int(m.hash([]byte(strconv.Itoa(i) + key))) + m.keys = append(m.keys, hash) + m.hashMap[hash] = key + } + } + sort.Ints(m.keys) +} + +// Gets the closest item in the hash to the provided key. +func (m *Map) Get(key string) string { + if m.IsEmpty() { + return "" + } + + hash := int(m.hash([]byte(key))) + + // Binary search for appropriate replica. + idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash }) + + // Means we have cycled back to the first replica. + if idx == len(m.keys) { + idx = 0 + } + + return m.hashMap[m.keys[idx]] +} |