A system, method, and medium for performing multi-level and multi-mode deduplication in a cloud based backup storage system. Fingerprints are generated for data segments from individual clients at a first level, with a separate fingerprint index for each individual client. The fingerprints are compared to their respective fingerprint indexes, and if the fingerprints are unique, then their associated data segments may be deduplicated across data segments from a plurality of clients at a second level. The fingerprints are compared to a common fingerprint index and deduplicated at a second level. The common fingerprint index contains fingerprints generated from data segments from a plurality of clients connected to the backup storage system.