1. A computer-implemented method of performing a storage operation in a distributed, deduplicated storage system, comprising: during a period of availability of a first deduplication database server of a plurality of deduplication database servers and during a period of availability of a second deduplication database server of the plurality of deduplication database servers, the first deduplication database server designated as a failover deduplication database server for the second deduplication database server, the plurality of deduplication database servers storing signatures of data blocks stored in secondary storage which correspond to data blocks received from primary storage: receiving at one or more secondary storage computing devices and as part of a first secondary copy operation a first set of one or more signatures corresponding to one or more data blocks stored in primary storage; identifying the second deduplication database server as the deduplication database server assigned to store the first set of signatures; determining that the first set of signatures match a second set of signatures comprising one or more signatures that were stored in the first deduplication database server during a previous period of unavailability of the second deduplication database server; and with the one or more secondary storage computing devices, querying one of the first deduplication database server and the second deduplication database server for the first set of signatures based at least on a storage policy.