Architect a distributed Search Engine

Question

Design a distributed search system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

For Expedia, I would design a distributed travel search engine that powers hotel, flight, and package search across web and mobile. I would start by scoping the technical screen version to **hotel search**, because it still captures the core distributed search problems: location filtering, availability, pricing, ranking, caching, and high request volume.

**Functional requirements:**

- Users can search hotels by destination, check-in/check-out dates, guest count, rooms, price range, star rating, amenities, brand, cancellation policy, and distance from landmarks.
- Search results should return hotel metadata, available room offers, price, taxes/fees, review score, images, and ranking signals.
- Users can sort by recommended, price, distance, rating, or deals.
- The system should support pagination or cursor-based result fetching.
- Inventory and price changes from hotel suppliers should be reflected quickly, but search results do not need strict read-after-write consistency.
- The system should support personalization signals such as user loyalty tier, location, previous searches, and device type.
- The system should expose APIs for Expedia web, mobile apps, partner integrations, and internal ranking/experimentation systems.
- The system should rate-limit abusive clients, bots, and misconfigured partners.

**Non-functional requirements:**

- Handle millions of search requests per day, with high traffic during travel planning windows, holidays, and marketing campaigns.
- Low latency: target p50 under 150 ms and p95 under 500 ms for cached or indexed search responses, excluding slow third-party supplier calls.
- High availability: target 99.9%+ for search reads, because search is the front door of Expedia booking flow.
- Search can be eventually consistent for price/inventory, but booking checkout must verify real-time price and availability before payment.
- Horizontally scalable across regions.
- Graceful degradation: if personalization, ranking, or a supplier feed is degraded, return reasonable default search results rather than failing the whole request.
- Strong observability across latency, cache hit rate, supplier freshness, index lag, query errors, and zero-result searches.

Assume Expedia hotel search receives about **50 million hotel search requests per day** globally.

**Traffic estimate:**

- Average QPS: `50M / 86,400 ≈ 580 QPS`
- Peak multiplier: travel traffic is bursty, so assume 10x peak
- Peak search QPS: `~5,800 QPS`
- If each user makes 3 paginated result calls per search session, backend result-fetch QPS could reach `~17,000 QPS` at peak.

**Data estimate:**

- Hotels indexed globally: assume 1 million properties.
- Average searchable hotel document: 5 KB including geo fields, amenities, normalized text, ratings, ranking features, and references to active offers.
- Base hotel index size: `1M * 5 KB = 5 GB` before replication and indexing overhead.
- With inverted index overhead, geo indexes, replicas, and versioning, assume 5x overhead: `~25 GB` per full hotel index.
- This is small enough for Elasticsearch/OpenSearch clusters, but the challenge is not raw hotel metadata size; it is **availability and price freshness**.

**Availability and price data:**

- Suppose each hotel has 20 room/rate plans and 365 days of availability.
- Raw offer records: `1M hotels * 20 rates * 365 days = 7.3B hotel-night rate records`.
- Average compressed rate record: 100 bytes to 200 bytes.
- Storage: `~730 GB to 1.5 TB` before replication.
- With 3x replication and indexes: `~3 TB to 6 TB`.

**Cache estimate:**

- Popular destinations dominate traffic: Las Vegas, Orlando, NYC, London, Paris, Cancun, etc.
- If the top 5% of query shapes produce 60% of traffic, caching normalized search results can dramatically reduce load.
- Cache key could include destination, date range, occupancy, filters, sort mode, locale, currency, and experiment bucket.
- Cache TTL should be short for price-sensitive results, for example 1 to 5 minutes, while static hotel metadata can cache for hours.

A reasonable Expedia-specific architecture would separate **search retrieval**, **price/availability freshness**, and **ranking**.

Async ingestion path:

Hotel Suppliers / Internal Inventory Systems
        |
        v
Kafka Topics
        |
        v
Stream Processors: Flink / Kafka Streams
        |
        +--> OpenSearch index updates
        +--> Cassandra/DynamoDB price availability updates
        +--> Redis cache invalidation events
        +--> Data lake for analytics and ML training
```

**Core components:**

- **API Gateway:** Handles authentication, partner quotas, bot protection, request normalization, and rate limiting. For example, unauthenticated users may get lower QPS limits than trusted Expedia mobile clients or partner APIs.
- **Search Aggregator Service:** Stateless service written in Java/Kotlin/Go. It parses the query, checks cache, queries OpenSearch, fetches availability/prices, calls ranking, and composes the response.
- **OpenSearch/Elasticsearch:** Stores searchable hotel documents with inverted indexes, geo indexes, filters, and ranking fields. This is the main retrieval engine.
- **Redis/Memcached:** Caches popular query results and partial objects such as hotel summaries, destination mappings, and ranking feature lookups.
- **Cassandra or DynamoDB:** Stores high-volume hotel availability and rate records keyed by hotel/date/occupancy patterns. This is better than forcing all volatile price data into the search index.
- **Kafka:** Decouples supplier updates from indexing. Supplier feeds can be noisy, late, duplicated, or bursty, so Kafka gives buffering and replay.
- **Flink/Kafka Streams:** Deduplicates, validates, enriches, and writes inventory/rate updates to the search index and availability store.
- **Ranking Service:** Applies Expedia-specific ranking such as conversion probability, margin, loyalty eligibility, review quality, distance, sponsored placement, and experiment variants.
- **Observability:** Use Prometheus/Grafana or Datadog for metrics, OpenTelemetry for traces, and centralized logging through ELK/Splunk.

**OpenSearch hotel document:**

```json
{
  "hotel_id": "h_12345",
  "name": "Expedia Downtown Seattle Hotel",
  "destination_ids": ["seattle", "downtown-seattle"],
  "geo": { "lat": 47.6101, "lon": -122.2015 },
  "star_rating": 4,
  "guest_rating": 8.7,
  "amenities": ["wifi", "pool", "parking", "pet_friendly"],
  "brands": ["example_brand"],
  "property_type": "hotel",
  "image_score": 0.93,
  "quality_score": 0.88,
  "base_rank_score": 0.76,
  "active": true
}
```

OpenSearch is optimized for access patterns like: destination + date + occupancy + filters + geo radius + sort/rank. I would keep mostly stable hotel metadata here and avoid constantly reindexing every price change.

**Availability table in Cassandra/DynamoDB:**

```text
Table: hotel_rate_availability
Partition key: hotel_id
Sort key: stay_date#occupancy#rate_plan_id
Columns:
- available_rooms
- refundable
- cancellation_policy_id
- base_price
- taxes_fees
- currency
- supplier_id
- last_updated_at
- version
```

For destination searches, the flow is:

1. Query OpenSearch for candidate hotel IDs matching destination, geo, filters, and quality constraints.
2. Fetch price/availability for the top N candidates from Cassandra/DynamoDB.
3. Remove unavailable hotels.
4. Call ranking service.
5. Return the top results with a cursor.

**Search API:**

```http
GET /v1/hotels/search?destination=seattle&checkIn=2026-08-10&checkOut=2026-08-13&adults=2&rooms=1&sort=recommended&currency=USD
```

Example response:

```json
{
  "query_id": "q_abc123",
  "results": [
    {
      "hotel_id": "h_12345",
      "name": "Expedia Downtown Seattle Hotel",
      "price": { "total": 642.18, "currency": "USD" },
      "guest_rating": 8.7,
      "star_rating": 4,
      "distance_miles": 0.8,
      "refundable": true
    }
  ],
  "next_cursor": "eyJvZmZzZXQiOjI1fQ=="
}
```

At checkout, Expedia should not trust cached search price as final. The booking service must call a real-time price/availability verification path before payment.

**Consistency vs performance:**

For Expedia search, I would choose eventual consistency. Search results can show a price that is a few minutes stale, but checkout must verify the final price. This keeps search fast and highly available while protecting booking correctness.

**Availability vs completeness:**

If one supplier feed or pricing service is slow, the system should still return hotels from cached data or other suppliers. It is better for users to see slightly fewer results than to receive a failed search page.

**Indexing price data vs separate availability store:**

Putting all prices directly into OpenSearch simplifies querying, but it causes massive reindexing pressure because prices and inventory change frequently. I would keep stable searchable metadata in OpenSearch and volatile price/availability in Cassandra/DynamoDB. The trade-off is more service-side joining, but it improves write scalability and index stability.

**Caching trade-off:**

Caching popular searches reduces latency and cost, especially for common destinations and date windows. The risk is stale prices. I would use short TTLs, event-based invalidation for major supplier updates, and clear final-price verification during booking.

**Failure handling:**

- OpenSearch shards should have replicas across availability zones.
- Search Aggregator instances should be stateless and horizontally scaled behind a load balancer.
- Kafka provides replay if indexers fail.
- Stream processors should be idempotent using supplier update version numbers.
- Redis failures should degrade to direct OpenSearch queries, not full outages.
- Ranking service failures should fall back to deterministic ranking using base quality score, price, rating, and distance.

**Monitoring and alerting:**

Track p50/p95/p99 latency, OpenSearch query latency, cache hit rate, index lag, Kafka consumer lag, supplier update failure rate, zero-result rate, stale-price rate at checkout, and search-to-book conversion. For Expedia, stale-price rate is especially important because it directly damages user trust during booking.

**Likely bottlenecks:**

- Hot destination queries causing OpenSearch pressure: mitigate with query-result caching and shard planning.
- Price/availability fanout for too many hotels: retrieve only top candidate IDs first, then batch-fetch prices for a limited candidate set.
- Supplier update bursts: buffer through Kafka and use backpressure.
- Ranking latency: precompute common features and use a lightweight online ranker.
- Cache key explosion from filters and personalization: cache base result sets separately from user-specific reranking where possible.

Architect a distributed Search Engine

Expedia

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Practice a Similar Problem on Codemia

Sample Answer

1. Requirements And Scope

2. Capacity Estimation

Submit Your Answer

Expedia Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search