Va chạm dấu thời gian nano giây là chuyện thường gặp
(evanjones.ca)- Trên các hệ thống hiện đại nơi nhiều lõi vật lý cùng đọc đồng hồ đồng thời, dấu thời gian nano giây cũng rất dễ trùng lặp; khi đo đồng thời trên 4 lõi vật lý, khoảng 5% tổng số mẫu bị va chạm
- Thiết kế dùng dấu thời gian thô như một định danh duy nhất là rủi ro, và tần suất va chạm thay đổi tùy theo hệ điều hành và cách thực thi
time.Now()của Go ghi lại cả thời gian tuyệt đối lẫn thời gian tương đối theo đồng hồ đơn điệu, nên có thể tách biệt việc kiểm tra chênh lệch giữa các lần gọi liên tiếp với việc trùng lặp dấu thời gian tuyệt đối- Trên Linux chạy đơn luồng, thời gian luôn tăng và bước tăng nhỏ nhất là 32ns; nhưng khi tách ra nhiều luồng, có thể quan sát thấy cùng một thời gian tuyệt đối
- Trên Mac OS X, thời gian tuyệt đối có độ phân giải micro giây nên va chạm xảy ra nhiều hơn rất nhiều, và ngay cả ở đơn luồng cũng thường xuyên xuất hiện trường hợp đồng hồ đơn điệu không tăng
Tần suất va chạm bộc lộ khi đọc đồng thời
- Câu hỏi cốt lõi là trong các hệ thống hiện đại, va chạm dấu thời gian nano giây thực tế xảy ra thường xuyên đến mức nào
- Khi 4 lõi vật lý cùng đọc đồng hồ đồng thời, khoảng 5% tổng số mẫu bị va chạm
- Ngay cả trên hệ thống 4 lõi, chỉ dùng 2 luồng cũng đã có khoảng 2% dấu thời gian bị trùng
- Vì vậy, giả định rằng chỉ với dấu thời gian nano giây thô là có thể tạo ID duy nhất là không an toàn
Cách thử nghiệm và khác biệt giữa các hệ điều hành
- Chương trình thử nghiệm được viết bằng Go
time.Now()của Go ở mỗi lần gọi sẽ ghi lại cả thời gian tuyệt đối và thời gian tương đối theo đồng hồ đơn điệu- Bài kiểm tra so sánh chênh lệch tương đối giữa các dấu thời gian liên tiếp
- Đồng thời cũng kiểm tra sự trùng lặp của chính dấu thời gian tuyệt đối
-
Linux
- Ở đơn luồng, thời gian tuyệt đối và thời gian đơn điệu luôn tăng
- Bước tăng nhỏ nhất trên hệ thống đo là 32ns
- Giữa các luồng, khoảng 5% trường hợp thời gian tuyệt đối trùng khớp chính xác với luồng khác
-
Mac OS X
- Vì thời gian tuyệt đối có độ phân giải micro giây, trong cùng bài kiểm tra số va chạm xảy ra rất nhiều
- Ngay cả ở đơn luồng cũng thường xuyên quan sát thấy trường hợp đồng hồ đơn điệu không tăng
1 bình luận
Ý kiến trên Hacker News
Dùng ID kết hợp thành phần thời gian và số thứ tự là cách để tránh kiểu vấn đề này
Ví dụ, UUIDv7 có thành phần thời gian ở đơn vị mili giây, có trường tăng dần cho mỗi sự kiện trong cùng một mili giây, và cũng có đủ số bit ngẫu nhiên để xác suất va chạm giữa các ID được tạo trên các máy khác nhau giảm xuống mức cực kỳ nhỏ
Tất nhiên số bit là hữu hạn, nên nếu có quá nhiều sự kiện trong cùng một khoảng thời gian thì bộ đếm thứ tự có thể bị tràn, va chạm giữa các máy vẫn có thể thực sự xảy ra, và phép tăng dần cũng có thể cần đồng bộ CPU nên tốc độ tạo sự kiện có thể bị giới hạn
Dù vậy, ở quy mô thực tế trong công việc, UUIDv7 hoạt động rất tốt
Mình tìm trên Internet mà không thấy rõ UUIDv7 có từ bao lâu rồi
Nó chỉ chiếm mất bit trong UUID mà hầu như không đóng góp gì cho entropy
Dù chưa được tích hợp vào bản thân hệ thống, ngoài việc tự dùng ở tầng ứng dụng thì cũng có vài extension pg rất tốt cung cấp uuidv7
Không chỉ khó hiểu, mà thậm chí còn rất khó để phân biệt chúng với nhau bằng mắt
Vì vậy trong một số trường hợp, một định danh không chứa thêm bất kỳ thông tin hay nhiễu nào ngoài lượng thông tin tối thiểu cần thiết lại rất hữu ích
Một bộ đếm tăng dần có thể tràn dưới bất kỳ dạng nào cùng với một ít bit ngẫu nhiên thường là đủ, và nếu làm khéo thì cả hai đều có thể thực hiện mà không cần nhánh
Nhân tiện, trước đây mình từng là quản lý chương trình phụ trách nhật ký sự kiện bảo mật của Windows
Trên hệ thống đa lõi, khi các việc xảy ra đồng thời hoặc ở thời điểm rất gần nhau, việc lập lịch luồng có thể ảnh hưởng rất lớn đến kết quả quan sát được
Ví dụ, quantum của luồng có thể kết thúc trước khi nó kịp tới lời gọi hệ thống để lấy timestamp, hoặc trước khi chuyển buffer dùng để đưa sự kiện vào hàng đợi nhằm đóng dấu thời gian về sau
Thực tế, trên các hệ thống đa xử lý của Windows trong thập niên 2000, việc các mục trong nhật ký sự kiện trông như bị đảo thứ tự là chuyện rất thường gặp, và cũng không thể tin tưởng độ chính xác của timestamp trong log một cách quá chi li
Giới hạn dưới an toàn trên thực tế gần như là 1 giây, và mình nhớ một số thành phần còn cắt bớt hoặc làm tròn timestamp
Nếu cần định danh duy nhất thì cứ dùng UUID phiên bản 4, tức UUID ngẫu nhiên
Xác suất va chạm cỡ như xác suất một con khủng long trưởng thành đột nhiên xuất hiện trong phòng ngủ vì dao động lượng tử
Nói nghiêm túc hơn thì, nếu dùng được, một giá trị tăng dần kiểu cũ có lẽ là tốt nhất
Nó nhanh và rẻ, đặc biệt là trong cơ sở dữ liệu, nhưng lại có vấn đề về quyền riêng tư và bảo mật vì có thể suy đoán thông tin từ giá trị ID
Trong những trường hợp như vậy, hoặc khi làm việc với hệ thống phân tán, UUID sẽ tốt hơn
Dù độ phân giải là nanô giây, mình vẫn tò mò độ chính xác của đồng hồ máy tính thực tế là đến mức nào
Khó mà tưởng tượng nó thực sự ở mức nanô giây, và điều này làm mình nhớ lại thời dạy thí nghiệm vật lý cho sinh viên, khi mình luôn phải nhấn mạnh rằng con số nhỏ nhất thiết bị đo hiển thị không đồng nghĩa với độ chính xác
Tuy nhiên điều đó không có nghĩa là nó chính xác ở mức đó, và trên hệ thống đa lõi thì đồng hồ giữa các lõi cũng có thể không được đồng bộ ở mức ấy
ARMv8 đảm bảo đồng hồ tăng tối thiểu ở 1GHz, còn Intel và ARM đời cũ thì phức tạp hơn
BEAM VM của Erlang/Elixir làm lộ rõ sự khác biệt này. Đó là sự phân biệt giữa tăng đơn điệu và tăng đơn điệu nghiêm ngặt
https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
“Trong một chuỗi giá trị tăng đơn điệu, mọi giá trị có giá trị đứng trước đều lớn hơn hoặc bằng giá trị đứng trước đó”
Có thể dùng điều này qua hàm https://www.erlang.org/doc/man/erlang.html#monotonic_time-0
https://www.erlang.org/doc/apps/erts/time_correction.html#st...
“Trong một chuỗi giá trị tăng đơn điệu nghiêm ngặt, mọi giá trị có giá trị đứng trước đều lớn hơn giá trị đứng trước đó”
Giá trị đơn điệu nghiêm ngặt hàm ý một dạng đồng bộ hóa hay điều phối nào đó, và đi kèm chi phí hiệu năng khi có nhiều tiến trình đồng thời
Tính năng này được cung cấp qua hàm https://www.erlang.org/doc/man/erlang.html#unique_integer-1, và tài liệu cũng cảnh báo rằng các giá trị tăng đơn điệu nghiêm ngặt vốn dĩ tốn kém để tạo ra và không mở rộng tốt, nên chỉ truyền bộ sửa đổi
monotonickhi thực sự cầnNói cách khác, nó khá giống UUIDv1 hoặc https://en.wikipedia.org/wiki/Snowflake_ID
Chỉ khi bạn cần first/last-write-wins nhất quán ngay lập tức thì định danh toàn cục đơn điệu nghiêm ngặt mới thực sự cần thiết
Thay vào đó, nếu bạn có thể dùng first/last-write-wins nhất quán sau cùng, ví dụ sự kiện ghi đi vào event store hoặc queue nơi các lần ghi được tuyến tính hóa theo ID và trong các lần ghi “đồng thời” chỉ giữ lại cái có độ ưu tiên ID cao nhất rồi loại bỏ phần còn lại trong lúc xử lý hoặc lúc đọc, thì tôi sẽ cân nhắc trước một cặp
(nodeID, seq)được nénNếu cần sắp thứ tự sự kiện toàn cục, thì đặc biệt đáng cân nhắc dạng Snowflake ID như
(timestampMajor, nodeID, timestampMinor, seq)FreeBSD không có
CLOCK_MONOTONIC_RAW, nên khi comment nó đi thì có vẻ ổnTôi hiểu rằng nếu có va chạm thì một số dấu thời gian sẽ phải lặp lại, nhưng tôi không tạo ra va chạm được
clock_getres(CLOCK_REALTIME, ...)=1 ns,clock_getres(CLOCK_MONOTONIC, ...)=1 ns, và trong 30 mẫu thì độ chênh cứ tiếp tục tăng trong khoảng xấp xỉ 29~71nsCuối cùng thì có lẽ ở một thời điểm nào đó mọi chuyện lại quy về vấn đề của kiến trúc tập lệnh
Một CPU chạy ở 3GHz có được 3 chu kỳ xung nhịp mỗi nano giây
Có vẻ khá khả thi là tối ưu hóa của trình biên dịch sẽ đặt các lời gọi assembly đọc thanh ghi đồng hồ sát nhau liên tiếp
Nếu các lệnh gọi
time.Now()liên tiếp xảy ra trong vòng 3 chu kỳ xung nhịp, thì liệu có công bằng khi kỳ vọng độ chính xác nano giây thực sự duy nhất khôngDù va chạm có phần hiếm, việc chúng xảy ra vài lần mỗi ngày vẫn tệ hơn rất nhiều so với “gần như tuyệt đối không xảy ra”
Tôi lại nhớ đến truyền thuyết về Lotus Notes
Hồi xưa người ta nói nó dùng dấu thời gian độ phân giải 1 giây làm ID duy nhất
Nếu xảy ra va chạm thì chỉ việc cộng thêm 1 giây, và cuối cùng va chạm nhiều đến mức các mục bắt đầu có thời gian ở tương lai
Thời gian chính xác tuyệt đối là một vấn đề bảo mật
Các nhà thiết kế CPU từ rất lâu rồi đã cố ý thêm jitter vào đồng hồ để ngăn tính dự đoán hoàn toàn, từ thời Alpha của DEC
Ngay cả trên x86, nếu chạy 3~4 lần, lưu các giá trị vào thanh ghi rồi báo ra sau khi xong, có lẽ bạn sẽ thấy chênh lệch thời gian không hoàn toàn giống hệt nhau
Tôi tìm không ra nhiều, nhưng nếu ý là điều này đã được nhận thức từ sớm đến mức bao gồm cả x86 đời đầu, thì việc vấn đề bảo mật của đồng hồ chính xác đã được nhận ra sớm như vậy khá đáng ngạc nhiên
Cá nhân tôi đoán là trước thiên niên kỷ này tôi còn chưa biết đến các vấn đề như vậy, và sẽ cho rằng jitter quan sát được của đồng hồ có thể giải thích bằng những thứ như ngắt
Không phải tôi nói là sai, chỉ là muốn biết thêm
Tôi đã thấy quá nhiều người ngạc nhiên vì va chạm dấu thời gian ở mức mili giây hay micro giây
Kiểu tôi nhớ nhất và ghét nhất là cách lắp ghép dấu thời gian bằng hai system call
Một lời gọi lấy phần chữ số cao, lời gọi kia lấy phần chữ số thấp; nhưng do tiến trình bị giành CPU, nếu sau khi đọc phần cao mà phần thấp chuyển từ 99x sang 00x, bạn có thể tạo ra một dấu thời gian còn sớm hơn nguyên nhân đã tạo ra thực thể đó
Điều này khiến một số đoạn mã hỏng theo cách cực kỳ ngoạn mục, và tôi đã thấy vòng lặp vô hạn ít nhất hai lần
Nếu bạn không tự nhắc mình phải luôn tránh điều này, thì bài test sẽ pass 99,5% số lần và cần một người có trực giác nhận diện mẫu cực tốt mới phát hiện ra rằng “cùng một bài test đã đỏ mỗi tuần một lần trong suốt một tháng rưỡi”
Đó là khoảng thời gian quá dài để một quả bom logic tồn tại trong mã CI/CD trước khi được sửa