Embodiments may include a consistency measurement component that utilizes memory-efficient sets (e.g., Bloom filters) to generate consistency metrics for read operations performed on different replicated data objects of distributed storage system. Based on the consistency metrics, the consistency measurement component may identify a subset of replicated data objects associated with low levels of consistency. The consistency measurement component may target this subset for consistency improvement by generating instructions to improve the consistency of the subset. In other cases, the consistency measurement component may notify a consistency improvement component about the targeted subset. In response, the consistency improvement component may generate instructions to improve the consistency of the targeted subset.