Học từ Facebook #26: Ring buffer biết trace nào đã mất log

Khi đo hiệu năng phía client, ta thường mở một trace cho mỗi tương tác: người dùng bấm "mở chat" thì bắt đầu ghi, chat hiện xong thì dừng và gửi lên server mọi sự kiện xảy ra trong khoảng đó (task nào chạy, chạy bao lâu, ai gọi ai).

Ba vấn đề xuất hiện ngay:

1. Sự kiện đổ về rất nhiều (mỗi lần một hàm được bọc profiler chạy). Không thể giữ mãi trong bộ nhớ.
2. Các trace chồng lên nhau: đang đo "mở chat" thì người dùng gõ tìm kiếm, sinh thêm trace "gõ tìm kiếm".
3. Nếu giới hạn bộ nhớ thì một trace dài sẽ bị mất các sự kiện đầu. Gửi lên một trace thiếu dữ liệu mà không biết là thiếu thì số liệu phân tích sai.

Facebook giải cả ba bằng một cấu trúc dữ liệu khoảng 100 dòng.

▶ 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?

Ba module trong thư mục TimeSliceSham/ của facebook-codebase (bản đầy đủ nằm trong các bundle 1.js, 22.js):

• CircularBuffer: ring buffer cơ bản có onEvict.
• IntervalTrackingBoundedBuffer: các "cửa sổ ghi" trên buffer đó.
• TimeSliceSham: tạo một buffer duy nhất cho cả trang, kích thước lấy từ Env.timesliceBufferSize, mặc định 5000.

Nơi dùng là TimeSliceInteraction (bundle 237.js), lớp đại diện cho một interaction trace:

// khi trace bắt đầu (được chọn mẫu)
this.$15 = b("TimeSlice").getBuffer().open();
// khi trace kết thúc
var i = this.$15 != null ? this.$15.close() : [],
    j = this.$15 != null ? this.$15.hasOverflown() : false,
    k = this.$15 != null ? this.$15.getOverflowSize() : 0;
// ... sau đó, lúc trình duyệt rảnh (requestIdleCallbackAcrossTransitions):
this.$10.addStringAnnotation("overflown_timeslice_buffer", f ? "1" : "0");
this.$10.addStringAnnotation("overflown_timeslice_entry_count", "" + h);

Vậy là mọi trace gửi lên đều kèm hai cờ cho biết dữ liệu có đầy đủ hay không.

#CircularBuffer

c.write = function (a) {
  this.$3.length < this.$1
    ? this.$3.push(a)                                  // chưa đầy: thêm vào cuối
    : (this.$4.forEach(fn => fn(this.$3[this.$2])),    // đầy: báo onEvict phần tử cũ nhất
       this.$3[this.$2] = a, this.$2++, this.$2 %= this.$1); // đè lên, con trỏ chạy vòng
};
c.read = function () {                                 // thứ tự từ cũ đến mới
  return this.$3.slice(this.$2).concat(this.$3.slice(0, this.$2));
};

Không có gì lạ, trừ onEvict: buffer báo ra ngoài mỗi lần đè một phần tử.

#IntervalTrackingBoundedBuffer

Đây là phần hay. Đổi tên biến cho dễ đọc:

constructor(size = 5000) {
  this.dropped = 0;                         // $6: số phần tử đã rời buffer
  this.buffer = new CircularBuffer(size);
  this.buffer.onEvict(() => this.dropped++);
  this.intervals = [];                      // $2: các cửa sổ đang mở
  this.pushed = 0;                          // $5: tổng số phần tử đã đẩy vào
}
open() {
  const startIdx = this.pushed;             // số thứ tự TUYỆT ĐỐI lúc mở
  return {
    getOverflowSize: () => Math.max(this.dropped - startIdx, 0),
    close: () => /* trả về các phần tử từ startIdx, rồi dọn */,
  };
}
pushElement(el) {
  if (this.intervals.length > 0) { this.buffer.write(el); this.pushed++; }  // không ai nghe thì bỏ
}

Hai con số pushed và dropped mang ý nghĩa rất gọn:

• Phần tử thứ k (đánh số từ 0 theo thứ tự đẩy vào) đang nằm ở vị trí k - dropped trong buffer.
• Buffer luôn chứa đúng các phần tử có số thứ tự trong khoảng [dropped, pushed).
• Một cửa sổ mở lúc pushed = s đã mất max(dropped - s, 0) phần tử đầu của nó.

Khi một cửa sổ đóng, ngoài việc trả về dữ liệu, nó còn dọn rác: tìm startIdx nhỏ nhất của các cửa sổ còn mở; mọi phần tử đứng trước số đó không còn ai cần nên dropFirst luôn, đồng thời cộng vào dropped. Không còn cửa sổ nào thì buffer rỗng.

sequenceDiagram
  participant A as Trace A
  participant Buf as Buffer 30 chỗ
  participant B as Trace B
  A->>Buf: open, startIdx = 0
  Note over Buf: đẩy 16 sự kiện
  B->>Buf: open, startIdx = 16
  Note over Buf: đẩy thêm 20, tổng 36, đè 6 phần tử cũ, dropped = 6
  B->>Buf: close: mất max(6 - 16, 0) = 0
  Note over Buf: đẩy thêm 24, tổng 60, dropped = 30
  A->>Buf: close: mất max(30 - 0, 0) = 30, gắn cờ overflown

Mình đã đọc kỹ phần dọn rác: công thức trong bản gốc là pos(d) - pos(c) với c là startIdx nhỏ nhất của mọi cửa sổ (kể cả cửa sổ đang đóng) và d là nhỏ nhất của các cửa sổ còn lại. Khi cửa sổ đang đóng không phải cửa sổ mở sớm nhất thì c = d và không dọn gì; đúng như mong đợi. Mình không tìm thấy lỗi trong module này.

#Bên trong trình duyệt: vì sao phải giới hạn?

Mỗi sự kiện TimeSlice là một object nhỏ (tên guard, thời điểm bắt đầu, kết thúc…). Một tab Facebook mở cả ngày có thể sinh hàng triệu sự kiện. Nếu mỗi trace tự giữ mảng riêng:

• Trace chồng nhau thì cùng một sự kiện bị giữ ở nhiều mảng (demo đếm con số này ở ô "Mỗi trace một mảng").
• Một trace quên đóng (lỗi logic, người dùng rời trang giữa chừng) sẽ giữ mảng phình mãi, chiếm bộ nhớ mà GC không thu hồi được.

Ring buffer chặn trên bộ nhớ ở một con số cố định, đổi lại là có thể mất dữ liệu. Phần còn lại của thiết kế chỉ để biết khi nào mất.

#Viết lại

CircularBuffer gần như giữ nguyên bản gốc, chỉ đặt tên rõ hơn (xem file đầy đủ ở cuối mục). IntervalTrackingBuffer dùng pushed/dropped như bản gốc; phần dọn rác viết thẳng bằng "startIndex nhỏ nhất của các cửa sổ còn mở":

  open(): RecordingWindow<T> {
    const id = this.nextId++;
    const startIndex = this.pushed;
    let closed = false;
    let finalOverflow: number | null = null;
    const window: RecordingWindow<T> = {
      id,
      startIndex,
      getOverflowSize: () => finalOverflow ?? Math.max(this.dropped - startIndex, 0),
      hasOverflown: () => window.getOverflowSize() > 0,
      close: () => {
        if (closed) return [];
        closed = true;
        finalOverflow = Math.max(this.dropped - startIndex, 0);
        return this.closeWindow(id);
      },
    };
    this.windows.push(window);
    return window;
  }

  /** chỉ số tuyệt đối -> vị trí trong buffer hiện tại */
  private position(absoluteIndex: number) {
    return Math.max(absoluteIndex - this.dropped, 0);
  }

  private closeWindow(id: number): T[] {
    const index = this.windows.findIndex((w) => w.id === id);
    if (index === -1) return [];
    const [closing] = this.windows.splice(index, 1);
    const entries = this.buffer.read().slice(this.position(closing.startIndex));

    // Dọn: phần tử nằm trước cửa sổ còn mở sớm nhất thì không ai cần nữa.
    // Không còn cửa sổ nào -> dọn sạch.
    const oldestStillNeeded = this.windows.length
      ? Math.min(...this.windows.map((w) => w.startIndex))
      : this.pushed;
    const removable = this.position(oldestStillNeeded);
    if (removable > 0) {
      this.buffer.dropFirst(removable);
      this.dropped += removable;
    }
    return entries;
  }
}

Khác bản gốc: dropFirst trong bản viết lại không gọi onEvict (bản gốc cũng vậy, nhưng cộng dropped bằng tay ở hàm đóng). getOverflowSize sau khi đóng trả về con số chốt lúc đóng, giống bản gốc. Bỏ phần báo lỗi "messed up state" qua ErrorPubSub, thay bằng trả [] khi không tìm thấy cửa sổ.

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

Mỗi trace một mảng, giới hạn mỗi mảng 5000? Bộ nhớ tăng theo số trace đang mở, và cùng một sự kiện bị nhân bản. Buffer chung thì bộ nhớ là hằng số.

Mỗi phần tử ghi kèm số thứ tự, khi đóng thì lọc theo số thứ tự? Được, nhưng tốn thêm một trường cho mỗi phần tử và một lần duyệt lọc. Bản gốc chỉ cần hai biến đếm cho cả buffer.

Không cần biết mất bao nhiêu, chỉ cần biết có mất hay không? Con số overflown_timeslice_entry_count giúp phân biệt trace thiếu vài phần tử (vẫn dùng được) với trace mất gần hết. Có lẽ đó là lý do Facebook gửi cả hai.

#Edge case và cạm bẫy

• Không có cửa sổ nào mở thì không ghi. Sự kiện xảy ra trước khi trace mở sẽ không bao giờ có. Nếu muốn có cả vài giây trước tương tác (ví dụ để xem vì sao click bị trễ) thì phải mở sẵn một cửa sổ "nền" luôn mở và tự cắt.
• Kích thước buffer. 5000 là mặc định; Facebook cho server đổi qua Env.timesliceBufferSize. Trace càng dài càng dễ mất đầu. Nhìn tỉ lệ trace bị overflown trên dashboard để chỉnh.
• read() sao chép cả buffer. Mỗi lần đóng là một lần tạo mảng 5000 phần tử. Với vài trace mỗi giây thì không sao; nếu đóng/mở liên tục hàng trăm lần mỗi giây thì nên cắt theo vị trí thay vì read() toàn bộ.
• Đóng hai lần. Lần hai trả []; đừng dựa vào giá trị trả về lần hai.

#Dùng trong dự án

Đặt buffer ở một module dùng chung, mọi nơi muốn log thì push, mọi interaction thì open/close:

export const perfBuffer = new IntervalTrackingBuffer<PerfEvent>(5000);

function startInteraction(name: string) {
  const window = perfBuffer.open();
  return () => {
    const events = window.close();
    sendTrace({ name, events, overflown: window.hasOverflown(), lost: window.getOverflowSize() });
  };
}

Có thể ghép với bộ gom log ở Học từ Facebook #7: Banzai để gửi lên theo lô, và với performance span ở bài #11 series web.

#Kiểm thử

import { describe, expect, it } from 'vitest';
import { CircularBuffer, IntervalTrackingBuffer } from './traceRingBuffer';

describe('CircularBuffer', () => {
  it('đè phần tử cũ nhất và báo onEvict', () => {
    const evicted: number[] = [];
    const buf = new CircularBuffer<number>(3).onEvict((x) => evicted.push(x));
    [1, 2, 3, 4, 5].forEach((x) => buf.write(x));
    expect(buf.read()).toEqual([3, 4, 5]);
    expect(evicted).toEqual([1, 2]);
  });
});

describe('IntervalTrackingBuffer', () => {
  it('trace ngắn đủ dữ liệu, trace dài biết mình mất bao nhiêu', () => {
    const b = new IntervalTrackingBuffer<number>(30);
    const a = b.open();
    for (let i = 0; i < 16; i++) b.push(i);
    const short = b.open();
    for (let i = 16; i < 36; i++) b.push(i);
    expect(short.close()).toHaveLength(20);
    expect(short.getOverflowSize()).toBe(0);
    for (let i = 36; i < 60; i++) b.push(i);
    const entries = a.close();
    expect(entries[0]).toBe(30);
    expect(a.getOverflowSize()).toBe(30);
    expect(b.stats.size).toBe(0); // không còn trace nào: dọn sạch
  });

  it('không có trace nào mở thì không ghi', () => {
    const b = new IntervalTrackingBuffer<number>(10);
    expect(b.push(1)).toBe(false);
    expect(b.stats.pushed).toBe(0);
  });
});

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

• Performance Timeline của trình duyệt (PerformanceObserver, performance.getEntries) cũng dùng buffer có giới hạn: ví dụ performance.setResourceTimingBufferSize() và sự kiện resourcetimingbufferfull báo khi đầy. Ý tưởng giống nhau: giới hạn bộ nhớ và báo cho người dùng biết đã tràn.
• OpenTelemetry JS có BatchSpanProcessor với maxQueueSize; khi đầy thì bỏ span mới và đếm số span bị bỏ. Nó giải bài toán "gửi lên", còn buffer của Facebook giải bài toán "nhiều trace đọc chung một nguồn sự kiện".

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