Sherpa Scales New Heights

Overview

Sherpa is Yahoo’s distributed NoSQL key-value store offered as a hosted service. It is the cornerstone of Yahoo properties and hosts over 2,000 tables, 1 trillion records, and serves over 1 million queries a second across a wide spectrum of applications.

Though core features described in prior publications (see References section) have solidly served applications over the years, we have constantly strived to evolve Sherpa to meet new requirements. Today, web properties have to deliver sub-second responsiveness with engaging experiences, application needs have diverged across durability and latency requirements, and scale has increased multifold due to user growth and mobile pervasiveness.

To address these needs, cost effectively, we have introduced differentiated service tiers to meet the varying durability and latency requirements. We have also adopted Log Structured Merge (LSM) storage based on RocksDB and devised a new serving stack compatible with existing applications using Nginx HTTP server for REST API support and ZeroMQ for parallel access to storage.

Key Drivers

The following key drivers influenced the evolution of Sherpa in the last 2-3 years:

Serving Latency: Many applications in Yahoo such as Homepage, Finance, Mail, Flickr, etc. use Sherpa for serving and hence, Sherpa’s latency directly impacts user engagement. Ad platforms such as Gemini also use Sherpa to insert highly targeted ads. This requires stringent latency adherence to 1-2 ms average, and less than 10ms 99% latency end to end including network round-trip within a datacenter.
Durability: Several applications in Yahoo use Sherpa as the source of truth system requiring high durability guarantees. However, many applications, especially those in ad technology and personalization, use the analytics grid as the source of truth and use Sherpa as the serving system. For such systems, durability is less of a concern as data can be quickly loaded from the grid to Sherpa.
Cost: Use of Sherpa has been growing at about 30-40% every year in both storage and queries per second (QPS). Meeting this growth in a cost efficient manner is an important focus area. Our cost benchmarks show that Sherpa’s TCO is multi-fold cheaper than comparable public cloud services.

Other requirements such as 100% uptime, horizontal scalability, ease of on-boarding and application development, geo-replication and modular architecture are assumed for Sherpa.

Differentiated Services

Traditionally, Sherpa offered a single service tier optimized for durability and latency. As application needs bifurcated across durability and latency requirements, it was more effective to introduce differentiated service tiers. To enable this, we introduced a separate service tier optimized for latency while retaining the traditional service tier for higher durability. The characteristics of these services are summarized below:

Sherpa HD: This is the traditional service tier with highly durable storage with multiple copies of data per region. This is suitable for applications that use Sherpa as the source of truth. Storage cost of this tier is lower despite the higher durability.
Sherpa LL: This is the new low latency service tier. The service provides average read latency of 1-2ms, and is suitable for applications to deliver ultra fast user experience. This service is based on PCIe Flash SSD storage and has fewer replicas of data to lower cost.

Figure 1 shows the relative read/write latencies of the two Sherpa services including network round trip. As observed in this chart, Sherpa LL provides significantly lower latency bounds at 99% for latency sensitive applications.

Figure 2 shows the TCO benchmarking of Sherpa LL with a popular public cloud service. We have chosen two record sizes, 1.5KB and 4KB, for this benchmark. As the record size increases, Sherpa cost advantage over public cloud services is even more pronounced.

Architecture Update

Sherpa architecture has been discussed in prior publications (see References section). Our solution to reduce latency while lowering cost was based on optimizing the storage node - the component of Sherpa that consists of distributed database implementation and the underlying embedded storage engine.

The architecture can be logically divided into a serving layer that front-ends REST API requests, request handlers which embed Sherpa distributed database software including query processing, sharding, consistency, failure handling, conflict resolution, etc., and the storage engine responsible for organizing data on disk.

In the legacy architecture, the serving layer used yApache, Yahoo’s customized Apache HTTP server with embedded request handlers. The HTTP server and the request handlers are now decoupled. We retained an Nginx-based HTTP server for backward compatibility with REST API. The request handlers are based on ZeroMQ. We used the ZeroMQ router-dealer pattern for increased parallelism. In addition, we adopted LSM storage based on RocksDB. Each database shard, called a tablet, is stored in a column family in RocksDB. LSM storage engine reduced read latency by 50% due to use of bloom filters and Level 0 in-memory cache. However, several optimizations were required to provide stable latency SLA, especially during compaction cycles.

Further, we introduced a proxy client in the application, which caches the mapping of a tablet to storage node and helps the application send simple Store/Retrieve queries directly to the storage unit avoiding a network hop to the Router.

For cost effectiveness, we retained storage based on magnetic media for Sherpa HD, but introduced PCIe Flash SSD for Sherpa LL to deliver lower latency. We piloted the Sherpa LL service as an in-memory database service, but with a rigorous focus on latency, including software architecture updates detailed above, we met our latency goal with PCIe Flash storage. PCIe Flash is approximately 5x cheaper than memory based on raw storage cost. Further, with PCIe Flash we can currently store 1TB of data per storage node which further reduces cost by amortizing common components over larger data density.

With all of these optimizations, we have increased the throughput per storage node by more than 20x and reduced end to end latency to 1-2ms to meet our application needs.

Future Development

Storage needs at Yahoo are growing at a rapid pace because of our initiatives across mobile, video, native advertising and social, also known as Mavens. To support this growth, we envision several improvements to Sherpa:

Cost: We are addressing cost in two dimensions: cost of storage and cost of QPS. To decrease cost of storage in Sherpa LL, we plan to increase storage capacity per node to a few terabytes. Supporting this large amount of data while maintaining ultra low latency is a tough technical challenge and requires several enhancements. We plan to increase throughput per storage node from tens of thousands to a hundred thousand, or more.
Operability: Though Sherpa operations are fully automated, troubleshooting across layers of applications, end to end, involves engineering effort. We plan to implement end-to-end monitoring and automation of troubleshooting. This will help improve the user experience, as well as, free up production engineering time.
Richer data types: With ultra low latency, Sherpa LL is eliminating the need for caching layers such as Redis. However, some applications use Redis for its richer data-types, such as lists and sorted sets. We intend to support these richer data types with Sherpa which will eliminate the need for separate caching clusters.

References: