DynamoDB: composite primary keys can collide because the internal key encoding is ambiguous

[chris-enroly]

The problem

A composite primary key is stored under a single map key built by joining the partition and sort values with a literal #:

// src/main/java/io/github/hectorvent/floci/services/dynamodb/DynamoDbService.java:3235
return pk + "#" + extractScalarValue(skAttr);

with the same join at line 3392 for the cursor/scan path.

# is a legal character inside a DynamoDB key attribute value, so two different primary keys can encode to the same address:

Item	partition key	sort key	encodes to
1	A#	B	A##B
2	A	#B	A##B

The second PutItem replaces the first. Both keys then read back as item 2, and item 1 is gone. Real DynamoDB stores both, since they are distinct primary keys.

This is silent data loss rather than an error, which is what makes it awkward to notice: nothing fails at write time.

Reproduction

Table with a composite key:

aws --endpoint-url http://localhost:4566 dynamodb create-table \
  --table-name Orders \
  --attribute-definitions AttributeName=customerId,AttributeType=S AttributeName=orderId,AttributeType=S \
  --key-schema AttributeName=customerId,KeyType=HASH AttributeName=orderId,KeyType=RANGE \
  --billing-mode PAY_PER_REQUEST

aws --endpoint-url http://localhost:4566 dynamodb put-item --table-name Orders \
  --item '{"customerId":{"S":"A#"},"orderId":{"S":"B"},"marker":{"S":"FIRST"}}'

aws --endpoint-url http://localhost:4566 dynamodb put-item --table-name Orders \
  --item '{"customerId":{"S":"A"},"orderId":{"S":"#B"},"marker":{"S":"SECOND"}}'

aws --endpoint-url http://localhost:4566 dynamodb get-item --table-name Orders \
  --key '{"customerId":{"S":"A#"},"orderId":{"S":"B"}}'

Expected: the item with marker=FIRST.

Observed against main (a2fddaf): the item with marker=SECOND. Both key combinations return the second item, and Scan shows one item where there should be two.

I confirmed this at the service layer on current main: after both writes, getItem for ("A#", "B") returns {"customerId":{"S":"A"},"orderId":{"S":"#B"},"marker":{"S":"SECOND"}}.

Keys that embed # as a separator are a common single-table design convention, so the colliding shapes are not especially exotic.

Two ways to fix it

These have quite different trade-offs and the choice affects stored state, so it seemed better to ask before anyone writes code.

Option 1: detect the collision and reject the write

Keep the current encoding. Compare the structured key identity against the item already stored at that encoded address, and if they are different logical keys, fail the write with a ValidationException instead of overwriting. The same check runs on the BatchWriteItem and TransactWriteItems paths before any write is applied, so a batch cannot half-apply.

• Stored key format is unchanged, so existing persisted state keeps working with no migration.
• Smaller, contained change.
• It does not match AWS. Real DynamoDB accepts both items, so a workload that is valid against AWS would start getting errors against Floci. It trades silent data loss for a failure AWS never produces.

Option 2: make the encoding unambiguous

Change the encoding so the delimiter cannot be confused with data, for example length-prefixed segments (2#A#1#B) or escaping the delimiter inside each segment. Collisions become impossible by construction.

• Behaviour matches AWS exactly: both items are stored and both read back. No new error path.
• The on-disk key format changes, so state persisted by earlier versions needs migrating on startup or rebuilding.
• Slightly wider change, since it touches the key encoding boundary rather than adding a guard in front of it.

One thing that does not work

Making the delimiter configurable. Whatever character is chosen is still legal inside a key value, so collisions remain possible and become rarer and harder to diagnose rather than being fixed.

Question

Which direction would you prefer, and is AWS fidelity the deciding factor here, or does the migration cost of changing the stored key format outweigh it? Happy to file this as a formal bug report as well if that is more useful for tracking.

[hectorvent]

Thanks for the careful write-up, @chris-enroly. I reproduced it on current main exactly as you describe, and AWS fidelity is the deciding factor here, so let's go with option 2.

A few things from digging into it:

• Escape rather than length-prefix. Escape \ and # inside each segment before joining. Any key without those two characters encodes to exactly the same string as today, so almost all persisted state is untouched. Rebuilding every map key from the item's own key attributes on load then covers the rest, with no format version needed. Numbers are already normalised before the join and binary keys are base64, so only strings need it.
• Both builders must share the encoder. buildItemKey and buildItemKeyFromNode feed the ConcurrentSkipListMap and the Scan tailMap cursor, so one helper keeps them consistent. Query is unaffected, it sorts by the sort key explicitly.
• One more symptom. TransactWriteItems with (X#, Y) and (X, #Y) is rejected today with "Transaction request cannot include multiple operations on one item", because the participant tuple still carries the encoded string. The comment above that check says it is immune, so that comment should go with the fix.

A bug issue would be useful for tracking. If you'd like to take the PR, it's yours; otherwise we'll pick it up.

[hectorvent]

Filed as #3800 for tracking, with the reproduction, the TransactWriteItems symptom, and the option 2 direction we agreed here.

[chris-enroly]

Thanks for digging into it, and agreed on option 2. The escaping approach is better than what I sketched: keeping every key without \ or # byte-identical means almost nothing has to migrate.

No need to assign it to me. #3804 landed a few hours ago and already covers the ground, including the TransactWriteItems comment and a regression for it. Duplicating it would just give you two PRs to reconcile.

Happy to review #3804 if that is useful. One thing I would want to check there: escaping changes the byte ordering of encoded keys, and the Scan cursor advances through the map by that ordering, so it is worth confirming pagination order still matches DynamoDB's.

[chris-enroly]

Following up on my own question about pagination order, since it should not sit here unanswered: the concern was unfounded.

Query is unaffected, as you said. It sorts explicitly by the sort key attributes through compareAttributeValues rather than relying on map iteration order. Scan order does change for keys containing # or \, because \# (0x5C 0x23) sorts differently from a bare # (0x23) against any byte in between, but real DynamoDB gives Scan no ordering guarantee, and pagination itself stays correct because the cursor and the stored keys are built with the same encoder. So there is nothing to fix in #3804 on that front.