Typeahead Search at Nextdoor

Jerry Tian6 Jul 2022

Problem

Nextdoor users mention nearby people and businesses in posts and comments, and they search for them in the search box. Every one of these features needs suggestions that appear while the user types. Relevance depends heavily on distance, because the platform is hyperlocal. The service has to answer in under 50 ms at the service level, across hundreds of millions of entities, and new entities must be indexed in hours without slowing production traffic. Millions of at-mentions are created each month.

Example from the article: a user types "@St" in a comment. The service returns "Starbucks" (a business) and "Steve Jobs" (a user) found near the user's location.

Solution in brief

Divide the map into H3 cells and store every name prefix of every entity under a key made of entity type, cell and prefix. A query becomes a single in-memory lookup in Redis sorted sets by type, cell and typed prefix. Writes go to Redis primary nodes and reads to replicas, so bulk indexing does not touch serving.

Questions this case answers
  • How to return prefix-matched results within a tight latency budget when relevance depends on the searcher's location and the entity set is very large
  • How to bulk-index a very large entity set for an in-memory lookup service without degrading serving traffic
  • How to build typeahead search that returns nearby users and businesses in under 50 ms over hundreds of millions of entities?
  • How to weight typeahead results by geographic proximity without a heavy search engine?

Tools and methods

  • H3 (Uber's open-source hexagonal grid) — maps latitude and longitude to a cell id that shards entities by proximity.
  • Redis sorted sets — in-memory store with built-in persistence, one key per type, cell and prefix.
  • CQRS — ingestion on primary nodes, search on read-only replicas.
  • indexing_api, typeahead_api, ranking_api — ingestion, lookup, and ranking by entity type.
Continue reading — it's free

Google or a one-time email code. No password.