CVE-2026-48096

@@ -53,13 +53,19 @@ import (
 	"github.com/openfga/openfga/pkg/typesystem"
 )
 
+var testCachePrefix string
+
 func init() {
 	_, filename, _, _ := runtime.Caller(0)
 	dir := path.Join(path.Dir(filename), "..", "..")
 	err := os.Chdir(dir)
 	if err != nil {
 		panic(err)
 	}
+
+	var builder storage.CacheKeyBuilder
+	builder.WriteString(storagewrappers.V2IteratorCachePrefix)
+	testCachePrefix = builder.Build()
 }
 
 func ExampleNewServerWithOpts() {
@@ -2498,10 +2504,10 @@ func TestV2CheckWithIteratorCache(t *testing.T) {
 
 	initialHits := cache.Hits()
 
-	// Verify iterator cache entries were created (v2ic. prefix) by waiting for
+	// Verify iterator cache entries were created (hex-encoded v2ic. prefix) by waiting for
 	// background cache population with a bounded timeout.
 	require.Eventually(t, func() bool {
-		return len(cache.KeysWithPrefix("v2ic.")) > 0
+		return len(cache.KeysWithPrefix(testCachePrefix)) > 0
 	}, 2*time.Second, 10*time.Millisecond, "V2 iterator cache should have entries after first check")
 
 	// Second check with different user but same userset traversal
@@ -2583,7 +2589,7 @@ func TestV2CheckWithIteratorCache_Invalidation(t *testing.T) {
 
 	// Wait for the iterator cache to be populated.
 	require.Eventually(t, func() bool {
-		return len(cache.KeysWithPrefix("v2ic.")) > 0
+		return len(cache.KeysWithPrefix(testCachePrefix)) > 0
 	}, 2*time.Second, 10*time.Millisecond)
 
 	// Write a DIFFERENT group membership on the same (document:1, viewer).
@@ -2681,11 +2687,11 @@ func TestV2CheckWithIteratorCache_HigherConsistencyBypassesCache(t *testing.T) {
 	require.True(t, checkResponse.GetAllowed())
 
 	require.Eventually(t, func() bool {
-		return len(cache.KeysWithPrefix("v2ic.")) > 0
+		return len(cache.KeysWithPrefix(testCachePrefix)) > 0
 	}, 2*time.Second, 10*time.Millisecond, "default consistency should populate iterator cache")
 
 	// Record cache key count before HIGHER_CONSISTENCY checks.
-	keysCountBefore := len(cache.KeysWithPrefix("v2ic."))
+	keysCountBefore := len(cache.KeysWithPrefix(testCachePrefix))
 
 	// Now make HIGHER_CONSISTENCY requests for a different document/user
 	// to ensure any new cache entries would be distinct from existing ones.
@@ -2701,7 +2707,7 @@ func TestV2CheckWithIteratorCache_HigherConsistencyBypassesCache(t *testing.T) {
 	}
 
 	// HIGHER_CONSISTENCY should not have added any new iterator cache entries.
-	keysCountAfter := len(cache.KeysWithPrefix("v2ic."))
+	keysCountAfter := len(cache.KeysWithPrefix(testCachePrefix))
 	require.Equal(t, keysCountBefore, keysCountAfter, "HIGHER_CONSISTENCY should not populate iterator cache")
 }
 
@@ -2784,15 +2790,26 @@ func TestV2CheckWithIteratorCache_Conditions(t *testing.T) {
 	require.True(t, checkResponse.GetAllowed())
 
 	// Wait for iterator cache to be populated and verify entries exist
-	// with condition hash segments (/c:) in the cache keys.
+	// with a non-empty condition hash segment. In the hex-encoded key format,
+	// condition hashes appear as the last pipe-delimited segment before the
+	// trailing '|'. A non-empty hash means the segment between the last two
+	// '|' chars has length > 0.
 	require.Eventually(t, func() bool {
-		v2CacheKeys := cache.KeysWithPrefix("v2ic.")
+		v2CacheKeys := cache.KeysWithPrefix(testCachePrefix)
 		if len(v2CacheKeys) == 0 {
 			return false
 		}
 		for _, key := range v2CacheKeys {
-			if strings.Contains(key, "/c:") {
-				return true
+			// The conditions hash is the last segment. With 7 segments there are
+			// 7 '|' delimiters. A non-empty last segment means conditions were hashed.
+			segments := strings.Split(key, "|")
+			// segments has len == numWritten+1 because of trailing '|'
+			if len(segments) >= 8 {
+				// second-to-last segment (last real data segment) is the conditions hash
+				condSeg := segments[len(segments)-2]
+				if len(condSeg) > 0 {
+					return true
+				}
 			}
 		}
 		return false

@@ -12,8 +12,10 @@ import (
 	"strconv"
 	"sync"
 	"time"
+	"unsafe"
 
 	"github.com/Yiling-J/theine-go"
+	"github.com/cespare/xxhash/v2"
 	"github.com/prometheus/client_golang/prometheus"
 	"github.com/prometheus/client_golang/prometheus/promauto"
 	"google.golang.org/protobuf/types/known/structpb"
@@ -225,17 +227,34 @@ func GetInvalidIteratorCacheKey(storeID string) string {
 }
 
 func GetInvalidIteratorByObjectRelationCacheKey(storeID, object, relation string) string {
-	return invalidIteratorCachePrefix + storeID + "-or/" + object + "#" + relation
+	var builder CacheKeyBuilder
+	builder.Grow(5) // grown by the number of elements to be written to the builder
+
+	builder.WriteString(invalidIteratorCachePrefix)
+	builder.WriteString("or")
+	builder.WriteString(storeID)
+	builder.WriteString(object)
+	builder.WriteString(relation)
+
+	return builder.Build()
 }
 
 func GetInvalidIteratorByUserObjectTypeCacheKeys(storeID string, users []string, objectType string) []string {
-	res := make([]string, len(users))
-	var i int
-	for _, user := range users {
-		res[i] = invalidIteratorCachePrefix + storeID + "-otr/" + user + "|" + objectType
-		i++
+	result := make([]string, len(users))
+
+	for i, user := range users {
+		var builder CacheKeyBuilder
+		builder.Grow(5) // grown by the number of elements to be written to the builder
+
+		builder.WriteString(invalidIteratorCachePrefix)
+		builder.WriteString("otr")
+		builder.WriteString(storeID)
+		builder.WriteString(user)
+		builder.WriteString(objectType)
+
+		result[i] = builder.Build()
 	}
-	return res
+	return result
 }
 
 type TupleIteratorCacheEntry struct {
@@ -247,16 +266,33 @@ func (t *TupleIteratorCacheEntry) CacheEntityType() string {
 	return "tuple_iterator"
 }
 
-func GetReadUsersetTuplesCacheKeyPrefix(store, object, relation string) string {
-	return iteratorCachePrefix + "rut/" + store + "/" + object + "#" + relation
+func GetReadUsersetTuplesCacheKeyPrefix(builder *CacheKeyBuilder, store, object, relation string) {
+	builder.Grow(5) // grown by the number of elements to be written to the builder
+
+	builder.WriteString(iteratorCachePrefix)
+	builder.WriteString("rut")
+	builder.WriteString(store)
+	builder.WriteString(object)
+	builder.WriteString(relation)
 }
 
-func GetReadStartingWithUserCacheKeyPrefix(store, objectType, relation string) string {
-	return iteratorCachePrefix + "rtwu/" + store + "/" + objectType + "#" + relation
+func GetReadStartingWithUserCacheKeyPrefix(builder *CacheKeyBuilder, store, objectType, relation string) {
+	builder.Grow(5) // grown by the number of elements to be written to the builder
+
+	builder.WriteString(iteratorCachePrefix)
+	builder.WriteString("rtwu")
+	builder.WriteString(store)
+	builder.WriteString(objectType)
+	builder.WriteString(relation)
 }
 
-func GetReadCacheKey(store, tuple string) string {
-	return iteratorCachePrefix + "r/" + store + "/" + tuple
+func GetReadCacheKey(builder *CacheKeyBuilder, store, tuple string) {
+	builder.Grow(4) // grown by the number of elements to be written to the builder
+
+	builder.WriteString(iteratorCachePrefix)
+	builder.WriteString("r")
+	builder.WriteString(store)
+	builder.WriteString(tuple)
 }
 
 // ErrUnexpectedStructValue is an error used to indicate that
@@ -541,3 +577,83 @@ func WriteInvariantCheckCacheKey(w io.StringWriter, params *CheckCacheKeyParams)
 
 	return nil
 }
+
+const hextable string = "0123456789ABCDEF"
+
+type CacheKeyBuilder struct {
+	buf [][]byte
+}
+
+func (b *CacheKeyBuilder) Grow(n int) {
+	if cap(b.buf) < n {
+		buf := make([][]byte, len(b.buf), n)
+		copy(buf, b.buf)
+		b.buf = buf
+	}
+}
+
+func (b *CacheKeyBuilder) Write(val []byte) (int, error) {
+	b.buf = append(b.buf, val)
+	return len(val), nil
+}
+
+func (b *CacheKeyBuilder) WriteString(val string) (int, error) {
+	return b.Write(unsafe.Slice(unsafe.StringData(val), len(val)))
+}
+
+// Build hex-encodes each written value and separates them with '|'.
+// The output alphabet is [0-9A-F|], which makes it injection-proof: no crafted
+// input can produce a '|', so segments can never collide across boundaries.
+// Tradeoff: keys are 2x larger than raw concatenation, increasing cache memory usage.
+func (b *CacheKeyBuilder) Build() string {
+	var count int
+	for _, buf := range b.buf {
+		count += len(buf)*2 + 1
+	}
+	hex := make([]byte, count)
+	var j int
+	for _, buf := range b.buf {
+		for i := range len(buf) {
+			hex[j] = hextable[buf[i]>>4]
+			j++
+			hex[j] = hextable[buf[i]&0x0F]
+			j++
+		}
+		hex[j] = '|'
+		j++
+	}
+	// unsafe.String: safe because hex is a local buffer never mutated after this point.
+	return unsafe.String(unsafe.SliceData(hex), len(hex))
+}
+
+// BuildUserTypeRestrictionsHash creates a deterministic xxhash digest from user type restrictions.
+// Each restriction is formatted as "type", "type:*", or "type#relation", then sorted and
+// hashed with null-byte separators. Returns the hash as a []byte.
+func BuildUserTypeRestrictionsHash(refs []*openfgav1.RelationReference) []byte {
+	if len(refs) == 0 {
+		return []byte{}
+	}
+
+	parts := make([]string, 0, len(refs))
+	for _, ref := range refs {
+		var part string
+		switch r := ref.GetRelationOrWildcard().(type) {
+		case *openfgav1.RelationReference_Relation:
+			part = ref.GetType() + "#" + r.Relation
+		case *openfgav1.RelationReference_Wildcard:
+			part = ref.GetType() + ":*"
+		default:
+			part = ref.GetType()
+		}
+		parts = append(parts, part)
+	}
+
+	sort.Strings(parts)
+
+	var hasher xxhash.Digest
+	for _, part := range parts {
+		hasher.WriteString(part)
+		hasher.Write([]byte{0})
+	}
+	return hasher.Sum([]byte{})
+}

@@ -23,6 +23,17 @@ import (
 	"github.com/openfga/openfga/pkg/tuple"
 )
 
+func BuildCacheKey(vals ...string) string {
+	var builder CacheKeyBuilder
+	builder.Grow(len(vals))
+
+	for _, val := range vals {
+		builder.WriteString(val)
+	}
+
+	return builder.Build()
+}
+
 // MustNewStruct returns a new *structpb.Struct or panics
 // on error. The new *structpb.Struct value is built from
 // the map m.
@@ -1292,3 +1303,70 @@ func TestJitteredTTL(t *testing.T) {
 		require.Equal(t, time.Duration(math.MaxInt64), result)
 	})
 }
+
+func TestBuildCacheKey(t *testing.T) {
+	t.Run("different_segments_produce_different_keys", func(t *testing.T) {
+		require.NotEqual(t, BuildCacheKey("a", "bc"), BuildCacheKey("ab", "c"))
+		require.NotEqual(t, BuildCacheKey("a", "b"), BuildCacheKey("a", "b", ""))
+	})
+
+	t.Run("identical_inputs_produce_identical_keys", func(t *testing.T) {
+		first := BuildCacheKey("foo", "bar")
+		second := BuildCacheKey("foo", "bar")
+		require.Equal(t, first, second)
+	})
+
+	t.Run("empty_input", func(t *testing.T) {
+		require.Equal(t, "|", BuildCacheKey(""))
+	})
+
+	t.Run("no_args", func(t *testing.T) {
+		require.Empty(t, BuildCacheKey())
+	})
+}
+
+func TestCacheKeyCollisionPrevention(t *testing.T) {
+	store := "01AAAAAAAAAAAAAAAAAAAAAAAA"
+
+	t.Run("ReadUsersetTuples_PoC_from_report", func(t *testing.T) {
+		var builder1 CacheKeyBuilder
+		GetReadUsersetTuplesCacheKeyPrefix(&builder1, store, "doc:1", "viewer")
+
+		var builder2 CacheKeyBuilder
+		GetReadUsersetTuplesCacheKeyPrefix(&builder2, store, "doc:1#viewer/group", "member")
+
+		require.NotEqual(t, builder1.Build(), builder2.Build())
+	})
+
+	t.Run("InvalidIteratorByObjectRelation_delimiter_in_object", func(t *testing.T) {
+		k1 := GetInvalidIteratorByObjectRelationCacheKey(store, "doc:1", "viewer")
+		k2 := GetInvalidIteratorByObjectRelationCacheKey(store, "doc:1#viewer", "")
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("InvalidIteratorByUserObjectType_delimiter_in_user", func(t *testing.T) {
+		k1 := GetInvalidIteratorByUserObjectTypeCacheKeys(store, []string{"user:alice|group"}, "doc")
+		k2 := GetInvalidIteratorByUserObjectTypeCacheKeys(store, []string{"user:alice"}, "group|doc")
+		require.NotEqual(t, k1[0], k2[0])
+	})
+
+	t.Run("ReadCacheKey_delimiter_in_tuple", func(t *testing.T) {
+		var builder1 CacheKeyBuilder
+		GetReadCacheKey(&builder1, store, "doc:1#viewer@user:alice")
+
+		var builder2 CacheKeyBuilder
+		GetReadCacheKey(&builder2, store, "doc:1#viewer@user:alice/extra")
+
+		require.NotEqual(t, builder1.Build(), builder2.Build())
+	})
+
+	t.Run("ReadStartingWithUser_delimiter_in_objectType", func(t *testing.T) {
+		var builder1 CacheKeyBuilder
+		GetReadStartingWithUserCacheKeyPrefix(&builder1, store, "doc", "viewer")
+
+		var builder2 CacheKeyBuilder
+		GetReadStartingWithUserCacheKeyPrefix(&builder2, store, "doc#viewer", "")
+
+		require.NotEqual(t, builder1.Build(), builder2.Build())
+	})
+}

@@ -3,10 +3,10 @@ package storagewrappers
 import (
 	"context"
 	"sort"
-	"strings"
 	"sync"
 	"time"
 
+	"github.com/cespare/xxhash/v2"
 	"go.opentelemetry.io/otel"
 	"go.opentelemetry.io/otel/attribute"
 	"go.opentelemetry.io/otel/trace"
@@ -297,105 +297,59 @@ func (c *CachedTupleReader) ReadPage(ctx context.Context, store string, filter s
 // ─────────────────────────────────────────────────────────────────────────────
 
 // buildReadUsersetTuplesCacheKey builds a cache key for ReadUsersetTuples.
-// Format: v2ic.rut/{storeID}/{object}#{relation}/{userTypeRestrictions}[/c:{conditionsHash}].
 func buildReadUsersetTuplesCacheKey(storeID string, filter storage.ReadUsersetTuplesFilter) string {
-	var b strings.Builder
-	b.Grow(128)
-
-	b.WriteString(v2IteratorCachePrefix)
-	b.WriteString("rut/") // "ReadUsersetTuples"
-	b.WriteString(storeID)
-	b.WriteByte('/')
-	b.WriteString(filter.Object) // e.g., "document:1"
-	b.WriteByte('#')
-	b.WriteString(filter.Relation) // e.g., "viewer"
-	b.WriteByte('/')
-
-	// Build user type restrictions string
-	restrictions := buildUserTypeRestrictionsString(filter.AllowedUserTypeRestrictions)
-	b.WriteString(restrictions)
-
-	// Add conditions hash
-	appendConditionsHash(&b, filter.Conditions)
-
-	return b.String()
+	restrictions := storage.BuildUserTypeRestrictionsHash(filter.AllowedUserTypeRestrictions)
+	conditions := generateConditionsHash(filter.Conditions)
+
+	var builder storage.CacheKeyBuilder
+	builder.Grow(7) // grown by the number of elements to be written to the builder
+
+	builder.WriteString(V2IteratorCachePrefix)
+	builder.WriteString("rut")
+	builder.WriteString(storeID)
+	builder.WriteString(filter.Object)
+	builder.WriteString(filter.Relation)
+	builder.Write(restrictions)
+	builder.Write(conditions)
+
+	return builder.Build()
 }
 
 // buildReadCacheKey builds a cache key for Read.
-// Format: v2ic.r/{storeID}/{object}#{relation}/{userPrefix}[/c:{conditionsHash}].
 func buildReadCacheKey(storeID string, filter storage.ReadFilter) string {
-	var b strings.Builder
-	b.Grow(128)
-
-	b.WriteString(v2IteratorCachePrefix)
-	b.WriteString("r/") // "Read"
-	b.WriteString(storeID)
-	b.WriteByte('/')
-	b.WriteString(filter.Object) // e.g., "document:1"
-	b.WriteByte('#')
-	b.WriteString(filter.Relation) // e.g., "parent"
-	b.WriteByte('/')
-	b.WriteString(filter.User) // e.g., "folder:" (type prefix)
-
-	// Add conditions hash
-	appendConditionsHash(&b, filter.Conditions)
-
-	return b.String()
+	conditions := generateConditionsHash(filter.Conditions)
+
+	var builder storage.CacheKeyBuilder
+	builder.Grow(7) // grown by the number of elements to be written to the builder
+
+	builder.WriteString(V2IteratorCachePrefix)
+	builder.WriteString("r")
+	builder.WriteString(storeID)
+	builder.WriteString(filter.Object)
+	builder.WriteString(filter.Relation)
+	builder.WriteString(filter.User)
+	builder.Write(conditions)
+
+	return builder.Build()
 }
 
 // buildReadStartingWithUserCacheKey builds a cache key for ReadStartingWithUser.
-// Format: v2ic.rswu/{storeID}/{objectType}#{relation}/{users}[/c:{conditionsHash}].
 func buildReadStartingWithUserCacheKey(storeID string, filter storage.ReadStartingWithUserFilter) string {
-	var b strings.Builder
-	b.Grow(128)
-
-	b.WriteString(v2IteratorCachePrefix)
-	b.WriteString("rswu/") // "ReadStartingWithUser"
-	b.WriteString(storeID)
-	b.WriteByte('/')
-	b.WriteString(filter.ObjectType) // e.g., "document"
-	b.WriteByte('#')
-	b.WriteString(filter.Relation) // e.g., "viewer"
-	b.WriteByte('/')
-
-	// Build user filter string
 	users := buildUserFilterString(filter.UserFilter)
-	b.WriteString(users)
+	conditions := generateConditionsHash(filter.Conditions)
 
-	// Add conditions hash
-	appendConditionsHash(&b, filter.Conditions)
+	var builder storage.CacheKeyBuilder
+	builder.Grow(7) // grown by the number of elements to be written to the builder
 
-	return b.String()
-}
+	builder.WriteString(V2IteratorCachePrefix)
+	builder.WriteString("rswu")
+	builder.WriteString(storeID)
+	builder.WriteString(filter.ObjectType)
+	builder.WriteString(filter.Relation)
+	builder.Write(users)
+	builder.Write(conditions)
 
-// buildUserTypeRestrictionsString creates a deterministic string from user type restrictions.
-// Examples:
-//   - [{Type:"user"}] -> "user"
-//   - [{Type:"user", Wildcard:true}] -> "user:*"
-//   - [{Type:"group", Relation:"member"}] -> "group#member"
-//   - Multiple: sorted and joined with ","
-func buildUserTypeRestrictionsString(refs []*openfgav1.RelationReference) string {
-	if len(refs) == 0 {
-		return ""
-	}
-
-	parts := make([]string, 0, len(refs))
-	for _, ref := range refs {
-		var part string
-		switch r := ref.GetRelationOrWildcard().(type) {
-		case *openfgav1.RelationReference_Relation:
-			part = ref.GetType() + "#" + r.Relation
-		case *openfgav1.RelationReference_Wildcard:
-			part = ref.GetType() + ":*"
-		default:
-			part = ref.GetType()
-		}
-		parts = append(parts, part)
-	}
-
-	// Sort for deterministic key
-	sort.Strings(parts)
-	return strings.Join(parts, ",")
+	return builder.Build()
 }
 
 // buildUserFilterString creates a deterministic string from user filters.
@@ -404,9 +358,9 @@ func buildUserTypeRestrictionsString(refs []*openfgav1.RelationReference) string
 //   - [{Object:"user:alice", Relation:"member"}] -> "user:alice#member"
 //   - [{Object:"user:*"}] -> "user:*"
 //   - Multiple: sorted and joined with ","
-func buildUserFilterString(filters []*openfgav1.ObjectRelation) string {
+func buildUserFilterString(filters []*openfgav1.ObjectRelation) []byte {
 	if len(filters) == 0 {
-		return ""
+		return []byte{}
 	}
 
 	parts := make([]string, 0, len(filters))
@@ -420,5 +374,11 @@ func buildUserFilterString(filters []*openfgav1.ObjectRelation) string {
 
 	// Sort for deterministic key
 	sort.Strings(parts)
-	return strings.Join(parts, ",")
+
+	var hasher xxhash.Digest
+	for _, c := range parts {
+		_, _ = hasher.WriteString(c)
+		_, _ = hasher.Write([]byte{0})
+	}
+	return hasher.Sum([]byte{})
 }

@@ -4,11 +4,11 @@ import (
 	"context"
 	"errors"
 	"sort"
-	"strconv"
 	"strings"
 	"sync"
 	"sync/atomic"
 	"time"
+	"unsafe"
 
 	"github.com/cespare/xxhash/v2"
 	"github.com/prometheus/client_golang/prometheus"
@@ -27,7 +27,7 @@ import (
 // ─────────────────────────────────────────────────────────────────────────────
 
 const (
-	v2IteratorCachePrefix = "v2ic."
+	V2IteratorCachePrefix = "v2ic."
 	maxCachedElements     = 1000
 	// InitialBufferCapacity is the default initial capacity for tuple buffers.
 	// Most queries return fewer than 100 tuples, so this avoids over-allocation
@@ -474,34 +474,34 @@ func (c *LockFreeCachedIterator) reconstruct(e *MinimalCacheEntry) *openfgav1.Tu
 // Cache Key Helpers
 // ─────────────────────────────────────────────────────────────────────────────
 
-// appendConditionsHash adds a hash of condition names to the key builder.
-func appendConditionsHash(b *strings.Builder, conditions []string) {
-	if len(conditions) == 0 {
-		return
+// generateConditionsHash returns an ordered string concatenation of condition names to the key builder.
+func generateConditionsHash(conditions []string) []byte {
+	var count int
+	for _, s := range conditions {
+		count += len(s) + 1
 	}
 
-	// Filter out empty/NoCond
-	filtered := make([]string, 0, len(conditions))
-	for _, c := range conditions {
-		if c != "" {
-			filtered = append(filtered, c)
-		}
+	if count == 0 {
+		return []byte{}
 	}
 
-	if len(filtered) == 0 {
-		return
-	}
+	sorted := make([]string, len(conditions))
+	copy(sorted, conditions)
 
-	// Sort for deterministic hash
-	sort.Strings(filtered)
+	// sort ensures a stable hash digest
+	sort.Strings(sorted)
 
-	// Hash condition names
-	hasher := xxhash.New()
-	for _, c := range filtered {
-		_, _ = hasher.WriteString(c)
-		_, _ = hasher.WriteString("|") // Separator to avoid collisions
+	filtered := make([]byte, count)
+	var w int
+	for _, c := range sorted {
+		if c != "" {
+			w += copy(filtered[w:], unsafe.Slice(unsafe.StringData(c), len(c)))
+		}
+		filtered[w] = 0x00
+		w++
 	}
 
-	b.WriteString("/c:")
-	b.WriteString(strconv.FormatUint(hasher.Sum64(), 10))
+	var hasher xxhash.Digest
+	hasher.Write(filtered)
+	return hasher.Sum([]byte{})
 }

@@ -4,7 +4,6 @@ import (
 	"context"
 	"fmt"
 	"strconv"
-	"strings"
 	"sync"
 	"testing"
 	"time"
@@ -1202,10 +1201,17 @@ func TestBuildReadUsersetTuplesCacheKey_Basic(t *testing.T) {
 
 	key := buildReadUsersetTuplesCacheKey("store123", filter)
 
-	require.Contains(t, key, "v2ic.rut/")
-	require.Contains(t, key, "store123")
-	require.Contains(t, key, "document:1#viewer")
-	require.Contains(t, key, "group#member")
+	require.NotEmpty(t, key)
+
+	differentObject := filter
+	differentObject.Object = "document:2"
+	require.NotEqual(t, key, buildReadUsersetTuplesCacheKey("store123", differentObject))
+
+	differentRelation := filter
+	differentRelation.Relation = "editor"
+	require.NotEqual(t, key, buildReadUsersetTuplesCacheKey("store123", differentRelation))
+
+	require.NotEqual(t, key, buildReadUsersetTuplesCacheKey("store456", filter))
 }
 
 func TestBuildReadUsersetTuplesCacheKey_WithConditions(t *testing.T) {
@@ -1220,8 +1226,9 @@ func TestBuildReadUsersetTuplesCacheKey_WithConditions(t *testing.T) {
 
 	key := buildReadUsersetTuplesCacheKey("store123", filter)
 
-	require.Contains(t, key, "v2ic.rut/")
-	require.Contains(t, key, "/c:") // Conditions hash
+	withoutConditions := filter
+	withoutConditions.Conditions = nil
+	require.NotEqual(t, key, buildReadUsersetTuplesCacheKey("store123", withoutConditions))
 }
 
 func TestBuildReadUsersetTuplesCacheKey_Wildcard(t *testing.T) {
@@ -1235,7 +1242,14 @@ func TestBuildReadUsersetTuplesCacheKey_Wildcard(t *testing.T) {
 
 	key := buildReadUsersetTuplesCacheKey("store123", filter)
 
-	require.Contains(t, key, "user:*")
+	filterWithRelation := storage.ReadUsersetTuplesFilter{
+		Object:   "document:1",
+		Relation: "viewer",
+		AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+			{Type: "user", RelationOrWildcard: &openfgav1.RelationReference_Relation{Relation: "member"}},
+		},
+	}
+	require.NotEqual(t, key, buildReadUsersetTuplesCacheKey("store123", filterWithRelation))
 }
 
 func TestBuildReadCacheKey_Basic(t *testing.T) {
@@ -1247,10 +1261,15 @@ func TestBuildReadCacheKey_Basic(t *testing.T) {
 
 	key := buildReadCacheKey("store123", filter)
 
-	require.Contains(t, key, "v2ic.r/")
-	require.Contains(t, key, "store123")
-	require.Contains(t, key, "document:1#parent")
-	require.Contains(t, key, "folder:")
+	require.NotEmpty(t, key)
+
+	differentObject := filter
+	differentObject.Object = "document:2"
+	require.NotEqual(t, key, buildReadCacheKey("store123", differentObject))
+
+	differentUser := filter
+	differentUser.User = "group:"
+	require.NotEqual(t, key, buildReadCacheKey("store123", differentUser))
 }
 
 func TestBuildReadCacheKey_WithConditions(t *testing.T) {
@@ -1263,7 +1282,9 @@ func TestBuildReadCacheKey_WithConditions(t *testing.T) {
 
 	key := buildReadCacheKey("store123", filter)
 
-	require.Contains(t, key, "/c:")
+	withoutConditions := filter
+	withoutConditions.Conditions = nil
+	require.NotEqual(t, key, buildReadCacheKey("store123", withoutConditions))
 }
 
 func TestBuildReadStartingWithUserCacheKey_Basic(t *testing.T) {
@@ -1277,10 +1298,11 @@ func TestBuildReadStartingWithUserCacheKey_Basic(t *testing.T) {
 
 	key := buildReadStartingWithUserCacheKey("store123", filter)
 
-	require.Contains(t, key, "v2ic.rswu/")
-	require.Contains(t, key, "store123")
-	require.Contains(t, key, "document#viewer")
-	require.Contains(t, key, "user:alice")
+	require.NotEmpty(t, key)
+
+	differentType := filter
+	differentType.ObjectType = "folder"
+	require.NotEqual(t, key, buildReadStartingWithUserCacheKey("store123", differentType))
 }
 
 func TestBuildReadStartingWithUserCacheKey_MultipleUsers(t *testing.T) {
@@ -1295,8 +1317,15 @@ func TestBuildReadStartingWithUserCacheKey_MultipleUsers(t *testing.T) {
 
 	key := buildReadStartingWithUserCacheKey("store123", filter)
 
-	// Users should be sorted
-	require.Contains(t, key, "user:alice,user:bob")
+	filterReversed := storage.ReadStartingWithUserFilter{
+		ObjectType: "document",
+		Relation:   "viewer",
+		UserFilter: []*openfgav1.ObjectRelation{
+			{Object: "user:alice"},
+			{Object: "user:bob"},
+		},
+	}
+	require.Equal(t, key, buildReadStartingWithUserCacheKey("store123", filterReversed))
 }
 
 func TestBuildReadStartingWithUserCacheKey_WithRelation(t *testing.T) {
@@ -1310,7 +1339,53 @@ func TestBuildReadStartingWithUserCacheKey_WithRelation(t *testing.T) {
 
 	key := buildReadStartingWithUserCacheKey("store123", filter)
 
-	require.Contains(t, key, "group:eng#member")
+	filterWithoutRelation := storage.ReadStartingWithUserFilter{
+		ObjectType: "document",
+		Relation:   "viewer",
+		UserFilter: []*openfgav1.ObjectRelation{
+			{Object: "group:eng"},
+		},
+	}
+	require.NotEqual(t, key, buildReadStartingWithUserCacheKey("store123", filterWithoutRelation))
+}
+
+func TestBuildCacheKey_CollisionPrevention(t *testing.T) {
+	store := "01AAAAAAAAAAAAAAAAAAAAAAAA"
+
+	t.Run("ReadUsersetTuples_PoC_from_report", func(t *testing.T) {
+		q1 := buildReadUsersetTuplesCacheKey(store, storage.ReadUsersetTuplesFilter{
+			Object:   "doc:1",
+			Relation: "viewer",
+			AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+				{Type: "group", RelationOrWildcard: &openfgav1.RelationReference_Relation{Relation: "member"}},
+			},
+		})
+		q2 := buildReadUsersetTuplesCacheKey(store, storage.ReadUsersetTuplesFilter{
+			Object:   "doc:1#viewer/group",
+			Relation: "member",
+		})
+		require.NotEqual(t, q1, q2)
+	})
+
+	t.Run("Read_delimiter_in_object", func(t *testing.T) {
+		k1 := buildReadCacheKey(store, storage.ReadFilter{
+			Object: "doc:1", Relation: "viewer", User: "user:alice",
+		})
+		k2 := buildReadCacheKey(store, storage.ReadFilter{
+			Object: "doc:1#viewer", Relation: "", User: "user:alice",
+		})
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("ReadStartingWithUser_delimiter_in_objectType", func(t *testing.T) {
+		k1 := buildReadStartingWithUserCacheKey(store, storage.ReadStartingWithUserFilter{
+			ObjectType: "doc", Relation: "viewer",
+		})
+		k2 := buildReadStartingWithUserCacheKey(store, storage.ReadStartingWithUserFilter{
+			ObjectType: "doc#viewer", Relation: "",
+		})
+		require.NotEqual(t, k1, k2)
+	})
 }
 
 func TestCacheKey_Deterministic(t *testing.T) {
@@ -1333,51 +1408,51 @@ func TestCacheKey_Deterministic(t *testing.T) {
 	require.Equal(t, key2, key3)
 }
 
-func TestBuildUserTypeRestrictionsString(t *testing.T) {
+func TestBuildUserTypeRestrictionsHash(t *testing.T) {
 	tests := []struct {
 		name     string
 		refs     []*openfgav1.RelationReference
-		expected string
+		expected []byte
 	}{
 		{
 			name:     "empty",
 			refs:     nil,
-			expected: "",
+			expected: []byte{},
 		},
 		{
 			name: "single_type",
 			refs: []*openfgav1.RelationReference{
 				{Type: "user"},
 			},
-			expected: "user",
+			expected: []byte{0x65, 0x52, 0x5, 0xbe, 0xa9, 0x4f, 0x7d, 0xa7},
 		},
 		{
 			name: "wildcard",
 			refs: []*openfgav1.RelationReference{
 				{Type: "user", RelationOrWildcard: &openfgav1.RelationReference_Wildcard{}},
 			},
-			expected: "user:*",
+			expected: []byte{0x70, 0x6f, 0x67, 0xe2, 0x78, 0xda, 0x3b, 0x61},
 		},
 		{
 			name: "relation",
 			refs: []*openfgav1.RelationReference{
 				{Type: "group", RelationOrWildcard: &openfgav1.RelationReference_Relation{Relation: "member"}},
 			},
-			expected: "group#member",
+			expected: []byte{0x7c, 0x64, 0x23, 0xcb, 0xdb, 0x70, 0x37, 0xe3},
 		},
 		{
 			name: "multiple_sorted",
 			refs: []*openfgav1.RelationReference{
 				{Type: "user"},
 				{Type: "group", RelationOrWildcard: &openfgav1.RelationReference_Relation{Relation: "member"}},
 			},
-			expected: "group#member,user",
+			expected: []byte{0x81, 0xf1, 0x10, 0x2f, 0x7e, 0xb3, 0xb3, 0x66},
 		},
 	}
 
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
-			result := buildUserTypeRestrictionsString(tt.refs)
+			result := storage.BuildUserTypeRestrictionsHash(tt.refs)
 			require.Equal(t, tt.expected, result)
 		})
 	}
@@ -1387,34 +1462,34 @@ func TestBuildUserFilterString(t *testing.T) {
 	tests := []struct {
 		name     string
 		filters  []*openfgav1.ObjectRelation
-		expected string
+		expected []byte
 	}{
 		{
 			name:     "empty",
 			filters:  nil,
-			expected: "",
+			expected: []byte{},
 		},
 		{
 			name: "single_object",
 			filters: []*openfgav1.ObjectRelation{
 				{Object: "user:alice"},
 			},
-			expected: "user:alice",
+			expected: []byte{0x18, 0x58, 0xad, 0x5a, 0x15, 0x29, 0x6c, 0x1b},
 		},
 		{
 			name: "with_relation",
 			filters: []*openfgav1.ObjectRelation{
 				{Object: "group:eng", Relation: "member"},
 			},
-			expected: "group:eng#member",
+			expected: []byte{0x42, 0x16, 0x92, 0xbb, 0x12, 0xdb, 0x48, 0x86},
 		},
 		{
 			name: "multiple_sorted",
 			filters: []*openfgav1.ObjectRelation{
 				{Object: "user:bob"},
 				{Object: "user:alice"},
 			},
-			expected: "user:alice,user:bob",
+			expected: []byte{0x85, 0xc9, 0xae, 0x69, 0xbe, 0xe4, 0xd7, 0xb3},
 		},
 	}
 
@@ -1426,30 +1501,26 @@ func TestBuildUserFilterString(t *testing.T) {
 	}
 }
 
-func TestAppendConditionsHash(t *testing.T) {
-	t.Run("empty_conditions", func(t *testing.T) {
-		var b strings.Builder
-		appendConditionsHash(&b, nil)
-		require.Empty(t, b.String())
+func TestGenerateConditionsHash(t *testing.T) {
+	t.Run("nil_conditions", func(t *testing.T) {
+		s := generateConditionsHash(nil)
+		require.Empty(t, s)
 	})
 
 	t.Run("empty_string_conditions", func(t *testing.T) {
-		var b strings.Builder
-		appendConditionsHash(&b, []string{""})
-		require.Empty(t, b.String())
+		s := generateConditionsHash([]string{""})
+		require.NotEmpty(t, s)
 	})
 
 	t.Run("with_conditions", func(t *testing.T) {
-		var b strings.Builder
-		appendConditionsHash(&b, []string{"cond1", "cond2"})
-		require.Contains(t, b.String(), "/c:")
+		s := generateConditionsHash([]string{"cond1", "cond2"})
+		require.NotEmpty(t, s)
 	})
 
 	t.Run("deterministic", func(t *testing.T) {
-		var b1, b2 strings.Builder
-		appendConditionsHash(&b1, []string{"cond2", "cond1"})
-		appendConditionsHash(&b2, []string{"cond1", "cond2"})
-		require.Equal(t, b1.String(), b2.String())
+		s1 := generateConditionsHash([]string{"cond2", "cond1"})
+		s2 := generateConditionsHash([]string{"cond1", "cond2"})
+		require.Equal(t, s1, s2)
 	})
 }
 

@@ -1,9 +1,6 @@
 package storagewrappersutil
 
 import (
-	"strconv"
-	"strings"
-
 	"github.com/cespare/xxhash/v2"
 
 	openfgav1 "github.com/openfga/api/proto/openfga/v1"
@@ -23,67 +20,49 @@ func ReadStartingWithUserKey(
 	store string,
 	filter storage.ReadStartingWithUserFilter,
 ) (string, error) {
-	var b strings.Builder
-	b.WriteString(
-		storage.GetReadStartingWithUserCacheKeyPrefix(store, filter.ObjectType, filter.Relation),
-	)
+	var builder storage.CacheKeyBuilder
+	storage.GetReadStartingWithUserCacheKeyPrefix(&builder, store, filter.ObjectType, filter.Relation)
+
+	size := len(filter.UserFilter)
+	if filter.ObjectIDs != nil {
+		size++
+	}
+
+	builder.Grow(size)
 
-	// NOTE: There is no need to limit the length of this
-	// since at most it will have 2 entries (user and wildcard if possible)
 	for _, objectRel := range filter.UserFilter {
 		subject := objectRel.GetObject()
 		if objectRel.GetRelation() != "" {
 			subject = tuple.ToObjectRelationString(objectRel.GetObject(), objectRel.GetRelation())
 		}
-		b.WriteString("/" + subject)
+		builder.WriteString(subject)
 	}
 
 	if filter.ObjectIDs != nil {
 		hasher := xxhash.New()
 		for _, oid := range filter.ObjectIDs.Values() {
-			if _, err := hasher.WriteString(oid); err != nil {
-				return "", err
-			}
+			hasher.WriteString(oid)
+			hasher.Write([]byte{0})
 		}
-
-		b.WriteString("/" + strconv.FormatUint(hasher.Sum64(), 10))
+		builder.Write(hasher.Sum([]byte{}))
 	}
-	return b.String(), nil
+
+	return builder.Build(), nil
 }
 
 func ReadUsersetTuplesKey(store string, filter storage.ReadUsersetTuplesFilter) string {
-	var b strings.Builder
-	b.WriteString(
-		storage.GetReadUsersetTuplesCacheKeyPrefix(store, filter.Object, filter.Relation),
-	)
+	var builder storage.CacheKeyBuilder
+	storage.GetReadUsersetTuplesCacheKeyPrefix(&builder, store, filter.Object, filter.Relation)
 
-	var rb strings.Builder
-	var wb strings.Builder
+	filterKey := storage.BuildUserTypeRestrictionsHash(filter.AllowedUserTypeRestrictions)
 
-	for _, userset := range filter.AllowedUserTypeRestrictions {
-		if _, ok := userset.GetRelationOrWildcard().(*openfgav1.RelationReference_Relation); ok {
-			rb.WriteString("/" + userset.GetType() + "#" + userset.GetRelation())
-		}
-		if _, ok := userset.GetRelationOrWildcard().(*openfgav1.RelationReference_Wildcard); ok {
-			wb.WriteString("/" + userset.GetType() + ":*")
-		}
-	}
+	builder.Write(filterKey)
 
-	// wildcard should have precedence
-	if wb.Len() > 0 {
-		b.WriteString(wb.String())
-	}
-
-	if rb.Len() > 0 {
-		b.WriteString(rb.String())
-	}
-	return b.String()
+	return builder.Build()
 }
 
 func ReadKey(store string, tupleKey *openfgav1.TupleKey) string {
-	var b strings.Builder
-	b.WriteString(
-		storage.GetReadCacheKey(store, tuple.TupleKeyToString(tupleKey)),
-	)
-	return b.String()
+	var builder storage.CacheKeyBuilder
+	storage.GetReadCacheKey(&builder, store, tuple.TupleKeyToString(tupleKey))
+	return builder.Build()
 }

@@ -0,0 +1,276 @@
+package storagewrappersutil
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/require"
+
+	openfgav1 "github.com/openfga/api/proto/openfga/v1"
+
+	"github.com/openfga/openfga/pkg/storage"
+)
+
+func TestReadStartingWithUserKey(t *testing.T) {
+	t.Run("basic", func(t *testing.T) {
+		filter := storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{
+				{Object: "user:alice"},
+			},
+		}
+		key, err := ReadStartingWithUserKey("store1", filter)
+		require.NoError(t, err)
+		require.NotEmpty(t, key)
+	})
+
+	t.Run("deterministic", func(t *testing.T) {
+		filter := storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{
+				{Object: "user:alice"},
+			},
+		}
+		k1, err := ReadStartingWithUserKey("store1", filter)
+		require.NoError(t, err)
+		k2, err := ReadStartingWithUserKey("store1", filter)
+		require.NoError(t, err)
+		require.Equal(t, k1, k2)
+	})
+
+	t.Run("different_stores_different_keys", func(t *testing.T) {
+		filter := storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{
+				{Object: "user:alice"},
+			},
+		}
+		k1, err := ReadStartingWithUserKey("store1", filter)
+		require.NoError(t, err)
+		k2, err := ReadStartingWithUserKey("store2", filter)
+		require.NoError(t, err)
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("different_object_types_different_keys", func(t *testing.T) {
+		f1 := storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{{Object: "user:alice"}},
+		}
+		f2 := storage.ReadStartingWithUserFilter{
+			ObjectType: "folder",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{{Object: "user:alice"}},
+		}
+		k1, err := ReadStartingWithUserKey("store1", f1)
+		require.NoError(t, err)
+		k2, err := ReadStartingWithUserKey("store1", f2)
+		require.NoError(t, err)
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("with_object_ids", func(t *testing.T) {
+		filter := storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{{Object: "user:alice"}},
+			ObjectIDs:  storage.NewSortedSet("id1", "id2"),
+		}
+		key, err := ReadStartingWithUserKey("store1", filter)
+		require.NoError(t, err)
+		require.NotEmpty(t, key)
+
+		filterNoIDs := storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{{Object: "user:alice"}},
+		}
+		keyNoIDs, err := ReadStartingWithUserKey("store1", filterNoIDs)
+		require.NoError(t, err)
+		require.NotEqual(t, key, keyNoIDs)
+	})
+
+	t.Run("with_relation_on_user", func(t *testing.T) {
+		f1 := storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{{Object: "group:eng", Relation: "member"}},
+		}
+		f2 := storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{{Object: "group:eng"}},
+		}
+		k1, err := ReadStartingWithUserKey("store1", f1)
+		require.NoError(t, err)
+		k2, err := ReadStartingWithUserKey("store1", f2)
+		require.NoError(t, err)
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("collision_delimiter_in_object_type", func(t *testing.T) {
+		f1 := storage.ReadStartingWithUserFilter{
+			ObjectType: "doc",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{{Object: "user:alice"}},
+		}
+		f2 := storage.ReadStartingWithUserFilter{
+			ObjectType: "doc#viewer",
+			Relation:   "",
+			UserFilter: []*openfgav1.ObjectRelation{{Object: "user:alice"}},
+		}
+		k1, err := ReadStartingWithUserKey("store1", f1)
+		require.NoError(t, err)
+		k2, err := ReadStartingWithUserKey("store1", f2)
+		require.NoError(t, err)
+		require.NotEqual(t, k1, k2)
+	})
+}
+
+func TestReadUsersetTuplesKey(t *testing.T) {
+	t.Run("basic", func(t *testing.T) {
+		filter := storage.ReadUsersetTuplesFilter{
+			Object:   "document:1",
+			Relation: "viewer",
+			AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+				{Type: "user"},
+			},
+		}
+		key := ReadUsersetTuplesKey("store1", filter)
+		require.NotEmpty(t, key)
+	})
+
+	t.Run("deterministic", func(t *testing.T) {
+		filter := storage.ReadUsersetTuplesFilter{
+			Object:   "document:1",
+			Relation: "viewer",
+			AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+				{Type: "group", RelationOrWildcard: &openfgav1.RelationReference_Relation{Relation: "member"}},
+				{Type: "user"},
+			},
+		}
+		k1 := ReadUsersetTuplesKey("store1", filter)
+		k2 := ReadUsersetTuplesKey("store1", filter)
+		require.Equal(t, k1, k2)
+	})
+
+	t.Run("different_stores_different_keys", func(t *testing.T) {
+		filter := storage.ReadUsersetTuplesFilter{
+			Object:   "document:1",
+			Relation: "viewer",
+		}
+		k1 := ReadUsersetTuplesKey("store1", filter)
+		k2 := ReadUsersetTuplesKey("store2", filter)
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("different_restrictions_different_keys", func(t *testing.T) {
+		f1 := storage.ReadUsersetTuplesFilter{
+			Object:   "document:1",
+			Relation: "viewer",
+			AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+				{Type: "user"},
+			},
+		}
+		f2 := storage.ReadUsersetTuplesFilter{
+			Object:   "document:1",
+			Relation: "viewer",
+			AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+				{Type: "group", RelationOrWildcard: &openfgav1.RelationReference_Relation{Relation: "member"}},
+			},
+		}
+		k1 := ReadUsersetTuplesKey("store1", f1)
+		k2 := ReadUsersetTuplesKey("store1", f2)
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("collision_delimiter_in_object", func(t *testing.T) {
+		f1 := storage.ReadUsersetTuplesFilter{
+			Object:   "doc:1",
+			Relation: "viewer",
+			AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+				{Type: "group", RelationOrWildcard: &openfgav1.RelationReference_Relation{Relation: "member"}},
+			},
+		}
+		f2 := storage.ReadUsersetTuplesFilter{
+			Object:   "doc:1#viewer/group",
+			Relation: "member",
+		}
+		k1 := ReadUsersetTuplesKey("store1", f1)
+		k2 := ReadUsersetTuplesKey("store1", f2)
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("wildcard_vs_relation", func(t *testing.T) {
+		f1 := storage.ReadUsersetTuplesFilter{
+			Object:   "document:1",
+			Relation: "viewer",
+			AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+				{Type: "user", RelationOrWildcard: &openfgav1.RelationReference_Wildcard{}},
+			},
+		}
+		f2 := storage.ReadUsersetTuplesFilter{
+			Object:   "document:1",
+			Relation: "viewer",
+			AllowedUserTypeRestrictions: []*openfgav1.RelationReference{
+				{Type: "user", RelationOrWildcard: &openfgav1.RelationReference_Relation{Relation: "member"}},
+			},
+		}
+		k1 := ReadUsersetTuplesKey("store1", f1)
+		k2 := ReadUsersetTuplesKey("store1", f2)
+		require.NotEqual(t, k1, k2)
+	})
+}
+
+func TestReadKey(t *testing.T) {
+	t.Run("basic", func(t *testing.T) {
+		tk := &openfgav1.TupleKey{
+			Object:   "document:1",
+			Relation: "viewer",
+			User:     "user:alice",
+		}
+		key := ReadKey("store1", tk)
+		require.NotEmpty(t, key)
+	})
+
+	t.Run("deterministic", func(t *testing.T) {
+		tk := &openfgav1.TupleKey{
+			Object:   "document:1",
+			Relation: "viewer",
+			User:     "user:alice",
+		}
+		k1 := ReadKey("store1", tk)
+		k2 := ReadKey("store1", tk)
+		require.Equal(t, k1, k2)
+	})
+
+	t.Run("different_stores_different_keys", func(t *testing.T) {
+		tk := &openfgav1.TupleKey{
+			Object:   "document:1",
+			Relation: "viewer",
+			User:     "user:alice",
+		}
+		k1 := ReadKey("store1", tk)
+		k2 := ReadKey("store2", tk)
+		require.NotEqual(t, k1, k2)
+	})
+
+	t.Run("different_tuples_different_keys", func(t *testing.T) {
+		tk1 := &openfgav1.TupleKey{
+			Object:   "document:1",
+			Relation: "viewer",
+			User:     "user:alice",
+		}
+		tk2 := &openfgav1.TupleKey{
+			Object:   "document:1",
+			Relation: "editor",
+			User:     "user:alice",
+		}
+		k1 := ReadKey("store1", tk1)
+		k2 := ReadKey("store1", tk2)
+		require.NotEqual(t, k1, k2)
+	})
+}

@@ -10,6 +10,9 @@ Try to keep listed changes to a concise bulleted list of simple explanations of
 ### Changed
 - Report `allowed` result and `tuple_key` on Check and experimental `weighted_graph_check` resolution trace spans. [#3116](https://github.com/openfga/openfga/pull/3116)
 
+### Fixed
+- Fixed cache key collisions in experimental `weighted_graph_check` union resolution by moving result caching from the union node level to the individual edge level, preventing collisions across requests that share edges but differ in object or relation. [#3117](https://github.com/openfga/openfga/pull/3117)
+
 ### Security
 - Update toolchain Go version to 1.26.3 to address the Go standard library vulnerabilities documented in the [Go 1.26.3 release notes](https://go.dev/doc/devel/release#go1.26.3). [#3115](https://github.com/openfga/openfga/pull/3115)
 

@@ -189,9 +189,6 @@ func (r *Resolver) ResolveUnionEdges(ctx context.Context, req *Request, edges []
 		close(out)
 	}()
 
-	relation := req.GetTupleKey().GetRelation()
-	objectType := tuple.GetType(req.GetTupleKey().GetObject())
-	objectRelation := tuple.ToObjectRelationString(objectType, relation)
 	ids := make([]string, 0, len(edges))
 	for _, edge := range edges {
 		id := buildEdgeCacheKey(r.model.GetModelID(), req, edge)
@@ -209,9 +206,7 @@ func (r *Resolver) ResolveUnionEdges(ctx context.Context, req *Request, edges []
 		}
 		pool.Go(func() error {
 			res, err := r.ResolveEdge(ctx, req, edge, visited)
-			// we only need to cache the response for the edge if the edge does not belong to the request relation
-			// otherwise the subproblem should be sufficient
-			if err == nil && edge.GetRelationDefinition() != objectRelation {
+			if err == nil {
 				entry := &ResponseCacheEntry{Res: res, LastModified: time.Now()}
 				r.cache.Set(id, entry, r.cacheTTL)
 			}
@@ -247,26 +242,13 @@ func (r *Resolver) ResolveUnionEdges(ctx context.Context, req *Request, edges []
 }
 
 // reduce as a logical union operation (exit the moment we have a single true).
-func (r *Resolver) ResolveUnion(ctx context.Context, req *Request, node *authzGraph.WeightedAuthorizationModelNode, visited *sync.Map) (resp *Response, err error) {
+func (r *Resolver) ResolveUnion(ctx context.Context, req *Request, node *authzGraph.WeightedAuthorizationModelNode, visited *sync.Map) (*Response, error) {
 	ctx, span := tracer.Start(ctx, "ResolveUnion", trace.WithAttributes(
 		attribute.String("tuple_key", req.GetTupleString()),
 		attribute.Bool("cached", false),
 	))
 	defer span.End()
 
-	if res, ok := r.isCached(req.GetConsistency(), req.GetCacheKey()); ok {
-		span.SetAttributes(attribute.Bool("cached", true))
-		return res, nil
-	}
-
-	defer func() {
-		if err != nil {
-			return
-		}
-		entry := &ResponseCacheEntry{Res: resp, LastModified: time.Now()}
-		r.cache.Set(req.GetCacheKey(), entry, r.cacheTTL)
-	}()
-
 	emptyCycle := visited == nil
 	if emptyCycle && node.GetNodeType() == authzGraph.SpecificTypeAndRelation && (node.GetRecursiveRelation() == node.GetUniqueLabel() || node.IsPartOfTupleCycle()) {
 		// initialize visited map for first time,
@@ -450,8 +432,19 @@ func (r *Resolver) ResolveRecursive(ctx context.Context, req *Request, edge *aut
 	}()
 
 	go func() {
+		cacheKey := buildEdgeCacheKey(r.model.GetModelID(), req, edge)
+
+		if res, ok := r.isCached(req.GetConsistency(), cacheKey); ok {
+			span := trace.SpanFromContext(ctx)
+			span.SetAttributes(attribute.Bool("cached", true))
+
+			concurrency.TrySendThroughChannel(ctx, ResponseMsg{Res: res}, out)
+			return
+		}
+
 		var err error
 		var res *Response
+
 		switch edge.GetEdgeType() {
 		case authzGraph.DirectEdge:
 			res, err = r.resolveRecursiveUserset(ctx, req, edge, visited, canApplyOptimization)
@@ -461,6 +454,10 @@ func (r *Resolver) ResolveRecursive(ctx context.Context, req *Request, edge *aut
 			res, err = nil, ErrPanicRequest
 		}
 
+		if err == nil {
+			entry := &ResponseCacheEntry{Res: res, LastModified: time.Now()}
+			r.cache.Set(cacheKey, entry, r.cacheTTL)
+		}
 		concurrency.TrySendThroughChannel(ctx, ResponseMsg{Res: res, Err: err}, out)
 	}()
 

@@ -3,7 +3,6 @@ package check
 import (
 	"context"
 	"errors"
-	"fmt"
 	"testing"
 	"time"
 
@@ -44,11 +43,6 @@ func TestResolveUnion(t *testing.T) {
 		mg, err := modelgraph.New(model)
 		require.NoError(t, err)
 
-		cachedEntry := &ResponseCacheEntry{
-			Res:          &Response{Allowed: true},
-			LastModified: time.Now(),
-		}
-
 		resolver := New(Config{
 			Model:                     mg,
 			Datastore:                 mockDatastore,
@@ -64,11 +58,34 @@ func TestResolveUnion(t *testing.T) {
 		})
 		require.NoError(t, err)
 
-		mockCache.EXPECT().Get(req.GetCacheKey()).Return(cachedEntry).Times(1)
-
 		node, ok := mg.GetNodeByID("group#member")
 		require.True(t, ok)
 
+		edges, ok := mg.GetEdgesFromNode(node)
+		require.True(t, ok)
+
+		union := edges[0].GetTo()
+		edges, ok = mg.GetEdgesFromNode(union)
+		require.True(t, ok)
+
+		cachedTrue := &ResponseCacheEntry{
+			Res:          &Response{Allowed: true},
+			LastModified: time.Now(),
+		}
+		firstCacheKey := buildEdgeCacheKey(model.GetId(), req, edges[0])
+		mockCache.EXPECT().Get(firstCacheKey).Return(cachedTrue).Times(1)
+
+		admin := edges[1].GetTo()
+		edges, ok = mg.GetEdgesFromNode(admin)
+		require.True(t, ok)
+
+		cachedFalse := &ResponseCacheEntry{
+			Res:          &Response{Allowed: false},
+			LastModified: time.Now(),
+		}
+		secondCacheKey := buildEdgeCacheKey(model.GetId(), req, edges[0])
+		mockCache.EXPECT().Get(secondCacheKey).Return(cachedFalse).MaxTimes(1)
+
 		res, err := resolver.ResolveUnion(context.Background(), req, node, nil)
 		require.NoError(t, err)
 		require.True(t, res.Allowed)
@@ -108,8 +125,8 @@ func TestResolveUnion(t *testing.T) {
 		})
 		require.NoError(t, err)
 
-		// the first cache call should be to check for a subproblem cache entry
-		mockCache.EXPECT().Get(req.GetCacheKey()).Return(nil).Times(1)
+		node, ok := mg.GetNodeByID("group#member")
+		require.True(t, ok)
 
 		// simulate an edge with a cached false result
 		mockCache.EXPECT().Get(gomock.Any()).Return(cachedFalse).Times(1)
@@ -130,15 +147,50 @@ func TestResolveUnion(t *testing.T) {
 				}).Times(2)
 
 		// each edge sets the results of its resolution
-		edgeCacheSets := mockCache.EXPECT().
-			Set(gomock.Not(gomock.Eq(req.GetCacheKey())), gomock.Any(), gomock.Any()).
+		mockCache.EXPECT().
+			Set(gomock.Any(), gomock.Any(), gomock.Any()).
 			Times(2)
 
-		// the last cache call should be to set the subproblem cache entry
-		mockCache.EXPECT().
-			Set(req.GetCacheKey(), gomock.Any(), gomock.Any()).
-			After(edgeCacheSets).
-			Times(1)
+		resolver := New(Config{
+			Model:                     mg,
+			Datastore:                 mockDatastore,
+			Cache:                     mockCache,
+			ConcurrencyLimit:          10,
+			LastCacheInvalidationTime: time.Now().Add(-time.Hour),
+		})
+
+		res, err := resolver.ResolveUnion(context.Background(), req, node, nil)
+		require.NoError(t, err)
+		require.True(t, res.Allowed)
+	})
+
+	t.Run("caches_all_edges", func(t *testing.T) {
+		ctrl := gomock.NewController(t)
+		defer ctrl.Finish()
+
+		storeID := ulid.Make().String()
+		mockDatastore := mocks.NewMockRelationshipTupleReader(ctrl)
+		mockCache := mocks.NewMockInMemoryCache[any](ctrl)
+
+		model := testutils.MustTransformDSLToProtoWithID(`
+            model
+              schema 1.1
+            type user
+            type group
+              relations
+                define member: [user] or admin
+                define admin: [user]
+        `)
+
+		mg, err := modelgraph.New(model)
+		require.NoError(t, err)
+
+		mockDatastore.EXPECT().ReadUserTuple(gomock.Any(), storeID, gomock.Any(), gomock.Any()).
+			Return(nil, storage.ErrNotFound).Times(2)
+
+		mockCache.EXPECT().Get(gomock.Any()).Return(nil).AnyTimes()
+		// Both edges (including the one whose relationDefinition matches objectRelation) must be cached.
+		mockCache.EXPECT().Set(gomock.Any(), gomock.Any(), gomock.Any()).Times(2)
 
 		resolver := New(Config{
 			Model:                     mg,
@@ -148,12 +200,19 @@ func TestResolveUnion(t *testing.T) {
 			LastCacheInvalidationTime: time.Now().Add(-time.Hour),
 		})
 
+		req, err := NewRequest(RequestParams{
+			StoreID:  storeID,
+			Model:    mg,
+			TupleKey: tuple.NewTupleKey("group:1", "member", "user:maria"),
+		})
+		require.NoError(t, err)
+
 		node, ok := mg.GetNodeByID("group#member")
 		require.True(t, ok)
 
 		res, err := resolver.ResolveUnion(context.Background(), req, node, nil)
 		require.NoError(t, err)
-		require.True(t, res.Allowed)
+		require.False(t, res.GetAllowed())
 	})
 }
 
@@ -338,15 +397,12 @@ func TestResolveUnionEdges(t *testing.T) {
 		ctx, cancel := context.WithCancel(context.Background())
 
 		mockDatastore.EXPECT().ReadUserTuple(gomock.Any(), storeID, gomock.Any(), gomock.Any()).
-			DoAndReturn(func(context.Context, string, storage.ReadUserTupleFilter, storage.ReadUserTupleOptions) (*openfgav1.Tuple, error) {
+			DoAndReturn(func(ctx context.Context, _ string, _ storage.ReadUserTupleFilter, _ storage.ReadUserTupleOptions) (*openfgav1.Tuple, error) {
 				cancel()
-				time.Sleep(10 * time.Millisecond)
-				return nil, storage.ErrNotFound
+				return nil, ctx.Err()
 			}).MaxTimes(2)
 
-		key := fmt.Sprintf(`^c\.%s\|group:1\|user:maria\|group#admin\|`, mg.GetModelID())
 		mockCache.EXPECT().Get(gomock.Any()).Return(nil).AnyTimes()
-		mockCache.EXPECT().Set(gomock.Regex(key), gomock.Any(), gomock.Any()).Times(1)
 
 		resolver := New(Config{
 			Model:            mg,
@@ -5494,6 +5550,142 @@ func TestResolveRecursiveCheck(t *testing.T) {
 		require.NoError(t, err)
 		require.True(t, res.GetAllowed())
 	})
+
+	t.Run("caches_recursive_edge_on_miss", func(t *testing.T) {
+		ctrl := gomock.NewController(t)
+		defer ctrl.Finish()
+
+		storeID := ulid.Make().String()
+		mockDatastore := mocks.NewMockRelationshipTupleReader(ctrl)
+		mockCache := mocks.NewMockInMemoryCache[any](ctrl)
+		mockPlanner := mocks.NewMockManager(ctrl)
+		mockSelector := mocks.NewMockSelector(ctrl)
+
+		model := testutils.MustTransformDSLToProtoWithID(`
+		   model
+			schema 1.1
+		   type user
+		   type document
+			relations
+			   define viewer: [user] or viewer from parent
+			   define parent: [document]
+	  	`)
+
+		mg, err := modelgraph.New(model)
+		require.NoError(t, err)
+
+		mockPlanner.EXPECT().GetPlanSelector(gomock.Any()).Return(mockSelector).AnyTimes()
+		mockSelector.EXPECT().Select(gomock.Any()).Return(DefaultPlan).AnyTimes()
+		mockSelector.EXPECT().UpdateStats(gomock.Any(), gomock.Any()).AnyTimes()
+
+		mockDatastore.EXPECT().ReadUserTuple(gomock.Any(), storeID, gomock.Any(), gomock.Any()).
+			Return(nil, storage.ErrNotFound).AnyTimes()
+
+		mockDatastore.EXPECT().Read(gomock.Any(), storeID, gomock.Any(), gomock.Any()).
+			AnyTimes().
+			DoAndReturn(func(_ context.Context, _ string, filter storage.ReadFilter, _ storage.ReadOptions) (storage.TupleIterator, error) {
+				if filter.Object == "document:1" {
+					return storage.NewStaticTupleIterator([]*openfgav1.Tuple{{Key: tuple.NewTupleKey("document:1", "parent", "document:2")}}), nil
+				}
+				return storage.NewStaticTupleIterator([]*openfgav1.Tuple{}), nil
+			})
+
+		mockCache.EXPECT().Get(gomock.Any()).Return(nil).AnyTimes()
+		// ResolveRecursive must write its result to the cache after resolution.
+		mockCache.EXPECT().Set(gomock.Any(), gomock.Any(), gomock.Any()).MinTimes(1)
+
+		resolver := New(Config{
+			Model:                     mg,
+			Datastore:                 mockDatastore,
+			Cache:                     mockCache,
+			Planner:                   mockPlanner,
+			ConcurrencyLimit:          10,
+			LastCacheInvalidationTime: time.Now().Add(-time.Hour),
+		})
+
+		req, err := NewRequest(RequestParams{
+			StoreID:  storeID,
+			Model:    mg,
+			TupleKey: tuple.NewTupleKey("document:1", "viewer", "user:maria"),
+		})
+		require.NoError(t, err)
+
+		resolver.strategies[DefaultStrategyName] = NewDefault(mg, resolver, 10)
+
+		res, err := resolver.ResolveCheck(context.Background(), req)
+		require.NoError(t, err)
+		require.False(t, res.GetAllowed())
+	})
+
+	t.Run("cache_hit_on_recursive_edge", func(t *testing.T) {
+		ctrl := gomock.NewController(t)
+		defer ctrl.Finish()
+
+		storeID := ulid.Make().String()
+		mockDatastore := mocks.NewMockRelationshipTupleReader(ctrl)
+		mockCache := mocks.NewMockInMemoryCache[any](ctrl)
+		mockPlanner := mocks.NewMockManager(ctrl)
+		mockSelector := mocks.NewMockSelector(ctrl)
+
+		model := testutils.MustTransformDSLToProtoWithID(`
+		   model
+			schema 1.1
+		   type user
+		   type document
+			relations
+			   define viewer: [user] or viewer from parent
+			   define parent: [document]
+	  	`)
+
+		mg, err := modelgraph.New(model)
+		require.NoError(t, err)
+
+		mockPlanner.EXPECT().GetPlanSelector(gomock.Any()).Return(mockSelector).AnyTimes()
+		mockSelector.EXPECT().Select(gomock.Any()).Return(DefaultPlan).AnyTimes()
+		mockSelector.EXPECT().UpdateStats(gomock.Any(), gomock.Any()).AnyTimes()
+
+		// Only the non-recursive direct [user] edge calls the datastore.
+		mockDatastore.EXPECT().ReadUserTuple(gomock.Any(), storeID, gomock.Any(), gomock.Any()).
+			Return(nil, storage.ErrNotFound).AnyTimes()
+
+		req, err := NewRequest(RequestParams{
+			StoreID:  storeID,
+			Model:    mg,
+			TupleKey: tuple.NewTupleKey("document:1", "viewer", "user:maria"),
+		})
+		require.NoError(t, err)
+
+		// Pre-populate the cache for the recursive edge.
+		node, ok := mg.GetNodeByID("document#viewer")
+		require.True(t, ok)
+		recursiveEdge, ok := mg.CanApplyRecursion(node, "", true)
+		require.True(t, ok)
+		recursiveKey := buildEdgeCacheKey(model.GetId(), req, recursiveEdge)
+
+		cachedTrue := &ResponseCacheEntry{
+			Res:          &Response{Allowed: true},
+			LastModified: time.Now(),
+		}
+		mockCache.EXPECT().Get(recursiveKey).Return(cachedTrue).Times(1)
+		mockCache.EXPECT().Get(gomock.Any()).Return(nil).AnyTimes()
+		// Non-recursive edges may still write to the cache.
+		mockCache.EXPECT().Set(gomock.Any(), gomock.Any(), gomock.Any()).AnyTimes()
+
+		resolver := New(Config{
+			Model:                     mg,
+			Datastore:                 mockDatastore,
+			Cache:                     mockCache,
+			Planner:                   mockPlanner,
+			ConcurrencyLimit:          10,
+			LastCacheInvalidationTime: time.Now().Add(-time.Hour),
+		})
+
+		resolver.strategies[DefaultStrategyName] = NewDefault(mg, resolver, 10)
+
+		res, err := resolver.ResolveCheck(context.Background(), req)
+		require.NoError(t, err)
+		require.True(t, res.GetAllowed())
+	})
 }
 
 func TestResolveCheck(t *testing.T) {