Search Recorded Metrics by Name, Tags, and Recency

Problem Statement

You are tasked with building an in-memory metric storage engine, MetricStore, to collect runtime statistics from serverless deployments and query them efficiently.

Each recorded metric consists of:

• name: A string identifier for the metric (e.g., "http_requests").
• value: A floating-point measurement.
• tags: A dictionary of key-value string pairs representing metadata (e.g., {"region": "iad1", "status": "200"}).
• timestamp: An integer representing the epoch timestamp in milliseconds.

Implement the MetricStore class with two methods:

1. record(name: str, value: float, tags: dict[str, str], timestamp: int) -> None

   • Stores the metric event. Multiple events can share the same name, timestamp, and tags.

2. query(name: str, tags: dict[str, str], limit: int) -> list[dict]

   • Returns up to limit recorded metrics that match the given name and contain all key-value pairs specified in tags (i.e., query tags must be a subset of the metric's tags; an empty query tags dictionary matches all tag sets).
   • Results must be sorted primarily by timestamp in descending order (most recent first).
   • In case of timestamp ties, break ties by insertion order descending (the metric recorded later appears first).
   • Each returned metric should be represented as a dictionary: {"name": str, "value": float, "tags": dict[str, str], "timestamp": int}.

Example

store = MetricStore()

store.record("cpu_usage", 75.5, {"env": "prod", "host": "a"}, 1000)
store.record("cpu_usage", 82.0, {"env": "prod", "host": "b"}, 1020)
store.record("cpu_usage", 40.0, {"env": "dev", "host": "c"}, 1050)
store.record("cpu_usage", 90.0, {"env": "prod", "host": "a"}, 1020)

# Query cpu_usage for prod environment, limit 2
results = store.query("cpu_usage", {"env": "prod"}, 2)
# Explanation:
# Matches: host 'b' at 1020, host 'a' at 1020, host 'a' at 1000.
# Both host 'b' and host 'a' have timestamp 1020; host 'a' was recorded after host 'b',
# so host 'a' comes first in the tiebreak.
# Output:
# [
#   {"name": "cpu_usage", "value": 90.0, "tags": {"env": "prod", "host": "a"}, "timestamp": 1020},
#   {"name": "cpu_usage", "value": 82.0, "tags": {"env": "prod", "host": "b"}, "timestamp": 1020}
# ]

Constraints

• name is a non-empty string consisting of alphanumeric characters and underscores (1 <= len(name) <= 100).
• tags contains between 0 and 20 key-value string pairs.
• 1 <= timestamp <= 2^63 - 1. Timestamps are not guaranteed to arrive in strictly chronological order.
• 1 <= limit <= 1000.
• Total calls to record and query: up to 50,000.

Edge Cases

• Empty query tags: should match any metric with the specified name.
• limit greater than the number of matching metrics: return all matches.
• Metrics recorded with identical name, tags, timestamp, and value should still be treated as distinct events.