lafikl / consistent Goto Github PK
View Code? Open in Web Editor NEWA Go library that implements Consistent Hashing and Consistent Hashing With Bounded Loads.
License: MIT License
A Go library that implements Consistent Hashing and Consistent Hashing With Bounded Loads.
License: MIT License
Hi lafikl,I found one possible code optimization from your lib.As the following code showed:
delSlice will delete the val from the c.sortedSet in a sequential traversal way.Why not just using binary search to found out the index of val in sortedSet and update the sortedSet?
func (c *Consistent) delSlice(val uint64) {
for i := 0; i < len(c.sortedSet); i++ {
if c.sortedSet[i] == val {
c.sortedSet = append(c.sortedSet[:i], c.sortedSet[i+1:]...)
}
}
}
Maybe like that:
func (c *Consistent) delSlice(val uint64) {
idx := binarySearch(c.sortedSet,val)
if idx != -1 { // if it does exist
c.sortedSet = append(c.sortedSet[:idx], c.sortedSet[idx+1:]...)
}
}
Thanks!
What if 2 hosts will have the same fnv-1 hash?
https://github.com/lafikl/consistent/blob/master/consistent.go#L49
// Consistent.Add method
h := c.hash(fmt.Sprintf("%s%d", host, i))
c.hosts[h] = host
What will be if c.hosts[h]
is not empty? When this host will be removed overridden host will not be restored. So Add/Remove of the same key may change internal state. I think this will break consistency.
PS: Excuse my poor English
Inc should first judge whether the loadMap has a host
c := consistent.New()
c.Add("127.0.0.1")
// Heartbeat detection causes node to be removed...
c.Remove("127.0.0.1")
c.Inc("127.0.0.1") //panic ...
1.consistance.add
==================
WARNING: DATA RACE
Write at 0x00c42019c650 by goroutine 76:
sync/atomic.AddInt64()
/usr/local/Cellar/go/1.8.1/libexec/src/runtime/race_amd64.s:276 +0xb
fs-router/vendor/github.com/lafikl/consistent.(*Consistent).Inc()
/Users/apple/go-dev/src/fs-router/vendor/github.com/lafikl/consistent/consistent.go:149 +0xa8
fs-router/controllers.getHost()
/Users/apple/go-dev/src/fs-router/controllers/hashhost.go:185 +0x34b
fs-router/controllers.load()
/Users/apple/go-dev/src/fs-router/controllers/hashhost.go:200 +0xeb
fs-router/controllers.HashHost()
/Users/apple/go-dev/src/fs-router/controllers/hashhost.go:68 +0x3c
fs-router/controllers.(*HostHashController).GetFileUrl()
/Users/apple/go-dev/src/fs-router/controllers/host_grpc.go:15 +0xd0
fs-router/protos._FileSystemRouterService_GetFileUrl_Handler()
/Users/apple/go-dev/src/fs-router/protos/fs_router.pb.go:286 +0x35a
fs-router/vendor/google.golang.org/grpc.(*Server).processUnaryRPC()
/Users/apple/go-dev/src/fs-router/vendor/google.golang.org/grpc/server.go:776 +0x1221
fs-router/vendor/google.golang.org/grpc.(*Server).handleStream()
/Users/apple/go-dev/src/fs-router/vendor/google.golang.org/grpc/server.go:976 +0x150e
fs-router/vendor/google.golang.org/grpc.(*Server).serveStreams.func1.1()
/Users/apple/go-dev/src/fs-router/vendor/google.golang.org/grpc/server.go:546 +0xb6
I found that default settings of this library performs poor keys distribution over hosts. To improve distribution hosts replication must be at least 1000. Better to make replication factor configurable.
But if replication factor will be so big, then sorted slice (sortedSet
) will be ineffective. You should use binary tree instead to improve add/remove host performance.
fmt.Sprintf("%s%d", host, i)
What if host names will be: host1, host2, ... host21, host22. Current mechanism of replications naming will produce a lot of collisions. Some sort of delimiter is required:
const delimiter = "æ" // some rare utf-8 symbol
...
fmt.Sprintf("%s%s%d", host, delimiter, i)
For example unicode 'SYMBOL FOR UNIT SEPARATOR' may be used: https://www.fileformat.info/info/unicode/char/241f/index.htm
when remove a host, the code doesn't remove the host's load. This will be a problem, when next time compute the average load. Please fix it.
Line 169 in 6e1d11f
Remove host from ring,but didn't remove from loadmap.
If use Hosts() to get all hosts, it return the list generate from the loadmap, not real hosts in the ring.
Whether or not delete the host from loadmap ?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.