Học từ Facebook #66: PRNG có seed, xáo trộn tái lập và lấy mẫu trace 1/32

Math.random() không nhận seed. Muốn cùng đầu vào thì ra cùng dãy ngẫu nhiên là bó tay:

• Xáo thứ tự câu hỏi cho mỗi thí sinh, tải lại trang vẫn giữ thứ tự cũ, không phải lưu thứ tự lên server.
• Chia người dùng vào nhóm A/B ổn định chỉ từ userId.
• Test hay demo có yếu tố ngẫu nhiên nhưng cần chạy lại y hệt khi gỡ lỗi.

Bundle Facebook mang theo Alea, một bộ sinh số giả ngẫu nhiên (PRNG) nhỏ của Johannes Baagøe (giấy phép MIT), cùng hai chỗ dùng nó: randomShuffleSeeded và ArtilleryTraceIDUtils (ID cho hệ thống trace hiệu năng Artillery).

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

#Mash và Alea

Module Alea (có trong bundle 1.js, 22.js) gần như nguyên văn bản gốc của Baagøe:

function Mash() {
  let n = 4022871197;                         // 0xefc8249d
  return function (data) {
    data = data.toString();
    for (let i = 0; i < data.length; i++) {
      n += data.charCodeAt(i);
      let h = 0.02519603282416938 * n;
      n = h >>> 0;                              // phần nguyên 32 bit
      h -= n;                                   // phần thập phân
      h *= n;
      n = h >>> 0;
      h -= n;
      n += h * 4294967296;                      // 2^32
    }
    return (n >>> 0) * 2.3283064365386963e-10;  // 2^-32 → [0, 1)
  };
}

function Alea(...args) {
  const seeds = args.length > 0 ? args : [new Date()];
  const mash = Mash();
  let s0 = mash(' '), s1 = mash(' '), s2 = mash(' '), c = 1;
  for (const seed of seeds) {
    s0 -= mash(seed); if (s0 < 0) s0 += 1;
    s1 -= mash(seed); if (s1 < 0) s1 += 1;
    s2 -= mash(seed); if (s2 < 0) s2 += 1;
  }
  return function random() {
    const t = 2091639 * s0 + c * 2.3283064365386963e-10;
    s0 = s1;
    s1 = s2;
    return (s2 = t - (c = t | 0));
  };
}

Mỗi lần gọi random(): nhân trạng thái cũ nhất với hằng số 2091639, cộng số nhớ c (đã chia cho 2³²), phần nguyên của kết quả thành số nhớ mới, phần thập phân là số trả về và trở thành trạng thái mới nhất. Ba trạng thái xoay vòng (s0 ← s1 ← s2 ← mới). Đây là phép multiply-with-carry "lag-3", viết bằng số thực để chạy nhanh trên JavaScript mà không cần số nguyên 64 bit. Chu kỳ khoảng 2¹¹⁶ theo tác giả, quá đủ cho UI.

Mash cũng đáng chú ý: nó băm mọi seed (số, chuỗi, Date) qua toString() thành số thực trong [0, 1), và giữ trạng thái n giữa các lần gọi. Vì thế nhiều seed (Alea('quiz-10', 'user-42')) được trộn theo thứ tự: Alea('a', 'b') khác Alea('b', 'a').

Hệ quả của toString(): seed mặc định new Date() thành "Wed Oct 28 2026 09:47:13 GMT+0000 (…)", không có mili-giây. Hai bộ sinh không truyền seed tạo trong cùng một giây (hai tab mở cùng lúc, hai component khởi tạo cùng lượt render) cho cùng một dãy số. Demo có thử điều này với hai thời điểm cách nhau 900ms.

#randomShuffleSeeded

function randomShuffleSeeded(array, ...seeds) {
  const random = Alea(...seeds);
  const randomInt = (max) => Math.floor(random() * max);
  for (let h = array.length - 1; h > 0; h--) {
    const i = randomInt(h + 1);             // 0 ≤ i ≤ h
    if (i != h) [array[i], array[h]] = [array[h], array[i]];
  }
  return array;                             // chính mảng đầu vào
}

Đây là Fisher-Yates chuẩn: đi từ cuối về đầu, đổi phần tử h với một phần tử ngẫu nhiên trong [0, h]. Mọi hoán vị có xác suất bằng nhau (nếu PRNG đều). Cạm bẫy: hàm sửa mảng đầu vào. Gọi hai lần với cùng seed trên cùng một mảng không ra cùng thứ tự, vì lần hai xáo một mảng đã bị xáo. Ai lấy mảng từ state React hay từ cache dùng chung mà quên .slice() sẽ gặp lỗi khó hiểu: "cùng seed mà sao thứ tự đổi?".

#ArtilleryTraceIDUtils: ID 63 bit và lấy mẫu bằng ký tự cuối

const BASE64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
const random = Alea(ServerNonce.ServerNonce);    // seed là nonce server gửi kèm trang

function once() {
  let bits = 0, pool = 0, id = '';
  for (let i = 10; i >= 0; i--) {
    if (bits < 6) { pool = Math.floor(2147483648 * random()); bits = 32; } // 2^31
    if (i === 0) pool &= 7;                       // ký tự đầu chỉ 3 bit
    id = BASE64.charAt(pool & 63) + id;
    pool >>= 6;
    bits -= 6;
  }
  return id;
}

newTraceId() {
  for (let n = 3; n > 0; n--) {
    const id = once();
    if (id != 'AAAAAAAAAAA') return id;           // ID toàn 0 dành cho "không có trace"
  }
  FBLogger('FIXME').mustfix('failed to generate valid Fbtrace id');
  return 'AAAAAAAAAAA';
}

traceIdToBucket(id) {
  return BASE64.indexOf(id.charAt(id.length - 1)) % 32;
}

• 63 bit: 10 ký tự × 6 bit + 3 bit = 63. ID đổi ngược ra số vừa kiểu BIGINT có dấu của MySQL/Java mà không bao giờ âm.
• Seed là ServerNonce (một chuỗi ngẫu nhiên server nhúng vào trang), không phải thời gian, nên hai tab có ID khác nhau.
• Lấy mẫu theo ký tự cuối: ký tự cuối mang 6 bit ngẫu nhiên, % 32 cho nhóm 0–31 đều nhau. Hệ thống chỉ cần quy định "giữ trace có nhóm < N" để lấy mẫu N/32. Vì quyết định nằm trong ID, mọi tầng (client, proxy, backend) nhìn cùng một ID đều đồng ý trace này được giữ hay bỏ, không cần truyền thêm cờ.
• Một chi tiết nhỏ: bộ đếm bits = 32 trong khi Math.floor(2^31 * random()) chỉ có 31 bit. Không ảnh hưởng kết quả: sau 5 ký tự (30 bit) bộ đếm còn 2, dưới 6 nên vẫn lấy số mới.

#Viết lại

Bản viết lại giữ nguyên Mash/Alea (thuật toán công khai, cần đúng hằng số để tái lập dãy), đổi phần xung quanh: xáo trên bản sao, seed mặc định bằng crypto.getRandomValues, thêm bucketOf cho A/B.

/** Hàm băm Mash: biến chuỗi thành số trong [0, 1). Giữ trạng thái giữa các lần gọi. */
function createMash() {
  let n = 0xefc8249d; // 4022871197
  return (data: string) => {
    for (let i = 0; i < data.length; i++) {
      n += data.charCodeAt(i);
      let h = 0.02519603282416938 * n;
      n = h >>> 0;
      h -= n;
      h *= n;
      n = h >>> 0;
      h -= n;
      n += h * 0x100000000; // 2^32
    }
    return (n >>> 0) * 2.3283064365386963e-10; // 2^-32
  };
}

export type Random = () => number;

/** Tạo PRNG Alea từ một hoặc nhiều seed. Cùng seed → cùng dãy số. */
export function alea(...seeds: Array<string | number>): Random {
  const mash = createMash();
  let s0 = mash(' ');
  let s1 = mash(' ');
  let s2 = mash(' ');
  let carry = 1;
  for (const seed of seeds) {
    const text = String(seed);
    s0 -= mash(text);
    if (s0 < 0) s0 += 1;
    s1 -= mash(text);
    if (s1 < 0) s1 += 1;
    s2 -= mash(text);
    if (s2 < 0) s2 += 1;
  }
  return () => {
    const t = 2091639 * s0 + carry * 2.3283064365386963e-10;
    s0 = s1;
    s1 = s2;
    return (s2 = t - (carry = t | 0));
  };
}

/** Seed khó trùng khi không truyền seed: bản gốc dùng new Date() (Mash đổi ra chuỗi, chỉ tới giây), hai tab mở trong cùng một giây sẽ trùng dãy. */
export function randomSeed() {
  const buf = new Uint32Array(2);
  crypto.getRandomValues(buf);
  return `${buf[0].toString(36)}${buf[1].toString(36)}`;
}

export function randomInt(random: Random, maxExclusive: number) {
  return Math.floor(random() * maxExclusive);
}

/** Fisher-Yates trên bản sao (bản gốc xáo trộn tại chỗ, dễ làm hỏng mảng của người gọi). */
export function shuffleSeeded<T>(items: readonly T[], ...seeds: Array<string | number>) {
  const random = alea(...seeds);
  const out = items.slice();
  for (let i = out.length - 1; i > 0; i--) {
    const j = randomInt(random, i + 1);
    [out[i], out[j]] = [out[j], out[i]];
  }
  return out;
}

/** Chia người dùng vào nhóm A/B ổn định: cùng (experiment, userId) luôn ra cùng nhóm. */
export function bucketOf(experiment: string, userId: string, buckets: number) {
  return randomInt(alea(experiment, userId), buckets);
}

ID trace và nhóm lấy mẫu:

const BASE64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
const DUMMY_TRACE_ID = 'AAAAAAAAAAA';

/**
 * ID trace 11 ký tự base64 = 63 bit: ký tự đầu chỉ 3 bit (0..7) để cả số vừa int64 có dấu.
 * Mỗi lần lấy 31 bit từ PRNG, cắt 6 bit một.
 */
export function createTraceIdGenerator(random: Random) {
  function once() {
    let bits = 0;
    let pool = 0;
    let id = '';
    for (let i = 10; i >= 0; i--) {
      if (bits < 6) {
        pool = Math.floor(0x80000000 * random());
        bits = 31;
      }
      if (i === 0) pool &= 7;
      id = BASE64.charAt(pool & 63) + id;
      pool >>= 6;
      bits -= 6;
    }
    return id;
  }
  return () => {
    // giống bản gốc: thử lại vài lần nếu ra đúng ID "rỗng" dùng làm giá trị giả
    for (let attempt = 0; attempt < 3; attempt++) {
      const id = once();
      if (id !== DUMMY_TRACE_ID) return id;
    }
    return DUMMY_TRACE_ID;
  };
}

/** Nhóm 0..31 suy từ ký tự cuối của ID: lấy mẫu 1/32 mà không cần thêm số ngẫu nhiên. */
export function traceIdToBucket(traceId: string) {
  return BASE64.indexOf(traceId.charAt(traceId.length - 1)) % 32;
}

/**
 * Số ngẫu nhiên tái lập được theo seed (ý tưởng từ Alea, randomShuffleSeeded và
 * ArtilleryTraceIDUtils trong bundle Facebook).
 *
 * Alea là thuật toán công khai của Johannes Baagøe (giấy phép MIT); Facebook dùng nguyên
 * hằng số của tác giả. KHÔNG dùng cho mật khẩu, token, ID bí mật: dùng crypto.getRandomValues.
 */

/** Hàm băm Mash: biến chuỗi thành số trong [0, 1). Giữ trạng thái giữa các lần gọi. */
function createMash() {
  let n = 0xefc8249d; // 4022871197
  return (data: string) => {
    for (let i = 0; i < data.length; i++) {
      n += data.charCodeAt(i);
      let h = 0.02519603282416938 * n;
      n = h >>> 0;
      h -= n;
      h *= n;
      n = h >>> 0;
      h -= n;
      n += h * 0x100000000; // 2^32
    }
    return (n >>> 0) * 2.3283064365386963e-10; // 2^-32
  };
}

export type Random = () => number;

/** Tạo PRNG Alea từ một hoặc nhiều seed. Cùng seed → cùng dãy số. */
export function alea(...seeds: Array<string | number>): Random {
  const mash = createMash();
  let s0 = mash(' ');
  let s1 = mash(' ');
  let s2 = mash(' ');
  let carry = 1;
  for (const seed of seeds) {
    const text = String(seed);
    s0 -= mash(text);
    if (s0 < 0) s0 += 1;
    s1 -= mash(text);
    if (s1 < 0) s1 += 1;
    s2 -= mash(text);
    if (s2 < 0) s2 += 1;
  }
  return () => {
    const t = 2091639 * s0 + carry * 2.3283064365386963e-10;
    s0 = s1;
    s1 = s2;
    return (s2 = t - (carry = t | 0));
  };
}

/** Seed khó trùng khi không truyền seed: bản gốc dùng new Date() (Mash đổi ra chuỗi, chỉ tới giây), hai tab mở trong cùng một giây sẽ trùng dãy. */
export function randomSeed() {
  const buf = new Uint32Array(2);
  crypto.getRandomValues(buf);
  return `${buf[0].toString(36)}${buf[1].toString(36)}`;
}

export function randomInt(random: Random, maxExclusive: number) {
  return Math.floor(random() * maxExclusive);
}

/** Fisher-Yates trên bản sao (bản gốc xáo trộn tại chỗ, dễ làm hỏng mảng của người gọi). */
export function shuffleSeeded<T>(items: readonly T[], ...seeds: Array<string | number>) {
  const random = alea(...seeds);
  const out = items.slice();
  for (let i = out.length - 1; i > 0; i--) {
    const j = randomInt(random, i + 1);
    [out[i], out[j]] = [out[j], out[i]];
  }
  return out;
}

/** Chia người dùng vào nhóm A/B ổn định: cùng (experiment, userId) luôn ra cùng nhóm. */
export function bucketOf(experiment: string, userId: string, buckets: number) {
  return randomInt(alea(experiment, userId), buckets);
}

const BASE64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
const DUMMY_TRACE_ID = 'AAAAAAAAAAA';

/**
 * ID trace 11 ký tự base64 = 63 bit: ký tự đầu chỉ 3 bit (0..7) để cả số vừa int64 có dấu.
 * Mỗi lần lấy 31 bit từ PRNG, cắt 6 bit một.
 */
export function createTraceIdGenerator(random: Random) {
  function once() {
    let bits = 0;
    let pool = 0;
    let id = '';
    for (let i = 10; i >= 0; i--) {
      if (bits < 6) {
        pool = Math.floor(0x80000000 * random());
        bits = 31;
      }
      if (i === 0) pool &= 7;
      id = BASE64.charAt(pool & 63) + id;
      pool >>= 6;
      bits -= 6;
    }
    return id;
  }
  return () => {
    // giống bản gốc: thử lại vài lần nếu ra đúng ID "rỗng" dùng làm giá trị giả
    for (let attempt = 0; attempt < 3; attempt++) {
      const id = once();
      if (id !== DUMMY_TRACE_ID) return id;
    }
    return DUMMY_TRACE_ID;
  };
}

/** Nhóm 0..31 suy từ ký tự cuối của ID: lấy mẫu 1/32 mà không cần thêm số ngẫu nhiên. */
export function traceIdToBucket(traceId: string) {
  return BASE64.indexOf(traceId.charAt(traceId.length - 1)) % 32;
}

#Đi qua code

• createMash viết lại bằng hằng số hex (0xefc8249d = 4022871197) cho dễ tra. Mọi phép >>> 0 lấy 32 bit thấp của phần nguyên; phép nhân với 0.0251… rồi tách nguyên/thập phân hai lần là cách Baagøe trộn bit chỉ bằng số thực.
• alea(...seeds) bắt buộc truyền seed (không có mặc định ngầm). Muốn ngẫu nhiên thật thì gọi alea(randomSeed()), để việc "không tái lập" là quyết định có chủ ý.
• randomSeed lấy 64 bit từ crypto.getRandomValues, đổi ra chuỗi base36. Có thể in seed ra log: khi người dùng báo lỗi, chạy lại đúng seed đó.
• shuffleSeeded nhận readonly T[], copy bằng slice() rồi Fisher-Yates trên bản sao. TypeScript chặn luôn việc truyền mảng rồi trông đợi nó bị sửa.
• bucketOf(experiment, userId, n) = số đầu tiên của alea(experiment, userId) nhân n. Thêm tên thí nghiệm vào seed để mỗi thí nghiệm chia người dùng độc lập nhau: người ở nhóm 0 của thí nghiệm này không mặc nhiên ở nhóm 0 của thí nghiệm khác. Demo chia 20.000 người vào 4 nhóm ra khoảng 5.000 mỗi nhóm.
• createTraceIdGenerator(random) nhận PRNG từ ngoài (dễ test với seed cố định), đặt bits = 31 cho đúng số bit thật.

Khác bản gốc:

• Xáo trên bản sao, không sửa mảng đầu vào.
• Không còn seed mặc định new Date() (độ phân giải giây).
• Bỏ phần ghi log khi sinh ID thất bại 3 lần (xác suất 2^-63 mỗi lần, thực tế không xảy ra).

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

Băm userId (FNV, murmur) rồi mod số nhóm? Với A/B chỉ cần một số ngẫu nhiên, hàm băm là đủ và nhanh hơn. PRNG có seed hơn ở chỗ sinh được cả dãy (xáo trộn, chọn nhiều phần tử, mô phỏng).

crypto.getRandomValues cho mọi thứ? Không có seed nên không tái lập được. Dùng nó cho thứ cần không đoán được (token, ID phiên, mật khẩu, nonce bảo mật); dùng PRNG có seed cho thứ cần tái lập được. Alea không an toàn mật mã: biết vài số đầu ra có thể suy ngược trạng thái.

Mulberry32, xoshiro128**, sfc32? Đều là PRNG nhỏ tốt, có seed, chất lượng thống kê tốt hơn hoặc ngang Alea, và nhận seed 32/128 bit thay vì chuỗi. Alea tiện ở chỗ seed là chuỗi bất kỳ nhờ Mash. Chọn cái nào cũng được, miễn cố định một thuật toán: đổi thuật toán là đổi mọi thứ tự đã lưu ngầm theo seed.

Lấy mẫu bằng Math.random() < 1/32 ở mỗi tầng? Mỗi tầng quyết định riêng: client giữ trace, backend bỏ, ra trace thiếu mảnh. Quyết định dựa trên ID thì nhất quán; OpenTelemetry làm đúng như vậy với TraceIdRatioBased sampler.

#Edge case và cạm bẫy

• Math.floor(random() * n) lệch nhẹ khi n không chia hết số giá trị có thể của random(). Với n nhỏ (vài nghìn) độ lệch không đáng kể (~n/2³²); với n cỡ tỉ thì dùng phép từ chối (rejection sampling).
• Đổi danh sách thì thứ tự đổi hết. Seed cố định nhưng thêm một câu hỏi vào đề là toàn bộ thứ tự xáo khác đi. Muốn ổn định từng phần tử, xếp theo hash(seed + item.id) thay vì Fisher-Yates.
• Seed từ dữ liệu người dùng (userId) thì ai biết userId cũng tính được nhóm hoặc thứ tự. Không sao với A/B; không được dùng cho thứ cần bí mật (thứ tự đáp án trong bài thi có thưởng).
• Số thực khác nhau giữa engine? Alea chỉ dùng phép nhân, cộng, trừ, >>> 0, | 0 trên số double theo IEEE 754, nên mọi trình duyệt và Node cho cùng một dãy. Đừng "tối ưu" bằng Math.fround hay đổi thứ tự phép tính.
• Bộ sinh dùng chung giữa các tính năng. Hai tính năng cùng gọi một random() thì thứ tự gọi quyết định kết quả; thêm một lời gọi ở tính năng A làm đổi kết quả của B. Mỗi việc một bộ sinh, seed riêng.

#Dùng trong dự án

import { alea, bucketOf, randomSeed, shuffleSeeded } from './seededRandom';

// Đề thi: mỗi thí sinh một thứ tự, ổn định khi tải lại
const ordered = shuffleSeeded(questions, exam.id, user.id);

// A/B: 10% người dùng thấy giao diện mới
const inTreatment = bucketOf('new-checkout-2026', user.id, 100) < 10;

// Test/demo tái lập: in seed ra để chạy lại
const seed = new URLSearchParams(location.search).get('seed') ?? randomSeed();
console.info('seed =', seed);
const random = alea(seed);

#Kiểm thử

import { describe, expect, it } from 'vitest';
import { alea, createTraceIdGenerator, shuffleSeeded, traceIdToBucket } from './seededRandom';

describe('alea', () => {
  it('cùng seed cùng dãy, thứ tự seed có ý nghĩa', () => {
    const a = alea('x', 'y'), b = alea('x', 'y'), c = alea('y', 'x');
    const first = a();
    expect(b()).toBe(first);
    expect(c()).not.toBe(first);
  });
  it('shuffle không sửa mảng gốc và ổn định theo seed', () => {
    const input = [1, 2, 3, 4, 5, 6];
    const once = shuffleSeeded(input, 'quiz', 'u1');
    expect(input).toEqual([1, 2, 3, 4, 5, 6]);
    expect(shuffleSeeded(input, 'quiz', 'u1')).toEqual(once);
    expect([...once].sort()).toEqual(input);
  });
  it('ID trace 11 ký tự, ký tự đầu A–H, nhóm lấy mẫu ~1/32', () => {
    const next = createTraceIdGenerator(alea('trace'));
    let zero = 0;
    for (let i = 0; i < 64_000; i++) {
      const id = next();
      expect(id).toMatch(/^[A-H][A-Za-z0-9+/]{10}$/);
      if (traceIdToBucket(id) === 0) zero++;
    }
    expect(zero / 64_000).toBeCloseTo(1 / 32, 2);
  });
});

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

• seedrandom (npm) có chính Alea cùng nhiều PRNG khác (xor4096, tychei), API seedrandom('hello'). Nếu không muốn tự giữ code, dùng nó.
• pure-rand (dùng trong fast-check) có xoroshiro128+, mersenne twister, API bất biến hợp cho property-based testing.
• Faker, fast-check, Playwright đều có tham số seed để test tái lập; nguyên tắc giống bài này: in seed khi test hỏng.
• Lấy mẫu trace: OpenTelemetry TraceIdRatioBasedSampler quyết định từ các bit của trace ID, W3C Trace Context mang cờ sampled để các dịch vụ sau tôn trọng.
• TC39 có đề xuất "Seeded Pseudo-Random Numbers" (Random.Seeded), có thể đưa PRNG có seed vào JavaScript chuẩn; tính tới 10/2026 vẫn chưa dùng được trong trình duyệt.

Bài liên quan: Học từ Facebook #26: ring buffer biết trace nào đã mất log, Học từ Facebook #63: cây tổng và rút thăm theo trọng số.

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