  Large-scale replicated data type stores often resort to eventual consistency
to guarantee low latency and high availability. It is widely accepted that
programming over eventually consistent data stores is challenging, since
arbitrary divergence among replicas is allowed. Moreover, pragmatic protocols
actually achieve consistency guarantees stronger than eventual consistency,
which can be and need to be utilized to facilitate the reasoning of and
programming over replicated data types. Toward the challenges above, we propose
the ViSearch framework for precise measurement of eventual consistency
semantics. ViSearch employs the visibility-arbitration specification
methodology in concurrent programming, which extends the linearizability-based
specification methodology with a dynamic visibility relation among operations,
in addition to the standard dynamic happen-before and linearization relations.
The consistency measurement using ViSearch is NP-hard in general. To enable
practical and efficient consistency measurement in replicated data type stores,
the ViSearch framework refactors the existing brute-force checking algorithm to
a generic algorithm skeleton, which further enables efficient pruning of the
search space and effective parallelization. We employ the ViSearch framework
for consistency measurement in two replicated data type stores Riak and
CRDT-Redis. The experimental evaluation shows the usefulness and
cost-effectiveness of consistency measurement based on the ViSearch framework
in realistic scenarios.
