Method and apparatus for repartitioning and replication of a searchable index in a searchable data service. The searchable data service may provide a searchable index to a backend data store. The searchable index may be repartitioned, and a partition may be moved to another storage node, to allow the searchable index to grow beyond the limits of a single storage device. Repartitioning may also be performed to provide load-balancing of write requests. Partitions may be replicated across two or more storage nodes to provide redundancy, data durability, data availability and load balancing of read requests among the storage nodes and/or across data centers. In one embodiment, a lazy replication mechanism may be used in the replication of partitions. In one embodiment, replication may be performed using an anti-entropy protocol to replicate a partition, and a gossip protocol to update the replicated partition.