Database sharding

A computer-implemented method for storing a record in a sharded table of a sharded database, the sharded database comprising a plurality of database shards, each of the database shards being configured to store a subset of records of the sharded table and being associated with a respective Bloom filter which is configured to provide an indication as to whether a record associated with a particular sharding key may have been stored in that database shard, the computer-implemented method comprising:

• obtaining a sharding key for the record to be stored, the sharding key being based on one or more fields of the record;
• generating, for each of a plurality of the respective Bloom filters, a respective representation of the sharding key for use with that Bloom filter by applying one or more hashing functions used by that Bloom filter to the sharding key;
• calculating Hamming distances between current values of each of the plurality of Bloom filters and the respective representation of the sharding key for use with that Bloom filter;
• selecting a database shard based on the calculated Hamming distances;
• and
• storing the record in the selected database shard.