Any database that's spread across multiple machines needs some scheme to decide which machines should store a given piece of data. A sharding system makes such a decision by using the key for each row in a database table. For example, with a ten machine cluster, one way to shard is to use the last decimal digit of the index number to decide which machine to store a piece of data. Since both the storing and retrieval code follows the same rule, the system knows exactly which machine holds a specific piece of data.

The biggest challenges with sharding are splitting the data evenly across machines and dealing with changes in the cluster size. To ease the pain of these operations, more complex schemes are used to split up the data. Some of these rely on a central directory that holds the locations of particular keys. This level of indirection allows data to be moved between machines when a particular shard grows too large (to rebalance the distribution), at the cost of requiring an extra lookup in the directory for each operation. The directory's information is usually fairly small and reasonably static, though, so it's a good candidate for local caching, as long as the infrequent changes are spotted.