Do you care about making keys appear expired in the seconds to minutes between the exact moment of expiration, and the time when some garbage collection process can clean those records up? If you don’t, option B (or option B with the key spread around the timestamp to spread out writes) seems ok; depending on the rate of rejected writes you might be pulling down a lot of 5k blobs though.
If so, you’d need an efficient way to go from key to timestamp, which eliminates option B.
I don’t claim any particular expertise, but given your description, I would try to do something like:
'k', key -> value
't', key -> timestamp
's', key[0], timestamp, key[1:7] -> empty
To read you pull the key from the k and t prefixes, if the timestamp is old, you can return nothing.
To write you check for the key in the t space, and can abort or overwrite the old value as appropriate. Writing fills out all three keys, with the s space splitting the key up on either side of the timestamp, to spread the writes out across processes.
Garbage collection can proceed in parallel by searching each of the 256 subspaces of s for timestamps that have expired. Expiration becomes just a performance/space optimization, as the reads/writes can still function and efficiently implement your expiration even if the garbage collector never runs.
(On further consideration, maybe your option A with the key splitting trick would be fine?)