Adding a UUID function that can be used to create sequential but random UUIDs.
Change-Id: Ie550e3c8ee13d7232733d88c8cdcdc12efef52b6
diff --git a/syncbase/key.go b/syncbase/key.go
index 34353af..362631c 100644
--- a/syncbase/key.go
+++ b/syncbase/key.go
@@ -4,7 +4,83 @@
package syncbase
+import (
+ "bytes"
+ "crypto/rand"
+ "encoding/base64"
+ "encoding/binary"
+ "fmt"
+ "sync/atomic"
+ "time"
+)
+
+const (
+ // First character of UUID to make the UUID start with a valid identifier character.
+ // Can be used for versioning.
+ uuidPrefix string = "v"
+ // Legal characters of Java identifiers in ASCII-encoding order.
+ uuidCharacterSet string = "$0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"
+)
+
+var (
+ invocationCounter uint32
+ base64Encoding *base64.Encoding
+)
+
+func init() {
+ base64Encoding = base64.NewEncoding(uuidCharacterSet).WithPadding(base64.NoPadding)
+}
+
+// Resize string 's' to 'length'. The string will be padded with the first character from the
+// uuidCharacterSet if it is too short, and cut off if its too long.
+func resize(s string, length int) string {
+ switch {
+ case len(s) > length:
+ return s[len(s)-length:]
+ case len(s) == length:
+ return s
+ default:
+ for len(s) < length {
+ return uuidCharacterSet[:1] + s
+ }
+ return s
+ }
+}
+
+// UUID generates a sequential and pseudo-random key that can be used as an ID within
+// Syncbase. The generates IDs are of the format [a-zA-z][a-zA-Z0-9$_]{19}
+//
+// A UUID is made up of four parts:
+// - a prefix which gurantees that the generated UUID is a valid variable name in most programming
+// languages
+// - a time component which uses nanosecond precision
+// - a counter component which is used to gurantee ordering between calls
+// - a random component which achieves pseude-randomness
func UUID() string {
- // TODO(kash): Implement me.
- return ""
+ buffer := new(bytes.Buffer)
+
+ // Encode the current time in nanos as an base64-charater string.
+ // The maximum encoded length is 11 characters: 2^63/64^11 < 1
+ currentTime := time.Now().UnixNano()
+ binary.Write(buffer, binary.BigEndian, currentTime)
+ uuidTime := base64Encoding.EncodeToString(buffer.Bytes())
+
+ // Increment the global count of invocations and encde as a 3-character base64 string.
+ // Note that overflows here are fine.
+ buffer.Reset()
+ currentInvocation := atomic.AddUint32(&invocationCounter, 1)
+ binary.Write(buffer, binary.BigEndian, currentInvocation)
+ uuidInvocation := base64Encoding.EncodeToString(buffer.Next(4)[1:])
+
+ // Encode 4 bytes of randomness as base64-string (maximum of 6 characters)
+ random := make([]byte, 4)
+ rand.Read(random)
+ uuidRandNumber := base64Encoding.EncodeToString(random)
+
+ return fmt.Sprintf(
+ "%s%s%s%s",
+ resize(uuidPrefix, 1),
+ resize(uuidTime, 11),
+ resize(uuidInvocation, 2),
+ resize(uuidRandNumber, 6))
}
diff --git a/syncbase/key_test.go b/syncbase/key_test.go
new file mode 100644
index 0000000..3ec9a3a
--- /dev/null
+++ b/syncbase/key_test.go
@@ -0,0 +1,66 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package syncbase_test
+
+import (
+ "regexp"
+ "sort"
+ "testing"
+
+ "v.io/v23/syncbase"
+)
+
+const (
+ uuidLoopIncovations int = 100
+)
+
+func TestUUIDFormat(t *testing.T) {
+ uuid := syncbase.UUID()
+ regexp := regexp.MustCompile("^v[\\$0-9A-Za-z_]{19}$")
+ if !regexp.MatchString(uuid) {
+ t.Error("Incorrect UUID format")
+ }
+}
+
+func TestUUIDCollisions(t *testing.T) {
+ uuidChannel := make(chan string)
+
+ createUUID := func() {
+ uuidChannel <- syncbase.UUID()
+ }
+
+ for i := 0; i < uuidLoopIncovations; i++ {
+ go createUUID()
+ }
+
+ uuidMap := make(map[string]bool)
+
+ for i := 0; i < uuidLoopIncovations; i++ {
+ uuidMap[<-uuidChannel] = true
+ }
+
+ if len(uuidMap) != uuidLoopIncovations {
+ t.Errorf("UUID collision for %d UUIDs", uuidLoopIncovations-len(uuidMap))
+ }
+}
+
+func TestUUIDSequential(t *testing.T) {
+ unsorted := make([]string, 100)
+ sorted := make([]string, 100)
+
+ for i := 0; i < uuidLoopIncovations; i++ {
+ uuid := syncbase.UUID()
+ unsorted[i] = uuid
+ sorted[i] = uuid
+ }
+
+ sort.Strings(sorted)
+
+ for i := 0; i < uuidLoopIncovations; i++ {
+ if unsorted[i] != sorted[i] {
+ t.Errorf("UUID not sorted at position %d", i)
+ }
+ }
+}
