Large-scale web services like LinkedIn serve millions of users across the globe. The user experience depends on high service availability and performance of the services. In such a scenario, capacity measurement is critical for these cloud services. Resources should be provisioned such that the service can easily handle peak traffic without experiencing bottlenecks or compromising on latency. In addition, accurate understanding of service capacity will lead to systematic provisioning of resources saving millions of dollars in capital investment and better savings in energy. Stateful services like NoSQL databases are one of the most expensive and critical components in a cloud stack. A clear understanding of the capacity limits of a stateful service will lead to better availability and performance across the stack. However, based on our experience, accurately measuring capacity of NoSQL databases is much more challenging than regular stateless services. In this work, we present various approaches to accurately measure the capacity of stateful NoSQL services, their benefits and costs, and discuss in detail about the solution we prefer to use.