flâneur

Hash-Range Partitioning | ben.kirw.in

ben.kirw.in · 765 words · saved by 1 readers

In distributed systems, it’s extroardinarily common to want to split a large dataset across some number of physical shards or partitions. This is commonly done by taking the key, hashing it, and then taking the hash modulo the number of partitions: Let’s call that hash-modulus partitioning for short. It’s simple, straightforward, and correct, and it’s used as the default partitioner in projects from Spark to Kafka to Hive. It’s also far from optimal, especially when you’re joining different data sets together. Here’s a slightly different partitioning function, which I’ll call hash-range partitioning: This post explains how that function works and why you might prefer it. So we can visualize things easily, let’s imagine we’re using a tiny 4-bit hash function. This gives us 2^4=16 different possible hash values, mapping to the integers from 0 to 15. Hash-modulus partitioning will take those 16 values and round-robin them across our partitions. If we have 3 partitions for our 16 possible

Hash-Range Partitioning Better partitioning for distributed data In distributed systems, it’s extroardinarily common to want to split a large dataset across some number of physical shards or partitions. This is commonly done by taking the key, hashing it, and then taking the hash modulo the number of partitions: def partition(key, num_partitions): hash(key) % num_partitions Let’s call that hash-modulus partitioning for short. It’s simple, straightforward, and correct, and it’s used as the default partitioner in projects from Spark to Kafka to Hive. It’s also far from optimal, especially when y

related reading