Design a Search for Datadog

Question

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

Codemia · Accepted Answer

### Functional Requirements
1. **Search Functionality**: Users should be able to perform keyword-based searches across logs, metrics, and events.
2. **Faceted Search**: Users should be able to filter results based on various attributes such as time range, tags, and event types.
3. **Real-time Updates**: The search index should reflect new data within seconds.
4. **User Authentication**: Only authenticated users can access the search features.
5. **Result Ranking**: Search results should be ranked based on relevance.

### Non-Functional Requirements
1. **Performance**: The system should handle 1 million queries per minute with an average response time of under 200ms.
2. **Scalability**: The system must be horizontally scalable to accommodate increasing loads.
3. **Availability**: The system should have a 99.9% uptime SLA.
4. **Consistency**: Eventual consistency is acceptable for search results but should be managed to avoid showing outdated data.

Assuming we expect up to 1 million search queries per minute:
- **Queries per second (QPS)**: 1 million / 60 = 16,667 QPS.
- **Data Ingestion Rate**: If Datadog ingests 10 GB of logs and metrics per minute, and assuming a 5% indexing overhead, we need to handle approximately 10.5 GB/min for indexing.
- **Storage Requirement**: If we estimate that each indexed record takes about 1 KB, we can expect to index 10,500 records per minute, leading to a total of 630,000 records per hour. Assuming a retention period of 30 days, this would require significant storage capacity.
- **Index Size**: For an estimated 20 million records, the index may take up to 20 GB in size. Hence, we will need to provision for at least 500 GB of storage to handle growth.

### Components
1. **Load Balancer**: Distributes incoming search requests across multiple search instances.
2. **Search Service**: Handles queries and interacts with the search index (using Elasticsearch).
3. **Indexing Service**: Responsible for ingesting logs and metrics, processing them, and updating the search index.
4. **Caching Layer**: Redis for caching frequently searched queries to improve performance.
5. **Authentication Service**: Verifies user credentials and supports roles and permissions.

### Technology Choices
- **Search Engine**: Elasticsearch for full-text search capabilities.
- **Database**: A NoSQL database like MongoDB for storing raw logs and metrics, allowing for flexible schema.
- **Message Queue**: Kafka for handling asynchronous data ingestion, ensuring high throughput and reliability.

### Schema Design
- **Log Entry Document**:
  - `timestamp`: DateTime, indexed
  - `service`: String, indexed
  - `level`: String, indexed
  - `message`: Text (full-text indexed)
  - `tags`: Array of Strings (for faceted search)

### Access Patterns
1. **Search by Time**: Queries will often filter by timestamp, so indexing on this field is crucial.
2. **Faceted Filters**: The service and level fields will be frequently used in filtering, requiring efficient indexing.
3. **Text Search**: The message field will leverage full-text search capabilities for keyword queries.

### Consistency vs. Availability
- **Eventual Consistency**: For search results, we can afford eventual consistency since some lag in data availability is acceptable for the use case.

### Caching vs. Freshness
- **Using Caching**: Implementing Redis for caching can significantly reduce response times but may serve stale data. A TTL (Time-to-Live) strategy can mitigate this by ensuring that cache is refreshed periodically.

### Complexity vs. Performance
- **Indexing Complexity**: More complex indexing strategies (like maintaining multiple indices for different types of logs) can improve performance but increase system complexity and maintenance overhead. A simpler strategy with one index may be more manageable but could lead to performance degradation over time as data scales.

Design a Search for Datadog

Datadog

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Practice a Similar Problem on Codemia

Sample Answer

Requirements

Functional Requirements

Capacity Estimation

Submit Your Answer

Datadog 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