Methods, systems, and computer-readable media for a cell-based storage system with failure isolation are disclosed. A first subset of storage nodes is selected from a set of storage nodes of a data store and assigned to a first partition of data. Replicas of the first partition are stored using the first subset. A second subset of storage nodes is selected from the set of storage nodes and assigned to a second partition of data. The second subset is selected based (at least in part) on the membership of the first subset, and the second subset comprises at least one node not present in the first. Replicas of the second partition are stored using the second subset. Access requests associated with the first partition are routed to the first subset of storage nodes. Access requests associated with the second partition are routed to the second subset of storage nodes.