Tạo các UUID thực sự độc đáo trong JavaScript và AS3 - PRNG và các thuật toán cơ bản

Question

Tôi đang làm việc trên một hệ thống tạo ra khoảng 2 tỷ UUID duy nhất mỗi ngày. UUID được tạo bằng JavaScript \ Flash (AS3) trên máy khách.

Gần đây chúng tôi nhận thấy rằng các UUID của chúng tôi không có nơi gần độc đáo. Chúng tôi có khoảng 20% ​​(!) Bản sao hàng ngày, hầu hết trong số đó (liên quan đến lưu lượng truy cập) đến từ chrome.

Tôi đã thực hiện some readingand learnedthat the pseudo-random triển khai thuật toán thế hệ (PRNG) trên hầu hết các trình duyệt và đặc biệt là chrome, là thiếu sót. Chromium và Node.js sử dụng công cụ V8Script V8, thực hiện một thuật toán gọi là MWC1616. Theo lý thuyết, UUID được tạo ra bằng cách sử dụng PRNG tốt phải có 2¹³² probability cho va chạm, nhưng với MWC1616, trong một số trường hợp rất thực tế, xác suất này là khoảng 1: 30000.

Để giải quyết vấn đề, tôi coi các tùy chọn sau:

1. Tạo ID trên máy chủ (sử dụng Go)
2. Tạo một ID mạnh trên máy khách, bằng cách băm một số thông tin như IP, UA , dấu thời gian, v.v. với UUID.
3. Thay thế Math.random() bằng trình tạo ngẫu nhiên tốt hơn.

Vì tôi muốn giữ chúng trên máy khách và tôi không muốn tái phát minh ra bánh xe và sửa đổi logic tạo UUID, tôi muốn gắn bó với tùy chọn 3.

Tin tốt lành là trên các trình duyệt mới hơn, có api getRandomValues. Thật không may, tôi cần hỗ trợ các trình duyệt cũ hơn.

Vì vậy, câu hỏi của tôi là:

1. một tốt và đáng tin cậy polyfill JavaScript cho

crypto.getRandomValues ​​()

(mà không sử dụng Math là gì .random nội bộ)?

2. AS3 Math.random() có sử dụng Math.random() của trình duyệt không? Liệu nó có thực hiện cùng một thuật toán không?

3. Flash.crypto.generateRandomBytes() có sử dụng Math.random() không? Nó có sử dụng crypto.getRandomValues ​​() không? Nếu không, thuật toán nào nó thực hiện và nó sẽ là một giải pháp tốt cho cùng một vấn đề trong AS3? Nếu không, bạn nên giới thiệu thư viện mã hóa AS3 nào?

P.S. Tôi đánh giá cao các bài viết tôi đã đề cập -1--2--3-. Tôi đã nhận thức được các vấn đề với Math.random() trong nhiều năm, nhưng bài viết này thực sự làm cho nó rõ ràng với tôi cho tốt.

Answer 1

Sau khi dành hơn một tuần nghiên cứu điều này - kết luận của tôi là: KHÔNG BAO GIỜ TẠO UUID trên máy khách. Chỉ cần không.Đặc biệt là nếu bạn có ý định mở rộng quy mô.

Trong nhiều năm, tôi biết rằng việc thực thi Math.random của trình duyệt rất kém, nhưng tôi không hiểu nó tệ như thế nào, cho đến khi chúng tôi đạt đến hàng tỷ sự kiện mỗi ngày.

Tôi quyết định đi với giải pháp kỹ thuật đơn giản nhất và di chuyển UUID thế hệ sang máy chủ. Tỷ lệ ID trùng lặp khi giảm từ ~ 25% một ngày thành ~ 0,0008%.

P.S. Máy chủ của chúng tôi được triển khai trong Go. Node.js sử dụng công cụ JavaScript V8 và có thể có cùng vấn đề. Mặc dù nó có vẻ như nếu bạn đang sử dụng Node.js mới nhất, bạn nên ổn.