The architecture of Yelp's in-house Search Engine - nrtSearch



2193 views Backend System Design



Elasticsearch is a great search engine, but Yelp was not happy with its performance, so they built their own HTTP layer on top of Lucene. Here’s the architecture of it…

Why not Elasticsearch?

  1. ES replication is naive. The operations that happen on the master are re-done on replicas; hence scaling is not cheap.
  2. ES suffers from the Hot Node problem and requires manual moving of the shards across nodes to balance the load.
  3. ES autoscaling is time-consuming and hence we always provision it for the peak load.

Key features of Lucene

Near Realtime Indexes

In Lucene, the data of an index is stored in an immutable structure called Segment. Once the segment is written it can be quickly copied to a replica, in near-real-time. Thus, replication does not require the Replicas to re-index the documents, making it super-efficient to scale out.

Concurrent Search on Segments

Search in Lucene is parallelized on segments. Hence for a given search query, Lucene can make parallel searches across segments using multiple threads and compute the most relevant results. It helps in leveraging all the cores of the underlying hardware.

Elasticsearch lacks the above features and is expensive in most cases, and hence Yelp thought of writing their own performant HTTP layer on top of Lucene, similar to Elasticsearch; and they call it nrtSearch.

Implementation Details

gRPC and Protobuf

Instead of using standard JSON-based endpoints for communication, nrtSearch uses gRPC/protobuf-based endpoints, saving a ton of time spent in serialization and de-serialization of the data.

To support existing systems that understand JSON, nrtSearch also provides a REST server built using gRPC-gateway. This gives clients an option to talk over gRPC or REST.

Quick Failovers

Failovers are painful with Lucene. A standard flow is to backup the index segments on S3 and when a new node spins up, download the required segments and start serving the request.

To make failover quicker, Yelp used EBS by AWS which is like pluggable storage. The index segments are stored on these EBS volumes.

When a node goes down, and a new node spins up, instead of downloading the segments from S3, the unaffected EBS volume is attached to the new node. This makes the recovery happen in seconds instead of minutes.

Replication

When the new segments are created on the master node, the master notifies all the replicas about it. The replicas then fetch the newly created segments from the Master over gRPC and maintain an eventual sync.

Performance Improvements

Virtual Sharding

Search in Lucene happens over segments, and the worst we can do is spin one thread for searching over each segment. This is sub-optimal and hence, the segments are virtually sharded.

Search Threads are capped and the segments are grouped greedily into slices. One search thread is allotted to each slice, thus searching over multiple segments in one go.

This logical abstraction helps in maintaining consistent utilization of search threads for a given search request.

Other improvements

  1. Fetching document fields in parallel
  2. Segment-level search timeout to maintain consistent SLA

Migration from ES to nrtSearch

Dark Launch

Instead of directly launching the nrtSearch to the public, it is important to test the correctness of the response on production data. Hence, the first phase of the launch is a Dark launch.

The idea is to serve the entire 100% of requests from Elasticsearch, but send 5% of the requests to the new nrtSearch. The responses of this 5% of the request are compared with the legacy system.

Once the difference is analyzed and confidence is built on the correctness, the percentage is increased to 10, 15, 20, and 50%.

Phased Rollout

Once there was 100% confidence in nrtSearch, the changes were rolled out to the general users in a phased manner and this time the requests we exclusively bifurcated across Elasticsearch and nrtSearch.

The initial percentage was 5%, eventually increasing it to 100% and then plugging out the legacy Elasticsearch.


Arpit Bhayani

Arpit's Newsletter

CS newsletter for the curious engineers

❤️ by 21000+ readers

If you like what you read subscribe you can always subscribe to my newsletter and get the post delivered straight to your inbox. I write essays on various engineering topics and share it through my weekly newsletter.




Other essays that you might like


Overview of Discord's data platform that daily processes petabytes of data and trillion points

924 views 54 likes 2022-11-14

When a company scales, they adopt microservices and each service typically gets its own independent database. With data ...

How Airbnb designed and scaled its central authorization system - Himeji

2206 views 98 likes 2022-11-07

Authorization plays a critical role in ensuring that the platform is not abused. For example, Instagram ensures that if ...

How Gojek masks and keeps users' phone numbers secure at scale?

2572 views 152 likes 2022-10-31

Do hyperlocal companies like Uber, Ola, Swiggy, Gojek, Zomato, etc share our phone numbers with the delivery people or t...

The architecture of Yelp's in-house Search Engine - nrtSearch

2193 views 81 likes 2022-10-24

Elasticsearch is a great search engine, but Yelp was not happy with its performance, so they built their own HTTP layer ...


Be a better engineer

A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.


Paid Courses

System Design Masterclass

A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.

1000+ learners

Details →

Redis Internals

Learn internals of Redis by re-implementing some of the core features in Golang.

28+ learners

Details →

Free Courses

Designing Microservices

A free playlist to help you understand Microservices and their high-level patterns in depth.

17+ learners

Details →

GitHub Outage Dissections

A free playlist to help you learn core engineering from outages that happened at GitHub.

67+ learners

Details →

Hash Table Internals

A free playlist to help you understand the internal workings and construction of Hash Tables.

25+ learners

Details →

BitTorrent Internals

A free playlist to help you understand the algorithms and strategies that power P2P networks and BitTorrent.

42+ learners

Details →

Topics I talk about

Being a passionate engineer, I love to talk about a wide range of topics, but these are my personal favourites.





  • v13.7.5
  • © Arpit Bhayani, 2022

Powered by this tech stack.