GoVector icon indicating copy to clipboard operation
GoVector copied to clipboard

Make ReturnVCString Deterministic

Open pfandzelter opened this issue 3 years ago • 0 comments

Currently when getting the string representation for a vector clock, you will get a non-deterministic order of keys and values. The reason is that ranging over a map in Go gives you its keys in a random order. Nevertheless, the current implementation of ReturnVCString in the vclock package relies on ranging over the keys to sort the output (note that the comment is from the original code):

//sort
ids := make([]string, len(vc))
i := 0
for id := range vc {
	ids[i] = id
	i++
}

So I'm assuming that non-deterministic output is a bug and not intentional.
For some use-cases (notably: my use-case 🙂), this can be problematic. My proposal is to add an additional sort.Strings(ids) step before using the array of keys so that iff v1 == v2 => v1.ReturnVCString() == v2.ReturnVCString(). This should prevent any further surprises.

There is a performance overhead but I find it negligible. For a vector clock with 100 entries (quite large):

goos: darwin
goarch: amd64
pkg: github.com/DistributedClocks/GoVector/govec/vclock
cpu: Intel(R) Core(TM) i5-8210Y CPU @ 1.60GHz
BenchmarkVCString-4         	   28614	     40648 ns/op
BenchmarkVCStringSorted-4   	   20901	     57339 ns/op
PASS
ok  	github.com/DistributedClocks/GoVector/govec/vclock	3.386s

(This benchmark is not included in this PR, just illustrative.)
0.017ms is acceptable, although that difference is grows or shrinks with the size of the clock.

pfandzelter avatar Jul 26 '21 13:07 pfandzelter