In one embodiment, a computer program product is configured for performing deduplication in conjunction with random read and write operations across a namespace divided into a plurality of disjoint regions. The computer program product includes a computer readable storage medium having program instructions embodied therewith, where the computer readable storage medium is not a transitory signal per se. The program instructions are executable by a computer to cause the computer to perform a method including: maintaining a metadata structure for each of the plurality of disjoint regions via the respective region manager(s) of the plurality of disjoint regions, each metadata structure comprising metadata indicating a physical storage location of one or more data chunks associated with the respective region; and performing, by the computer, a deduplicated write operation of a first data chunk in a first region of the plurality of disjoint regions.