How to shuffle a big dataset

Jane Street · 2018 · 3. Quy mô lớn · Độ khó: Trung bình — bài gốc

Bài thuật toán của một researcher, không kể hệ thống thay đổi. Wiki giữ vì nó cho thấy hình dạng dữ liệu huấn luyện của một công ty quant và cách tổ chức pipeline quanh nó.

Bối cảnh

• Theo bài, dữ liệu ở Jane Street có tỉ lệ tín hiệu/nhiễu rất thấp nhưng rất nhiều: kiểu một tỉ mẫu huấn luyện mà nhãn chỉ hơi có xu hướng đúng.
• Huấn luyện bằng SGD cần xáo trộn dữ liệu; dữ liệu không vừa RAM thì Fisher–Yates không dùng được, còn đọc ngẫu nhiên từ đĩa thì quá chậm.

Thay đổi chính

• Xáo trộn hai lượt: lượt 1 đọc tuần tự, ghi mỗi mẫu vào một trong M "đống" (file) chọn ngẫu nhiên; lượt 2 xáo từng đống trong RAM rồi nối lại. Tương đương sắp theo một số ngẫu nhiên (radix theo đống, phần còn lại trong đống), nên không lệch.
• Đống quá cỡ: chọn kích thước có dư (kỳ vọng + 6 độ lệch chuẩn), hiếm khi vượt thì làm lại từ đầu; làm lại không gây lệch vì kích thước các đống độc lập với hoán vị.
• Thực tế: lượt 1 chạy song song trên nhiều file đầu vào và gộp vào bước tiền xử lý (ghi ra nhiều đống thay vì một file), nên gần như miễn phí; lượt 2 làm lười lúc nạp đống để train, có thể vừa train đống này vừa nạp đống sau.
• Giữ đống chưa xáo cho phép duy trì một cửa sổ trượt Y năm: mỗi đống là ring buffer theo thời gian, dữ liệu mới vào thì bỏ dữ liệu cũ.
• Số đo (2018): 220 triệu mẫu × 9 kB, 2 TB chưa nén, 320 GB nén HDF5 (4 file × 80 GB). Đọc ngẫu nhiên 394.000 µs/mẫu, tức khoảng 2,75 năm cho một lượt; đọc tuần tự theo khối 120 µs/mẫu, 7,3 giờ một lượt; cả quy trình hai lượt khoảng một ngày, nhanh khoảng 1.000 lần. Kể cả SSD cục bộ không nén, tuần tự vẫn nhanh 48 lần.

Vì sao

• Chi phí bị chi phối bởi kiểu truy cập (tuần tự hay ngẫu nhiên) chứ không bởi số lượt đọc/ghi; thêm một lượt ghi tuần tự rẻ hơn rất nhiều so với đọc ngẫu nhiên.

Bài học cho SWE

• Với dữ liệu lớn hơn RAM, đổi truy cập ngẫu nhiên thành nhiều lượt tuần tự.
• Đẩy bước tốn kém vào bước đã phải làm (tiền xử lý) và làm lười phần còn lại.
• Đo cả khi kết quả "hiển nhiên": người đọc vẫn nghi ngờ, và con số (1.000 lần) thuyết phục hơn lập luận.

Liên quan

• Jane Street 2026 · Hudson River Trading 2022 · Optiver 2026 (cũng bàn dữ liệu nhiễu trong trading)
• Hạ tầng nghiên cứu định lượng (dữ liệu thị trường, feature, backtest) · Nền tảng ML (feature, training, serving, giám sát model) · Pipeline dữ liệu và analytics