UUID là gì?
UUID là viết tắt của Universally Unique IDentifier
Một cách dễ hiểu, UUID là 1 thứ duy nhất mà không chỗ nào khác đã có trong hệ thống của chúng ta.
Nó khác gì với 1 ID là primary key truyền thống
- Primary key truyền thống thường có dạng auto-increase với độ lớn là 1 số int 32 hoặc 64bit. Dẫn tới việc, gặp rắc rối khi sharding ra nhiều server khác nhau (lúc này ID có thể trùng với các db server khác)
- ID chỉ lưu 1 con số increase, nó chỉ ra thứ tự trước sau của 1 ID, và cũng không lưu thêm những thông tin đại diện khác như ID thuộc server db nào, hay thời gian tạo ID là lúc nào.
Các UUID thông dụng
- Dạng UUID truyền thống — 128bit
Cấu trúc nó gồm 32 số hex nằm trong 5 nhóm theo công thức số lượng là 8–4–4–4–12. Ví dụ:
xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
123e4567-e89b-12d3-a456–426655440000
Đây là dạng UUID phổ biến của các database system hiện nay, kiểu UUID này là duy nhất vì bao hàm cả thông tin server_id, timestamp .. trong đó. Nhược điểm của nó, chỉ là khó nhìn, khó đọc.
2. UUID dạng số, thông thường là 64bit: Trong bài article này, ta chỉ đi vào phân tích dạng UUID số 64bit này.
UUID dạng số
Yêu cầu đưa ra, là cần tạo 1 UUID dạng số, đại diện được sự duy nhất cho data của chúng ta (có nghĩa là nó không bị trùng lắp với bất kỳ 1 ID của data nào khác đã tồn tại trước đó)
Hiện tại, cũng chưa có 1 chuẩn nào quy định việc tạo ra 1 UUID dạng số theo 1 format nào.
Vì vậy, mình sẽ đi tìm hiểu những ông lớn công nghệ, xem họ làm như thế nào. Sau đó, có thể bắt chước làm theo.
1 là từ 1 bài sharding của instagram về khởi tạo UUID tại đây.
2 là từ 1 bài sharding của pinterest, có thể xem thêm lại đây.
3 là từ hàm UUID_SHORT() của mysql, có thể xem thêm lại đây.
UUID dạng number 64bit
Vì sao UUID này nên là 1 con số ?
Đơn giản là vì tính dễ đọc, dễ hiểu của nó. Ví dụ như khách hàng của bạn bị 1 sự cố nào đó, họ gọi đến tổng đài CSKH để báo cho bạn, thay vì đọc 1 chuỗi dài loằng ngoằng, dễ nhầm lẫn, thì nếu ID là 1 con số sẽ có vẻ dễ dàng đọc, tìm kiếm, tra cứu .. hơn nhiều, đúng không?
Trong thực tế, thì các con số ID này cũng thường là số, hãy check xem số IMEI của apple hay facebook_id, pinterest pin_id, instagram user_id .. tất cả đều là các con số nguyên 64bit.
Cấu trúc của 1 UUID dạng số
Vì sao phải là 1 số nguyên 64bit ?
Để tiện lợi cho việc xử lý tính toán trên các HDH, các số thường có kích thước 32bit, 64bit .. chính là bội số của 1 WORD trong hệ điều hành.
Vì sao không phải là 32bit ?
32bit quá ít, không để lưu trữ được nhiều dữ liệu.
Có 3 loại dữ liệu khá quan trọng để lưu lại, và đảm bảo được tính unique của 1 ID bao gồm:
server_id hoặc shard_id: là instance id tạo ra ID này
timestamp: thời điểm thêm id này vào
counter: là 1 biến auto increase, maximum của biến này tương đương số lượng ID có thể tạo ra trong 1 đơn vị timestamp nên trên.
Cho 1 ví dụ như sau:
Tạo 1 UUID 64 bit đơn giản với cấu trúc bao gồm, 41 bit đầu để lưu trữ timestamp, 13 bit sau đó để lưu server_id và 10bit cuối để lưu giá trị của counter.
Timestamp (ô màu xám) : giả sử nó chiếm 41bit, tức là giá trị lớn nhất của số timestamp này sẽ là 2 ^ 41 = 2199023255553, tức là tới khoảng thời điểm 2039–09–07T15:47:35.000Z.
Server_id hoặc shard_id (ô màu xanh) : giả sử nó chiếm 13bit, tức là giá trị lớn nhất của số timestamp này sẽ là 2 ^ 13 = 8192, như vậy, không thể tạo ra hơn 8192 database server sinh ra UUID cùng 1 lúc được. Con số này quá lớn nên ta cũng không phải lăn tăn.
Thực tế, 1 hệ thống với 8192 replicate hoặc sharding database là quá đủ để serves cho rất rất rất nhiều request rồi.
Counter (ô màu vàng) : giả sử nó chiếm 10bit, tức là giá trị lớn nhất của số timestamp này sẽ là 2 ^ 10 = 1024, như vậy, không thể tạo ra hơn 1024 ID trong 1 millisecond được.
Con số 1024 này thực ra rất lớn. Vì trong 1 giây, thì số ID sinh ra tối đa sẽ thành 1,024,000 cái. Và sau 1 giờ, nếu việc sinh ID này liên tục, thì nó cũng đã sinh ra tối đa tới hơn 3 tỉ cái ID. Bằng ½ dân số thế giới rồi.
1 cách tóm lại:
- Trong 1 millisecond, ta có thể gen ra nhiều nhất 1024 số unique duy nhất trong 1 shard.
- Không shard nào có ID giống ID của shard khác
- Không có ID nào sinh ra trùng với ID đã tạo ra ở giây trước đó.
Tạo UUID như thế nào
Các bước tạo 1 UUID dạng này.
- Nạp số timestamp, dịch qua trái 23 bit, rồi đưa vào UUID. Lúc này khu lưu trữ timestamp là 64–23 = 41bit, và khu còn lại còn 24 bit 0.
2. Tạo shard_id, dịch qua trái 10 bit. Lúc này khu lưu trữ shard_id là 13 bit, khu còn lại là 0bit. Lúc này phải dùng phép OR để nạp vào UUID (vì nguyên tắc: bit nào OR với 0 cũng sẽ ra kết quả bằng biến đó)
3. Tương tự,nạp số counter vào. Sau đó thực hiện phép OR với phần còn lại, để tạo thành 1 UUID hoàn chỉnh.
Từ dãy nhị phân này, sẽ tạo ra 1 con số thập phân UUID cuối cùng.
Hiện thực tạo UUID trên Javascript
encode(
264384000000,
2,
147
);
> 2217813737473025832
Như vậy, chúng ta đã hoàn thành bước tạo UUID theo chính cách mà Instagram đã làm trên javascript theo bài viết đã đề cập ở đầu bài.
Decode UUID như thế nào ?
Từ 1 UUID ta hoàn toàn có thể decode ra 3 thông tin nó đang chứa 1 cách rất dễ dàng.
Để lấy thông tin của timestamp, rất đơn giản, là dịch 41 bit về lại bên phải, rồi thực hiện phép AND với 1 vùng có 41 số 1 (nguyên tắc: bit nào AND với 1 sẽ ra chính nó).
Tương tự, với các thành phần còn lại.
Hiện thực decode trên javascript
Các con số dùng cho phép and trong code là dạng hexa. Nó chính là:
11111…11111 (41 số 1): 0x1ffffffffff
11111111111111: 0x1fff
11111111111: 0x3ff
Bạn có thể kiểm tra lại qua trang web chuyển đổi sau đây
Sau đó, tiến hành chạy thử:
decode(‘2217813737473025832’);
> {
time: 264384000000,
serverId: 2,
counter: 147
}
Một ví dụ khác với UUID — Mysql UUID_SHORT()
1 ví dụ khác là hàm UUID_SHORT() của mysql. Xem thông tin hàm đó tại đây
Hàm này, cơ bản cũng tạo ra 1 số UUID 64bit với kiến trúc như sau
(server_id & 255) << 56
+ (server_startup_time_in_seconds << 24)
+ incremented_variable++;
Áp dụng kiến thức vừa đề cập ở trên, ta cũng dễ dàng tạo ra UUID theo kiến trúc như trên và thử so sánh với kết quả trả về của chính mysql_server để so sánh nhé.
Tiến hành kiểm tra. Để ý thấy tham số time là time từ lúc start server. Vì thế, mình cần restart mysql, lúc status vừa qua trạng thái running thì phải chạy ngay app của mình.
const server_time = Math.floor(new Date().getTime() / 1000);
encode_mysql(
1,
server_time,
0
);
> 98556460643909632
Cũng cùng lúc đó, thực hiện câu lệnh mysql như sau
SELECT UUID_SHORT();
> 98556460442583040
2 kết quả có vẻ là gần như giống nhau, có thể thấy server_id chắc chắn là 1, time second là gần bằng nhau. Đây chính là cách UUID dạng số mà mysql sử dụng.
Với pinterest, họ lưu trữ UUID mà ko có timestamp, tuy nhiên ý tưởng lưu trữ dạng số 64bit này cũng vẫn giữ nguyên. Trong 64 bit này có 3 thành phần là ShardId, TypeId và LocalId như thông tin bên dưới.
Chia 3 phân vùng như thế nào?
Một câu hỏi đưa ra, là chia 3 phân vùng này như thế nào cho hợp lý.
Hãy để ý lại cách mysql tạo UUID dạng số.
mysql dành ra chỉ 32bit để lưu trữ timestamp dạng second, nhưng lại từ lúc start_server. Vì lưu dạng second nên không gian của timestamp này lên tới thời điểm 2106–02–07T06:28:16.000Z.
Tuy nhiên, vùng counter lại lên đến 24bit, tương ứng với số lớn nhất có thể lưu trữ là 16777216 . Tức là hơn 16 triệu ID có thể sinh ra trong 1 lần running mysql.
Cách sinh UUID này, rõ ràng không dành cho số lượng ID sinh ra lớn quá 16 triệu ID, nếu muốn gen ra lớn hơn phải restart lại bộ sinh UUID (tương đương với restart lại mysql).
Tóm lại, tùy vào độ lớn của database, cũng như số lượng ID phải được sinh ra trong 1 thời điểm nhiều như thế nào, mà ta có thể cân đối số bit dành cho các thành phần nêu trên.
Nếu số lượng ID sinh ra trong 1 millisecond là quá lớn, có thể dùng cách lưu trữ của instagram. Cách này về cơ bản, mỗi lần sinh ra ID đều phải tính lại timestamp. Độ phức tạp thời gian tính toán là:
T(get_current_timestamp) + 3 x T(shiftLeft) + 3 x T(or)
Nếu tổng lượng ID sinh ra không quá lớn, có thể dùng cách của mysql. Cách này không phải tính lại timestamp, giúp tăng tốc quá trình sinh UUID, bù lại là số ID lưu trữ không cao. Độ phức tạp thời gian tính toán là:
3 x T(shiftLeft) + 3 x T(or)
Bài viết này là của tác giả tranquansp.
