Requirements

Functional Requirements:

• Monitor and analyze traffic to determine top-k most frequent request within a specified time interval. Here we define most frequent request to be the url that is most frequently accessed.
• Support visualization of top-k requests in a real-time leaderboard style
• Allow changing of k and time interval.
• Support querying of historic data (i.e. specify an interval)

Non-Functional Requirements:

• Favor availability over consistency. Eventual consistency is okay, ideally with low latency to reach it.
• High availability (>99.99%)
• Low latency in visualization (<200ms) and real-time updates (<200ms)
• When k and time-interval is changed, low latency in updating the calculations and visualization.
• Highly reliable, and scalable
• Assume 1min minimum granularity

API Design

// For retrieving top-k results

GET /topsites?k={k}&interval={1m|1hour|1day|n-min|...}×tamp={time} ->

{

k,

interval,

timestamp,

topK: [

{url: "", count: }

]

}

High-Level Design

Capacity estimation:

• Assume our website gets 100M visits per day
• Assume peak traffic occurs during 8 hours of a day
• Each url is 1k maximum

We might need to ingest:

• 100M * 1k = 100GB of data / day. 36TB per year
• Network: 80% traffic in 8 hours: 100M * 0.8 / 8 / 86400 = 100 / sec
• Top-K queries: 1 qps

When a request enters APIGateway, it sends the url to IngestService, which puts it on IngestQueue. Each message contains the url and the timestamp.

Persistence service takes the message off IngestQueue, and persist into blob storage, partitioned by hour. This is our raw data.

A real-time processing service (Spark streaming or Flink) takes message of IngestQueue, and aggregate it by the minute. It stores minute level aggregation in AggTable. This can be a no-sql database, such as DynamoDB, Cassandra.

A BatchProcess service runs in the background, and aggregate data into larger granularities (hour, day), and stores it into AggTable in descending order.

When querying for top-k for a given interval and given timestamp, the query service looks for the more appropriate table with the right granularity (e.g. if top-10 on Nov 10), then it looks for the daily aggregate table for Nov 10, and retrieve top 10 results.

Detailed Component Design

How to handle late data

• For stream processing it is common to specify a watermark, after which data is not processed.
• A longer watermark reduces data loss, and reduces data freshness.
• One option is to specify a shorter watermark to achieve better freshness. The in BatchProcess we reprocess the raw data with longer time delay, and update the aggregation tables.

How to show a leaderboard

• For minute level granularity, we can use polling from the client to update the leaderboard.
• SSE and websocket is overkill for this kind of time granularity.

Handling failures

How to scale the service

• IngestService, QueryService and PersistenceService are stateless and can be horizontally scaled.
• For IngestQueue, we can partition it based on url.
• Stream processing service (Spark Streaming/Flink) can be configured to run in a cluster.
• The BatchProcessing service can be a SparkService. Again configured for high availability.

Data retention

• We probably don't need to store raw data indefinitely. We can configure a 30 day retention or even short time period.. It is unlikely that data would be 30 day late.
• For aggregation data, we can expire data with shorter granularity. For example, 1 min aggregation is kept for 30 days, and 1 day aggregation is kept for 1 year.