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>"