I've seen two large usages of DynamoDB at two different companies, and for what it's worth, in both cases we've had similar trouble as the author. In one case we ended up ripping it out and moving to a sharded Postgres scheme, and in the other we've left in place for now because a migration will be such a monumental effort, but it's pretty much universally maligned. Fundamentally, the problem seems to be that choosin…
But what's a better option for a distributed, managed database-as-a-service? Rolling your own does mean significant operational burden.
I wonder if you could do something like add a random number to each of your keys before hashing. It would increase your storage size by Nx, but it seems like that would spread your load as well.