Typeahead Search at Nextdoor

Summary

Nextdoor built a proximity-based autocomplete service to power typeahead search and mention features across its hyperlocal platform for hundreds of millions of entities, including users and businesses. The system shards geographic data using Uber's open-source H3 geohashing library and stores prefix indexes in memory using Redis sorted sets. By adopting a Command Query Responsibility Segregation architecture, ingestion writes are processed on Redis primary nodes and replicated to read-only search nodes with under 10 milliseconds of replication lag. Dedicated APIs handle indexing, typeahead lookups, and ranking before returning hydrated results. Operating since August 2021, the service processes hundreds of millions of monthly typeahead queries while maintaining a P95 search latency below 30 milliseconds.

Context

Nextdoor required a proximity-based typeahead autocomplete service for at-mentions and search across hundreds of millions of users and businesses. The service needed to maintain search latency under 50ms, scale horizontally, support high write throughput to index hundreds of millions of entities in hours, and serve search traffic without production impact during indexing.

Approach / What changed

The team implemented an in-memory solution using Uber's open-source H3 geohashing library to shard data into buckets by proximity. Redis sorted sets were selected for fast typeahead lookups and built-in persistence. Under a CQRS pattern, ingestion is handled by Redis primary nodes and replicated to read-only search nodes with under 10ms replication lag. A suite of indexing, typeahead, and ranking APIs ingest data and look up results by entity type, geohash key, and prefix before hydrating and ranking them.

Takeaways

• Uber's open-source H3 geohashing library divides geographic coordinates into zones, allowing large entity datasets to be sharded into proximity-based buckets.
• Applying the CQRS pattern with Redis primary nodes for ingestion and read-only nodes for queries isolates indexing workloads from search traffic, maintaining replication lag below 10ms.
• Typeahead queries perform direct lookups against Redis sorted sets using entity type, geohash key, and prefix before hydrating and ranking results, achieving a P95 latency below 30ms.

Related reading