I believe whatever random GUID generator you are using isn't truly random, or, your HashKeyRange values for each shard are not actually evenly distributed, as is highlighted in this question: Kinesis partition key falls always in the same shard