syncbase: Change id encoding in store keys to preserve sorting.
Changed id encoding in store keys from the wire encoding
encodeName("<blessing>,<name>") to "<blessing>\0<name>\0".
The new encoding preserves the natural sort order (lexicographically,
first by blessing, then by name).
The new encoding removes the need for sorting when scanning databases,
collections, and rows.
Syncgroups use a hash in keys instead; changed syncgroup sort routine
to sort by blessing first instead of name first, added test to confirm.
MultiPart: 2/3
Change-Id: Ia50ec50b8629e924f827af47e04cc6e7e4c1f1db
diff --git a/services/syncbase/common/constants.go b/services/syncbase/common/constants.go
index 5632349..7505315 100644
--- a/services/syncbase/common/constants.go
+++ b/services/syncbase/common/constants.go
@@ -28,6 +28,11 @@
// range. Must be greater than any character allowed in client-specified keys.
PrefixRangeLimitSuffix = "\xff"
+ // IdPartSep is a separator and terminator for id encoding in keys. NUL was
+ // chosen to make ids encoded as <blessing><sep><name><sep> sorted, first by
+ // blessing, then by name.
+ IdPartSep = "\x00"
+
// AppDir is the filesystem directory that holds all app databases.
AppDir = "apps"
diff --git a/services/syncbase/common/key_util.go b/services/syncbase/common/key_util.go
index 0bb1171..889141f 100644
--- a/services/syncbase/common/key_util.go
+++ b/services/syncbase/common/key_util.go
@@ -51,6 +51,24 @@
return SplitNKeyParts(key, 2)[0]
}
+// EncodeIdKeyPart encodes an id for embedding in a store key. No escaping is
+// necessary since valid ids are guaranteed not to contain reserved key bytes
+// such as '\xfe'. Ids are encoded as "<blessing>\x00<name>\x00" to preserve
+// the natural sort order (first by blessing, then by name) even when embedded
+// in store keys.
+func EncodeIdKeyPart(id wire.Id) string {
+ return id.Blessing + IdPartSep + id.Name + IdPartSep
+}
+
+// DecodeIdKeyPart is the inverse of EncodeIdKeyPart.
+func DecodeIdKeyPart(idKeyPart string) (wire.Id, error) {
+ parts := strings.SplitN(idKeyPart, IdPartSep, 3)
+ if len(parts) < 3 || parts[2] != "" {
+ return wire.Id{}, fmt.Errorf("DecodeIdKeyPart: invalid id part %q", idKeyPart)
+ }
+ return wire.Id{Blessing: parts[0], Name: parts[1]}, nil
+}
+
// IsRowKey returns true iff 'key' is a storage engine key for a row.
func IsRowKey(key string) bool {
return FirstKeyPart(key) == RowPrefix
@@ -65,7 +83,7 @@
if len(parts) < 3 || pfx != RowPrefix {
return wire.Id{}, "", fmt.Errorf("ParseRowKey: invalid key %q", key)
}
- cxId, err := util.DecodeId(parts[1])
+ cxId, err := DecodeIdKeyPart(parts[1])
if err != nil {
return wire.Id{}, "", fmt.Errorf("ParseRowKey: invalid collection %q: %v", parts[1], err)
}
@@ -82,7 +100,7 @@
if len(parts) < 3 || pfx != CollectionPermsPrefix || parts[2] != "" {
return wire.Id{}, fmt.Errorf("ParseCollectionPermsKey: invalid key %q", key)
}
- cxId, err := util.DecodeId(parts[1])
+ cxId, err := DecodeIdKeyPart(parts[1])
if err != nil {
return wire.Id{}, fmt.Errorf("ParseCollectionPermsKey: invalid collection %q: %v", parts[1], err)
}
diff --git a/services/syncbase/common/key_util_test.go b/services/syncbase/common/key_util_test.go
index 4c61d7e..62441cb 100644
--- a/services/syncbase/common/key_util_test.go
+++ b/services/syncbase/common/key_util_test.go
@@ -125,27 +125,35 @@
row string
err bool
}{
- {common.RowPrefix + "\xfeu,c\xferow", wire.Id{"u", "c"}, "row", false},
- {common.RowPrefix + "\xfeu,c\xfe", wire.Id{"u", "c"}, "", false},
- {common.RowPrefix + "\xfe,c\xfe", wire.Id{"", "c"}, "", false},
- {common.RowPrefix + "\xfeu,\xfe", wire.Id{"u", ""}, "", false},
- {common.RowPrefix + "\xfe,\xferow", wire.Id{"", ""}, "row", false},
+ {common.RowPrefix + "\xfeu\x00c\x00\xferow", wire.Id{"u", "c"}, "row", false},
+ {common.RowPrefix + "\xfeu\x00c,d\x00\xferow", wire.Id{"u", "c,d"}, "row", false},
+ {common.RowPrefix + "\xfeu\x00c\x00\xferow,x", wire.Id{"u", "c"}, "row,x", false},
+ {common.RowPrefix + "\xfeu\x00c,d\x00\xferow,x", wire.Id{"u", "c,d"}, "row,x", false},
+ {common.RowPrefix + "\xfeu\x00c\x00\xfe", wire.Id{"u", "c"}, "", false},
+ {common.RowPrefix + "\xfe\x00c\x00\xfe", wire.Id{"", "c"}, "", false},
+ {common.RowPrefix + "\xfeu\x00\x00\xfe", wire.Id{"u", ""}, "", false},
+ {common.RowPrefix + "\xfe\x00\x00\xferow", wire.Id{"", ""}, "row", false},
{common.RowPrefix + "\xfe\xferow", wire.Id{}, "", true},
+ {common.RowPrefix + "\xfe\x00\xferow", wire.Id{}, "", true},
{common.RowPrefix + "\xfeuc\xfe", wire.Id{}, "", true},
- {common.CollectionPermsPrefix + "\xfeu,c\xferow", wire.Id{}, "", true},
- {common.CollectionPermsPrefix + "\xfeu,c\xfe", wire.Id{}, "", true},
+ {common.RowPrefix + "\xfeu\x00c\xfe", wire.Id{}, "", true},
+ {common.RowPrefix + "\xfeuc\x00\xfe", wire.Id{}, "", true},
+ {common.CollectionPermsPrefix + "\xfeu\x00c\x00\xferow", wire.Id{}, "", true},
+ {common.CollectionPermsPrefix + "\xfeu\x00c\x00\xfe", wire.Id{}, "", true},
{common.CollectionPermsPrefix + "\xfe\xferow", wire.Id{}, "", true},
{common.CollectionPermsPrefix + "\xfe\xfe", wire.Id{}, "", true},
- {"pfx\xfeu,c\xferow", wire.Id{}, "", true},
- {"pfx\xfeu,c\xfe", wire.Id{}, "", true},
+ {"pfx\xfeu\x00c\x00\xferow", wire.Id{}, "", true},
+ {"pfx\xfeu\x00c\x00\xfe", wire.Id{}, "", true},
{"pfx\xfe\xferow", wire.Id{}, "", true},
{"pfx\xfe\xfe", wire.Id{}, "", true},
- {"\xfeu,c\xferow", wire.Id{}, "", true},
- {"\xfeu,c\xfe", wire.Id{}, "", true},
+ {"\xfeu\x00c\x00\xferow", wire.Id{}, "", true},
+ {"\xfeu\x00c\x00\xfe", wire.Id{}, "", true},
{"\xfe\xferow", wire.Id{}, "", true},
{"\xfe\xfe", wire.Id{}, "", true},
{common.RowPrefix, wire.Id{}, "", true},
- {common.RowPrefix + "\xfeu,c", wire.Id{}, "", true},
+ {common.RowPrefix + "\xfeu\x00c", wire.Id{}, "", true},
+ {common.RowPrefix + "\xfeuc\x00", wire.Id{}, "", true},
+ {common.RowPrefix + "\xfeu\x00c\x00", wire.Id{}, "", true},
{common.RowPrefix + "\xfe", wire.Id{}, "", true},
}
for _, test := range tests {
@@ -168,18 +176,24 @@
collection wire.Id
err bool
}{
- {common.CollectionPermsPrefix + "\xfeu,c\xfe", wire.Id{"u", "c"}, false},
- {common.CollectionPermsPrefix + "\xfeu,\xfe", wire.Id{"u", ""}, false},
- {common.CollectionPermsPrefix + "\xfe,c\xfe", wire.Id{"", "c"}, false},
- {common.CollectionPermsPrefix + "\xfe,\xfe", wire.Id{"", ""}, false},
- {"\xfeu,c\xfe", wire.Id{}, true},
- {"pfx\xfeu,c\xfe", wire.Id{}, true},
- {common.RowPrefix + "\xfeu,c\xfe", wire.Id{}, true},
+ {common.CollectionPermsPrefix + "\xfeu\x00c\x00\xfe", wire.Id{"u", "c"}, false},
+ {common.CollectionPermsPrefix + "\xfeu\x00c,d\x00\xfe", wire.Id{"u", "c,d"}, false},
+ {common.CollectionPermsPrefix + "\xfeu\x00\x00\xfe", wire.Id{"u", ""}, false},
+ {common.CollectionPermsPrefix + "\xfe\x00c\x00\xfe", wire.Id{"", "c"}, false},
+ {common.CollectionPermsPrefix + "\xfe\x00\x00\xfe", wire.Id{"", ""}, false},
+ {"\xfeu\x00c\x00\xfe", wire.Id{}, true},
+ {"pfx\xfeu\x00c\x00\xfe", wire.Id{}, true},
+ {common.RowPrefix + "\xfeu\x00c\x00\xfe", wire.Id{}, true},
{common.CollectionPermsPrefix + "\xfe", wire.Id{}, true},
{common.CollectionPermsPrefix + "\xfe\xfe", wire.Id{}, true},
- {common.CollectionPermsPrefix + "\xfeu,c\xferow", wire.Id{}, true},
- {common.CollectionPermsPrefix + "\xfeu,c", wire.Id{}, true},
+ {common.CollectionPermsPrefix + "\xfe\x00\xfe", wire.Id{}, true},
+ {common.CollectionPermsPrefix + "\xfeu\x00c\x00\xferow", wire.Id{}, true},
+ {common.CollectionPermsPrefix + "\xfeu\x00c\x00", wire.Id{}, true},
+ {common.CollectionPermsPrefix + "\xfeu\x00c", wire.Id{}, true},
+ {common.CollectionPermsPrefix + "\xfeuc\x00", wire.Id{}, true},
+ {common.CollectionPermsPrefix + "\xfeuc", wire.Id{}, true},
{common.CollectionPermsPrefix + "\xfe", wire.Id{}, true},
+ {common.CollectionPermsPrefix + "\xfe\x00", wire.Id{}, true},
}
for _, test := range tests {
collection, err := common.ParseCollectionPermsKey(test.key)
diff --git a/services/syncbase/server/collection.go b/services/syncbase/server/collection.go
index b4041ca..1ff5005 100644
--- a/services/syncbase/server/collection.go
+++ b/services/syncbase/server/collection.go
@@ -10,7 +10,6 @@
"v.io/v23/rpc"
"v.io/v23/security/access"
wire "v.io/v23/services/syncbase"
- pubutil "v.io/v23/syncbase/util"
"v.io/v23/verror"
"v.io/v23/vom"
"v.io/x/ref/services/syncbase/common"
@@ -269,5 +268,5 @@
}
func (c *collectionReq) stKeyPart() string {
- return pubutil.EncodeId(c.id)
+ return common.EncodeIdKeyPart(c.id)
}
diff --git a/services/syncbase/server/db_info.go b/services/syncbase/server/db_info.go
index b3e903b..7b0c656 100644
--- a/services/syncbase/server/db_info.go
+++ b/services/syncbase/server/db_info.go
@@ -15,13 +15,12 @@
import (
"v.io/v23/context"
wire "v.io/v23/services/syncbase"
- pubutil "v.io/v23/syncbase/util"
"v.io/x/ref/services/syncbase/common"
"v.io/x/ref/services/syncbase/store"
)
func dbInfoStKey(dbId wire.Id) string {
- return common.JoinKeyParts(common.DbInfoPrefix, pubutil.EncodeId(dbId))
+ return common.JoinKeyParts(common.DbInfoPrefix, common.EncodeIdKeyPart(dbId))
}
// getDbInfo reads data from the storage engine.
diff --git a/services/syncbase/server/db_info_test.go b/services/syncbase/server/db_info_test.go
index 79e9cd6..b9222f2 100644
--- a/services/syncbase/server/db_info_test.go
+++ b/services/syncbase/server/db_info_test.go
@@ -15,7 +15,7 @@
dbId wire.Id
stKey string
}{
- {wire.Id{Blessing: "app1", Name: "db1"}, "i\xfeapp1,db1"},
+ {wire.Id{Blessing: "app1", Name: "db1"}, "i\xfeapp1\x00db1\x00"},
}
for _, test := range tests {
got, want := dbInfoStKey(test.dbId), test.stKey
diff --git a/services/syncbase/server/util/glob_children.go b/services/syncbase/server/util/glob_children.go
index e2469e2..ffcb0ac 100644
--- a/services/syncbase/server/util/glob_children.go
+++ b/services/syncbase/server/util/glob_children.go
@@ -30,15 +30,10 @@
for it.Advance() {
key = it.Key(key)
parts := common.SplitKeyParts(string(key))
- id, err := pubutil.DecodeId(parts[len(parts)-1])
+ id, err := common.DecodeIdKeyPart(parts[len(parts)-1])
if err != nil {
return verror.New(verror.ErrBadState, ctx, err)
}
- // Note, even though DecodeId followed by EncodeId are currently redundant
- // (other than checking that the key component is a properly encoded Id),
- // the Id encoding in the key will soon change to a different format than
- // the pubutil (wire) encoding.
- // TODO(ivanpi): Implement the new encoding.
encId := pubutil.EncodeId(id)
if matcher.Match(encId) {
// TODO(rogulenko): Check for resolve access. (For collection glob, this
diff --git a/services/syncbase/vsync/initiator_test.go b/services/syncbase/vsync/initiator_test.go
index b8eb1ea..e087f83 100644
--- a/services/syncbase/vsync/initiator_test.go
+++ b/services/syncbase/vsync/initiator_test.go
@@ -427,8 +427,8 @@
}
wantVecs = interfaces.Knowledge{
- "mockuser,foo\xfe": interfaces.GenVector{10: 0},
- "mockuser,bar\xfe": interfaces.GenVector{10: 0},
+ "mockuser\x00foo\x00\xfe": interfaces.GenVector{10: 0},
+ "mockuser\x00bar\x00\xfe": interfaces.GenVector{10: 0},
}
}
diff --git a/services/syncbase/vsync/syncgroup.go b/services/syncbase/vsync/syncgroup.go
index ab20f0a..132a58d 100644
--- a/services/syncbase/vsync/syncgroup.go
+++ b/services/syncbase/vsync/syncgroup.go
@@ -1000,13 +1000,13 @@
s[i], s[j] = s[j], s[i]
}
func (s syncgroups) Less(i, j int) bool {
- if s[i].Name < s[j].Name {
+ if s[i].Blessing < s[j].Blessing {
return true
}
- if s[i].Name > s[j].Name {
+ if s[i].Blessing > s[j].Blessing {
return false
}
- return s[i].Blessing < s[j].Blessing
+ return s[i].Name < s[j].Name
}
func (sd *syncDatabase) ListSyncgroups(ctx *context.T, call rpc.ServerCall) ([]wire.Id, error) {
diff --git a/services/syncbase/vsync/testutil_test.go b/services/syncbase/vsync/testutil_test.go
index 8ab18c5..5f03282 100644
--- a/services/syncbase/vsync/testutil_test.go
+++ b/services/syncbase/vsync/testutil_test.go
@@ -17,7 +17,6 @@
"v.io/v23/rpc"
"v.io/v23/security/access"
wire "v.io/v23/services/syncbase"
- pubutil "v.io/v23/syncbase/util"
"v.io/v23/verror"
"v.io/x/ref/services/syncbase/common"
"v.io/x/ref/services/syncbase/server/interfaces"
@@ -190,12 +189,12 @@
}
func makeRowKeyFromParts(cxBlessing, cxName, row string) string {
- return common.JoinKeyParts(common.RowPrefix, pubutil.EncodeId(wire.Id{cxBlessing, cxName}), row)
+ return common.JoinKeyParts(common.RowPrefix, common.EncodeIdKeyPart(wire.Id{cxBlessing, cxName}), row)
}
func makeCollectionPermsKey(cxBlessing, cxName string) string {
// TODO(rdaoud,ivanpi): See hack in collection.go.
- return common.JoinKeyParts(common.CollectionPermsPrefix, pubutil.EncodeId(wire.Id{cxBlessing, cxName}), "")
+ return common.JoinKeyParts(common.CollectionPermsPrefix, common.EncodeIdKeyPart(wire.Id{cxBlessing, cxName}), "")
}
// conflictResolverStream mock for testing.
diff --git a/services/syncbase/vsync/util.go b/services/syncbase/vsync/util.go
index 5bdc7a0..0c44ba8 100644
--- a/services/syncbase/vsync/util.go
+++ b/services/syncbase/vsync/util.go
@@ -13,7 +13,6 @@
"v.io/v23/rpc"
"v.io/v23/security"
wire "v.io/v23/services/syncbase"
- pubutil "v.io/v23/syncbase/util"
"v.io/v23/verror"
"v.io/x/lib/vlog"
"v.io/x/ref/services/syncbase/common"
@@ -70,7 +69,7 @@
// toCollectionPrefixStr converts a collection id to a string of the form used
// for storing perms and row data in the underlying storage engine.
func toCollectionPrefixStr(c wire.Id) string {
- return common.JoinKeyParts(pubutil.EncodeId(c), "")
+ return common.JoinKeyParts(common.EncodeIdKeyPart(c), "")
}
// toRowKey prepends RowPrefix to what is presumably a "<collection>:<row>"
