Học từ Facebook #69: Thống kê cửa sổ trượt và đại số khoảng thời gian

Hai câu hỏi hay gặp khi làm client: "trong 30 giây vừa rồi có bao nhiêu sự kiện?" và "từ ngày A tới ngày B là bao nhiêu tháng?". Câu đầu dùng để chặn vòng lặp kết nối lại, giới hạn log, đo tốc độ. Câu sau dùng cho "Đã tham gia 3 năm 2 tháng", hạn dùng thử, tuổi.

Cả hai nghe đơn giản nhưng dễ sai ở mép. Bài này đọc hai module nhỏ của Facebook là MovingStat và TimeInterval, chỉ ra chỗ chúng sai, rồi viết lại.

▶ Mở demo toàn màn hình ↗ · Sửa code trên StackBlitz ↗ · Xem source trên GitHub ↗

#Facebook làm thế nào?

#MovingStat: danh sách liên kết các bucket

Module MovingStat nằm trong 225.js, ngắn tới mức đọc hết được trong một màn hình. Bỏ tên biến rút gọn đi thì nó như sau:

add(v) {
  this.sum += v; this.count++;
  if (new Date() - this.tail.t < 1e3) { this.tail.v += v; this.tail.count++; return; }
  this.tail = this.tail.next = { t: new Date(), v, count: 1 };
  this.evict();
}
tally(per = 1e3) { this.evict(); return { sum: this.sum, count: this.count, timeAverage: this.sum * per / this.window }; }
evict() {
  const cutoff = new Date() - this.window;
  while (this.head && this.head.next && this.head.t < cutoff) { /* trừ sum, count rồi */ this.head = this.head.next; }
}

Constructor nhận độ dài cửa sổ (mặc định 6e4, tức 60 giây) và tạo sẵn một bucket rỗng tại thời điểm khởi tạo làm cả head lẫn tail.

Ý tưởng tốt: không lưu từng sự kiện mà gộp theo giây, nên bộ nhớ tối đa khoảng 60 bucket dù có hàng nghìn sự kiện. sum và count được cộng/trừ dần, tally() là O(số bucket hết hạn).

Người dùng chính trong bundle là ChannelManager, lớp quản lý kênh long-polling cũ của chat:

this._transportRate = new (b("MovingStat"))(3e4);
// mỗi lần đổi trạng thái kênh
this._transportRate && this._transportRate.add(1);
// khi vào trạng thái lỗi
var e = this._transportRate.tally().timeAverage, f = this.getConfig("MAX_CHANNEL_STATES_PER_SEC", 1);
e >= f && (this._throttled || (this._throttled = !0, /* … hãm lại */));

Kênh đổi trạng thái liên tục (pull → lỗi → pull → lỗi…) là dấu hiệu vòng lặp kết nối lại. Trung bình trên 30 giây vượt 1 lần/giây thì client tự hãm để không dội request lên server.

#Hai chỗ sai

flowchart LR
  B1["bucket 0s: 10"] --> B2["bucket 1s: 10"] --> B3["bucket 2s: 10"]
  E["evict lúc 64s"] -->|"bỏ"| B1
  E -->|"bỏ"| B2
  E -.->|"không bỏ vì không có next"| B3
  B3 --> S["tally: sum = 10 dù 61 giây im lặng"]

1. Điều kiện this.head.next khiến bucket cuối cùng luôn ở lại. Ở phần 1 của demo: bắn 30 sự kiện trong 3 giây, tua 61 giây, bản kiểu Facebook vẫn báo tổng 10. Với ChannelManager điều này ít khi gây hại vì ngưỡng là 30 sự kiện, nhưng với một bộ đếm lỗi để hiện cảnh báo thì cảnh báo sẽ không bao giờ tắt.
2. timeAverage = sum * per / window luôn chia cho 30 giây. Ba giây đầu có 30 lần đổi trạng thái (10 lần/giây, rõ ràng là vòng lặp) thì timeAverage chỉ là 1. Ngưỡng >= 1 vừa chạm nên trường hợp này vẫn bị chặn, nhưng 20 lần trong 3 giây thì không: client phải đợi thêm vài chục lần lặp nữa mới tự hãm.

Ngoài ra bucket được bỏ khi thời điểm bắt đầu của nó đã quá cửa sổ, trong khi các sự kiện cuối bucket có thể vẫn còn trong cửa sổ. Sai số tối đa một bucket, chấp nhận được, nhưng nên biết đó là xấp xỉ.

#TimeInterval: khoảng nửa mở và đo theo lịch

Module TimeInterval (trong 233.js) giữ start, end (giây Unix) và timezoneID. Các phép so sánh đều quy về hai số max(start) và min(end):

c.abuts    = a => Math.max(this.start, a.start) === Math.min(this.end, a.end);
c.overlaps = a => Math.max(this.start, a.start) <  Math.min(this.end, a.end);
c.intersects = a => Math.max(this.start, a.start) <= Math.min(this.end, a.end);
c.union = b => this.intersects(b) ? a.create(Math.min(...), Math.max(...), tz) : null;

Phân biệt overlaps (chồng thật) và intersects (chồng hoặc dính mép) là điểm hay: 9:00–10:00 và 10:00–11:00 không chồng nhau (không trùng lịch) nhưng vẫn gộp được thành 9:00–11:00.

Đo theo tháng thì không chia cho 30:

case PeriodUnit.month:
  e = 12 * (d.getYear() - c.getYear()) + (d.getMonth() - c.getMonth());
  for (var f = e; Math.max(0, e - 2) < f; f -= 1)
    if (c.addMonths(f).instant <= d.instant) break;
  return f;

Ước lượng bằng hiệu năm/tháng, rồi lùi tối đa hai bước tới khi cộng f tháng vào ngày đầu không vượt ngày cuối. toPeriodIn(["year", "month", "week", "day"]) đo đơn vị lớn nhất, cộng phần đó vào start, rồi đệ quy cho phần còn lại.

#Viết lại

src/lib/movingStat.ts cho bộ đếm, src/lib/timeInterval.ts cho khoảng thời gian.

Bộ đếm dùng mảng thay vì danh sách liên kết, đồng hồ truyền vào được. evict so thời điểm kết thúc của bucket với mốc cắt và không đòi bucket phải có phần tử sau nó:

/**
 * Thống kê trên cửa sổ thời gian trượt, gộp mẫu vào bucket (ý tưởng từ MovingStat của Facebook).
 *
 * Không lưu từng mẫu: mẫu rơi vào cùng một bucket (mặc định 1 giây) thì cộng dồn.
 * Hỏi `tally()` thì bỏ các bucket đã ra khỏi cửa sổ rồi trả sum/count/trung bình.
 *
 * Khác bản gốc:
 * - Bản gốc không bao giờ bỏ bucket cuối cùng (điều kiện vòng lặp đòi bucket phải có `next`),
 *   nên sau một lúc im lặng `tally()` vẫn trả số liệu cũ. Bản này bỏ cả bucket cuối.
 * - Bucket được bỏ theo thời điểm KẾT THÚC (start + bucketMs), không theo lúc bắt đầu.
 * - Trung bình chia cho phần cửa sổ đã thực sự trôi qua, không chia cả cửa sổ khi vừa khởi tạo.
 * - Đồng hồ truyền vào được, để test và demo tua thời gian.
 */

interface Bucket {
  start: number;
  sum: number;
  count: number;
}

export interface MovingStatOptions {
  windowMs?: number;
  bucketMs?: number;
  now?: () => number;
}

export class MovingStat {
  private buckets: Bucket[] = [];
  private sum = 0;
  private count = 0;
  private readonly createdAt: number;
  readonly windowMs: number;
  private readonly bucketMs: number;
  private readonly now: () => number;

  constructor({ windowMs = 60_000, bucketMs = 1_000, now = Date.now }: MovingStatOptions = {}) {
    this.windowMs = windowMs > 0 ? windowMs : 60_000;
    this.bucketMs = bucketMs;
    this.now = now;
    this.createdAt = now();
  }

  add(value: number) {
    const t = this.now();
    this.evict(t);
    this.sum += value;
    this.count++;
    const last = this.buckets[this.buckets.length - 1];
    if (last && t - last.start < this.bucketMs) {
      last.sum += value;
      last.count++;
    } else {
      this.buckets.push({ start: t, sum: value, count: 1 });
    }
  }

  /** `per`: trung bình trên mỗi `per` ms, mặc định "mỗi giây". */
  tally(per = 1_000) {
    const t = this.now();
    this.evict(t);
    const elapsed = Math.min(this.windowMs, Math.max(t - this.createdAt, this.bucketMs));
    return { sum: this.sum, count: this.count, ratePer: (this.sum * per) / elapsed, buckets: this.buckets.length };
  }

  private evict(t: number) {
    const cutoff = t - this.windowMs;
    let drop = 0;
    while (drop < this.buckets.length && this.buckets[drop].start + this.bucketMs <= cutoff) {
      this.sum -= this.buckets[drop].sum;
      this.count -= this.buckets[drop].count;
      drop++;
    }
    if (drop > 0) this.buckets.splice(0, drop);
  }
}

Đếm tháng trọn và quy ra năm/tháng/ngày:

/**
 * Số tháng TRỌN giữa start và end. Ước lượng bằng hiệu năm/tháng, rồi lùi tối đa 2 bước
 * cho tới khi start + n tháng không vượt end (cùng cách bản gốc làm).
 */
export function wholeMonths(iv: Interval): number {
  const a = new Date(iv.start);
  const b = new Date(iv.end);
  const guess = (b.getUTCFullYear() - a.getUTCFullYear()) * 12 + (b.getUTCMonth() - a.getUTCMonth());
  for (let n = guess; n > Math.max(0, guess - 2); n--) {
    if (addMonthsUTC(iv.start, n) <= iv.end) return n;
  }
  return Math.max(0, guess - 2);
}

export interface Period {
  years: number;
  months: number;
  days: number;
}

/**
 * "Bao lâu" theo lịch. Luôn cộng từ mốc start (không cộng dồn từng tháng một),
 * vì 31/1 +1 tháng +1 tháng = 28/3 còn 31/1 + 2 tháng = 31/3.
 */
export function toPeriod(iv: Interval): Period {
  const total = wholeMonths(iv);
  const anchor = addMonthsUTC(iv.start, total);
  return { years: Math.floor(total / 12), months: total % 12, days: Math.floor((iv.end - anchor) / DAY) };
}

/**
 * Khoảng thời gian nửa mở [start, end) và phép đo theo lịch (ý tưởng từ TimeInterval của Facebook).
 *
 * Đơn vị là mili giây UTC để ví dụ gọn; bản gốc dùng giây Unix + timezoneID và đo ngày/tháng
 * theo lịch của múi giờ đó. Muốn đo theo múi giờ khác thì đổi `addMonthsUTC` sang hàm cộng tháng
 * theo múi giờ (ví dụ Temporal.ZonedDateTime.add).
 */

export class Interval {
  constructor(
    readonly start: number,
    readonly end: number,
  ) {
    if (!(start <= end)) throw new RangeError(`Interval: start (${start}) phải <= end (${end})`);
  }

  static of(a: Date | number, b: Date | number) {
    return new Interval(+a, +b);
  }

  get length() {
    return this.end - this.start;
  }

  contains(t: number) {
    return this.start <= t && t < this.end;
  }

  /** dính mép: [0,5) và [5,9) */
  abuts(o: Interval) {
    return Math.max(this.start, o.start) === Math.min(this.end, o.end);
  }

  /** chồng lên nhau thật sự (dính mép không tính) */
  overlaps(o: Interval) {
    return Math.max(this.start, o.start) < Math.min(this.end, o.end);
  }

  /** phần chung; dính mép trả về khoảng rỗng [5,5), rời nhau trả về null */
  intersect(o: Interval): Interval | null {
    const s = Math.max(this.start, o.start);
    const e = Math.min(this.end, o.end);
    return s <= e ? new Interval(s, e) : null;
  }

  /** khoảng trống giữa hai khoảng rời nhau, null nếu chúng chạm hoặc chồng nhau */
  gap(o: Interval): Interval | null {
    const s = Math.min(this.end, o.end);
    const e = Math.max(this.start, o.start);
    return s < e ? new Interval(s, e) : null;
  }

  /** hợp, chỉ khi kết quả vẫn liền một khúc (chồng hoặc dính mép) */
  union(o: Interval): Interval | null {
    return this.intersect(o) ? new Interval(Math.min(this.start, o.start), Math.max(this.end, o.end)) : null;
  }
}

/** Gộp danh sách khoảng: sắp theo start rồi quét một lượt. */
export function mergeIntervals(list: Interval[]): Interval[] {
  const sorted = [...list].sort((a, b) => a.start - b.start);
  const out: Interval[] = [];
  for (const cur of sorted) {
    const last = out[out.length - 1];
    const merged = last?.union(cur);
    if (merged) out[out.length - 1] = merged;
    else out.push(cur);
  }
  return out;
}

const DAY = 86_400_000;

/** Cộng tháng, kẹp về ngày cuối tháng: 31/1 + 1 tháng = 28/2 (hoặc 29/2). */
export function addMonthsUTC(t: number, months: number): number {
  const d = new Date(t);
  const y = d.getUTCFullYear();
  const m = d.getUTCMonth() + months;
  const lastDay = new Date(Date.UTC(y, m + 1, 0)).getUTCDate();
  const day = Math.min(d.getUTCDate(), lastDay);
  return Date.UTC(y, m, day, d.getUTCHours(), d.getUTCMinutes(), d.getUTCSeconds(), d.getUTCMilliseconds());
}

/**
 * Số tháng TRỌN giữa start và end. Ước lượng bằng hiệu năm/tháng, rồi lùi tối đa 2 bước
 * cho tới khi start + n tháng không vượt end (cùng cách bản gốc làm).
 */
export function wholeMonths(iv: Interval): number {
  const a = new Date(iv.start);
  const b = new Date(iv.end);
  const guess = (b.getUTCFullYear() - a.getUTCFullYear()) * 12 + (b.getUTCMonth() - a.getUTCMonth());
  for (let n = guess; n > Math.max(0, guess - 2); n--) {
    if (addMonthsUTC(iv.start, n) <= iv.end) return n;
  }
  return Math.max(0, guess - 2);
}

export interface Period {
  years: number;
  months: number;
  days: number;
}

/**
 * "Bao lâu" theo lịch. Luôn cộng từ mốc start (không cộng dồn từng tháng một),
 * vì 31/1 +1 tháng +1 tháng = 28/3 còn 31/1 + 2 tháng = 31/3.
 */
export function toPeriod(iv: Interval): Period {
  const total = wholeMonths(iv);
  const anchor = addMonthsUTC(iv.start, total);
  return { years: Math.floor(total / 12), months: total % 12, days: Math.floor((iv.end - anchor) / DAY) };
}

/** Cách hay gặp mà sai: coi mọi tháng dài 30 ngày. */
export function naivePeriod(iv: Interval): Period {
  const days = Math.floor(iv.length / DAY);
  const months = Math.floor(days / 30);
  return { years: Math.floor(months / 12), months: months % 12, days: days - months * 30 };
}

Khác bản gốc:

• Bucket được bỏ khi thời điểm kết thúc (start + bucketMs) đã ra khỏi cửa sổ, kể cả bucket cuối. Im lặng đủ lâu thì tổng về 0.
• Tốc độ chia cho thời gian đã trôi qua (min(window, now - createdAt), tối thiểu một bucket), nên ba giây đầu cho số đúng.
• Đồng hồ là tham số now, test và demo tua thời gian được mà không cần fake timer.
• Interval dùng mili giây UTC thay vì giây + múi giờ. Đo theo múi giờ khác thì thay addMonthsUTC bằng phép cộng tháng có múi giờ.
• toPeriod đếm tổng số tháng một lần từ mốc đầu rồi tách năm/tháng, thay vì đệ quy từng đơn vị.

#Đi qua code

• add() gọi evict() trước rồi mới cộng. Nếu bucket cuối vẫn trong khoảng bucketMs thì cộng dồn, không thì đẩy bucket mới.
• evict() duyệt từ đầu mảng, gặp bucket còn hạn thì dừng, rồi splice một lần. Mảng tối đa windowMs / bucketMs phần tử nên chi phí nhỏ.
• tally(per) trả ratePer: số sự kiện trên mỗi per ms. Mặc định là "mỗi giây".
• addMonthsUTC kẹp ngày về cuối tháng: 31/1 + 1 tháng = 28/2 (29/2 năm nhuận). Đây là quy ước của hầu hết thư viện ngày tháng.
• wholeMonths lấy hiệu năm×12 + hiệu tháng làm dự đoán. Dự đoán chỉ có thể dư, không thiếu, vì ngày trong tháng của mốc cuối có thể nhỏ hơn mốc đầu. Vì vậy chỉ cần lùi.
• toPeriod lấy anchor = start + tổng số tháng, phần còn lại chia cho 86.400.000 để ra số ngày.

#Tại sao không làm cách khác?

• Lưu mọi timestamp rồi lọc: chính xác tuyệt đối nhưng bộ nhớ tăng theo số sự kiện. Một vòng lặp lỗi bắn 1.000 lần/giây sẽ giữ 60.000 số.
• EWMA (trung bình trượt hàm mũ, xem bài #58): chỉ cần một số, nhưng không trả lời được "đúng 30 giây qua có bao nhiêu lần", và chậm về 0 sau khi im lặng.
• Token bucket: hợp để cho phép/từ chối từng request, nhưng không cho số liệu để log. MovingStat đo trước, quyết định sau.
• Chia 30 ngày, 365 ngày: sai dần theo thời gian. Ở phần 2 của demo, 15/5/2000 → 28/10/2026 theo lịch là 26 năm 5 tháng 13 ngày, chia 30 ngày ra 26 năm 10 tháng 2 ngày.

#Edge case và cạm bẫy

• Cộng tháng không có tính kết hợp. 31/1 + 1 tháng + 1 tháng = 28/3, còn 31/1 + 2 tháng = 31/3. Luôn cộng từ mốc gốc, đừng cộng dồn từng tháng một trong vòng lặp.
• 29/2. 29/2/2024 → 28/2/2025 là tròn 1 năm theo cách kẹp cuối tháng. Có hệ thống (luật một số nước về tuổi) coi sinh nhật 29/2 năm không nhuận là 1/3. Chọn quy ước và ghi rõ.
• Giờ mùa hè. Đo "số ngày" bằng hiệu mili giây chia 86.400.000 sẽ lệch khi khoảng thời gian vắt qua lúc đổi giờ. Bản gốc làm tròn hiệu hai startOfDay rồi kiểm tra lại bằng addDays, đúng cách.
• Đồng hồ máy nhảy lùi. Date.now() có thể lùi khi người dùng chỉnh giờ hoặc NTP đồng bộ. Đo khoảng thời gian ngắn thì nên dùng performance.now(), nó luôn tăng.
• Khoảng nửa mở. contains(end) là false. Lịch 9:00–10:00 và sự kiện lúc 10:00 không trùng.

#Dùng trong dự án

Tự hãm vòng lặp kết nối lại WebSocket:

const reconnects = new MovingStat({ windowMs: 30_000 });
socket.addEventListener('close', () => {
  reconnects.add(1);
  const { ratePer } = reconnects.tally();
  const delay = ratePer >= 1 ? 30_000 : 1_000; // hơn 1 lần/giây thì nghỉ hẳn 30 giây
  setTimeout(connect, delay);
});

Hiển thị "Đã tham gia":

const p = toPeriod(Interval.of(Date.parse(user.joinedAt), Date.now()));
const label = p.years ? `${p.years} năm ${p.months} tháng` : p.months ? `${p.months} tháng` : `${p.days} ngày`;

#Kiểm thử

import { describe, expect, it } from 'vitest';
import { MovingStat } from '../src/lib/movingStat';
import { Interval, mergeIntervals, naivePeriod, toPeriod } from '../src/lib/timeInterval';

describe('MovingStat', () => {
  it('tốc độ lúc đầu chia cho thời gian đã trôi, im lặng thì về 0', () => {
    let t = 0;
    const s = new MovingStat({ now: () => t });
    for (let i = 0; i < 30; i++) {
      s.add(1);
      t += 100;
    }
    expect(s.tally()).toMatchObject({ sum: 30, ratePer: 10 });
    t += 61_000;
    expect(s.tally()).toMatchObject({ sum: 0, count: 0, buckets: 0 });
  });

  it('chỉ bỏ bucket đã hết hạn', () => {
    let t = 0;
    const s = new MovingStat({ windowMs: 10_000, now: () => t });
    s.add(5);
    t = 5_000;
    s.add(7);
    t = 11_500; // bucket đầu (0–1s) đã ra khỏi cửa sổ 1,5–11,5s
    expect(s.tally().sum).toBe(7);
  });
});

describe('Interval', () => {
  const d = (s: string) => Date.parse(s);
  it('dính mép thì không chồng nhưng vẫn gộp được', () => {
    const a = Interval.of(0, 10);
    const b = Interval.of(10, 20);
    expect(a.overlaps(b)).toBe(false);
    expect(a.abuts(b)).toBe(true);
    expect(a.union(b)).toEqual(Interval.of(0, 20));
    expect(a.gap(Interval.of(15, 20))).toEqual(Interval.of(10, 15));
  });

  it('mergeIntervals gộp theo thứ tự bất kỳ', () => {
    const r = mergeIntervals([Interval.of(5, 8), Interval.of(0, 2), Interval.of(2, 4), Interval.of(7, 9)]);
    expect(r).toEqual([Interval.of(0, 4), Interval.of(5, 9)]);
  });

  it('đếm tháng theo lịch', () => {
    expect(toPeriod(Interval.of(d('2026-01-31'), d('2026-03-01')))).toEqual({ years: 0, months: 1, days: 1 });
    expect(toPeriod(Interval.of(d('2024-02-29'), d('2025-02-28')))).toEqual({ years: 1, months: 0, days: 0 });
    expect(naivePeriod(Interval.of(d('2026-01-31'), d('2026-03-01')))).toEqual({ years: 0, months: 0, days: 29 });
  });

  it('start > end thì ném lỗi', () => {
    expect(() => Interval.of(2, 1)).toThrow(RangeError);
  });
});

#So với thư viện và chuẩn web

• Temporal: Temporal.PlainDate.prototype.until(other, { largestUnit: 'year' }) trả Duration theo lịch, cùng quy ước kẹp cuối tháng. Temporal đã có trên Firefox và Chrome, Safari vẫn đang triển khai (tính tới 10/2026), nên cần polyfill @js-temporal/polyfill nếu phải chạy mọi nơi.
• date-fns: differenceInMonths, intervalToDuration, areIntervalsOverlapping (có tuỳ chọn inclusive để coi dính mép là chồng). Luxon có Interval gần giống TimeInterval: abutsStart, overlaps, union, Interval.merge.
• Bộ đếm cửa sổ trượt ở phía server thường là Redis sorted set (chính xác) hoặc "sliding window counter" hai bucket (xấp xỉ). MovingStat là bản nhiều bucket nằm giữa hai cách đó.

Bài này thuộc series Học từ mã nguồn Facebook (106 bài, đọc theo thứ tự).

Code + demo: examples/facebook-patterns · Mở trên StackBlitz