Microsoft Coding：流式 Error Count、Moving Average 与告警

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练合同输入及查询时间非递减，窗口(now−W,now]；过滤level精确等于ERROR，W>0。
• moving average选择窗口每秒错误数=count/W，不是错误事件占全部日志比例；若求error ratio必须额外维护全部日志数量。
• 示例不做事件去重、不支持迟到；它们是单独接口扩展，不默默丢弃旧事件。

解题路线

1. 队列存(timestamp,service)的错误事件，Counter存每服务活跃错误数。每次advance弹出timestamp≤now−W的事件并减计数，入队新错误时加计数。INFO/WARN仍推进时间，防止空错误期保留旧值。
2. 查询也先advance，保证没有新日志时窗口能归零。统一边界判断并对同一时间多个事件保留 multiplicity；若原合同需要去重，先定义event_id和去重保留期。
3. 速率count/W用整个W作分母，包含空秒。若要启动初期按实际观察时长归一，则分母另定义，不能两个时段混用。告警可设进入/退出阈值与持续时间避免抖动，并按service+window身份防重复通知。
4. 乱序场景需event-time水位、时间桶或有序结构，延迟刷新与更正明确。单FIFO过期仅在时间有序时正确；在advance后接受旧事件会污染已最终窗口。
5. 线程安全将advance/ingest/stats原子保护；多机按service分区，状态checkpoint与日志位置协调。低量服务也应有最小样本/绝对量政策，错误占比与每秒速率用于不同故障类型。

手动走一遍

训练例W=10，serviceA在t=0、t=5出现ERROR。query(10)窗口(0,10]排除t=0，返回count1、rate0.1/s。query(15)排除t=5，返回0；没有新日志也必须清理。若每条ERROR写两次，按本文未去重合同算两次。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import Counter, deque


class ErrorWindow:
    def __init__(self, window_seconds):
        if window_seconds <= 0:
            raise ValueError("positive window required")
        self.window = window_seconds
        self.events = deque()
        self.counts = Counter()
        self.now = float("-inf")

    def advance(self, now):
        if now < self.now:
            raise ValueError("timestamps must be nondecreasing")
        self.now = now
        while self.events and self.events[0][0] <= now - self.window:
            _, service = self.events.popleft()
            self.counts[service] -= 1
            if self.counts[service] == 0:
                del self.counts[service]

    def ingest(self, timestamp, service, level):
        self.advance(timestamp)
        if level == "ERROR":
            self.events.append((timestamp, service))
            self.counts[service] += 1

    def stats(self, now, service):
        self.advance(now)
        count = self.counts.get(service, 0)
        return count, count / self.window

复杂度

每事件入/出队各一次，ingest与advance均摊O(1)，单次长时间跳跃可清理O(e)事件。空间O(窗口内错误事件数+活跃服务数)。独立history扫描核对40,000次查询，覆盖同时间、空闲、边界、非ERROR和未知服务；迟到输入明确拒绝。

易错点与追问

容易失分的边界

• 只在ERROR到达时过期，闲时告警不恢复。
• count/W和errors/total_logs混称average。
• 队列支持乱序却没有排序或水位。
• 端点≤与<不一致。

继续深挖

• 窗口很长如何用秒桶降低内存？
• 必须精确到毫秒时桶边界怎么处理？
• 上游重发如何去重及恢复去重状态？
• 告警重试怎样避免重复分页通知？