1. A method for processing tracked blocks in a data storage implemented with data deduplication by a processor, comprising: partitioning input snapshot data into changed tracked blocks; grouping the changed tracked blocks into enclosing similarity units; processing for deduplication similarity units that contain at least one input changed tracked block; aligning a boundary of the similarity units to the size of the tracked blocks; deduplicating a respective one of the similarity units with a corresponding similarity unit of a previous snapshot; and examining a deduplication coverage; wherein if a deduplication coverage threshold is not met, a similarity search is conducted and the respective one of the similarity units is deduplicated with a found similarity unit residing in a similarity index.