1. A computing system, comprising a plurality of physical computing nodes that implement a distributed data store configured to: partition data to be stored in the distributed data store, wherein to partition the data, the distributed data store is configured to: divide the data into two or more partitions; and store each of the two or more partitions of the data in a respective relational database on one of the plurality of computing nodes, wherein at least two of the partitions are stored on different computing nodes; create a partition map comprising information usable to identify the one of the plurality of computing nodes on which each partition is stored; store a copy of the partition map on one or more of the plurality of computing nodes; change the partitioning of at least a portion of the data; create a new partition map comprising information reflecting said change; and send an indication of the new partition map to one or more of the plurality of computing nodes, wherein the partition map and the new partition map comprise respective version identifiers.