Một số giải pháp generate ID

Đối với những hệ thống nhỏ chỉ cần 1 Database thì chắc chẳng mấy ai quan tâm đến việc tạo ra ID cho bản ghi. Vì dùng auto increment trong MySQL là có thể làm được rồi, chẳng cần phải làm gì thêm.

Thế nhưng với dữ liệu càng ngày càng to ra thì hệ thống chỉ có 1 database duy nhất có thể sẽ không thể đáp ứng được. Bởi vì traffic đang tập trung hết vào database đó.

Để giải quyết bài toán đó thì người ta đã tách database ra thành nhiều database khác nhau, và mỗi database đó sẽ chứa 1 phần dữ liệu. Ví dụ db01 chứa thông tin user từ 1 đến 1000, db02 chứa thông tin user từ 1001 đến 2000 chẳng hạn. Và khi query sẽ tìm xem user thuộc database nào và thực hiện truy vấn.

Và kĩ thuật này người ta gọi là sharding.

Thế nhưng có vấn đề xảy ra ở đây là làm thế nào sinh ra ID cho user mà không bị trùng lặp giữa các database đó? Dùng auto increment mặc định của database có giải quyết được không? Làm thế nào để từ 2 ID có thể phán đoán cái nào được sinh ra trước, cái nào được sinh ra sau?

Vậy cùng đọc bài này xem các kĩ sư Instagram đã giải quyết bài toán này thế nào nhé.

Mục tiêu bài viết:

• Hiểu thêm được 1 cơ chế sinh ID mới.
• Có thể áp dụng vào các bài toán sharding data trong database.

https://nghethuatcoding.com/2019/05/19/instagram-da-sinh-ra-id-trong-database-cua-ho-nhu-the-nao/

instagram_da_sinh_ra_id_trong_database_cu_a_ho_như_thê_na_o_-_nghe_̂_thua_̂t_coding.pdf

Về chức năng này thì ai cũng biết rồi. Lúc tạo bảng chỉ cần khai báo auto increment là xong.

Ưu điểm:

• Cách dùng đơn giản.

Nhược điểm:

• Chỉ tập trung vào 1 database và không thể phân chia sang database khác được.
• Không thể đảm bảo rằng việc sinh ID ở nhiều database là không bị trùng nhau.

Đây cũng là 1 cách khá hay để giải quyết bài toán. UUID là 1 chuẩn chung nhằm sinh ra chuỗi random không trùng nhau (xác suất gần như bằng 0). Ví dụ như: b875d561-20fd-498d-8452-5d5ffa879856.

Ưu điểm:

Cho dù chạy trên nhiều máy tính cùng thời điểm đi chăng nữa thì xác suất các string đó trùng nhau dường như gần bằng 0.

Nhược điểm:

• Nó bao gồm 128 bits nên hơi to, không phù hợp với yêu cầu của hệ thống (là 64 bits)
• Với 2 ID thì không thể phân biệt ID nào tạo trước, ID nào tạo sau.

Đây chính là 1 công cụ sinh ra ID random được phát triển bởi Twitter. Cái này sử dụng Apache Zookepper để phối hợp với các node để tạo ID 64 bit duy nhất.

Ưu điểm:

• Snowflake ID có 64 bit
• Có thể sử dụng time trong component đầu tiên của ID nên có thể sắp xếp được

Nhược điểm:

• Phải đưa ZooKeeper, Snowflake vào trong kiến trúc của dự án.

Những giải pháp trên đều không đáp ứng được yêu cầu của Instagram nên họ quyết định tự xây dựng cho mình 1 giải pháp riêng.

Họ sẽ dùng thuật toán đơn giản để sinh ra 1 chuỗi ID random duy nhất từ 1 số input đầu vào. Và từ chuỗi ID đó có thể decode ngược lại để lấy ra được input.

ID ở đây chính là ID của photo, ID của posts chẳng hạn.

Database họ sử dụng là PostgreSQL.

Cụ thể như sau.

ID có độ dài 64 bits, sẽ bao gồm những bộ phận sau:

• 41 bits để lưu thời gian (đơn vị milliseconds). Khoảng thời gian này sẽ được tính từ ngày 2011/01/01 00:00.
• 13 bits để lưu shard ID. (tối đa có thể tạo ra được 2^13 = 8192 shard)
• 10 bits để lưu auto-incrementing sequence, sau đó module 1024. (Vì sao lại là 1024 vì tối đa có 10 bit thôi, mà 2^10 = 1024). Điều đó có nghĩa là có thể tạo ra 1024 IDs trên 1 shard, trên millisecond.

Câu hỏi đặt ra là nếu tạo upload quá 1024 bức ảnh trong 1ms có được không?

Câu trả lời là không. Vì lúc đó thằng thứ 1025 sinh ra ID sẽ bị trùng với thằng thứ 1. Với cả ID là khoá chính nên khi insert vào sẽ bị lỗi. Nên lúc đó chỉ cần try cach đoạn đó là ok.

Công thức sinh ID như sau:

ID = (time << 23) | (shardID << 10) | (seqId <<0)

Trong đó:

• time = now - instagram_epoch_time (2011/01/01 00:00)
• shardId = userId % 2000
• seqId = (currentSeqID + 1) % 1024

Từ công thức trên ta có thể thấy ID được tạo ra bằng cách:

ID = (Dịch trái time sang trái 23 bit) bitwise OR (dịch trái shardID 10 bit) bitwise OR (dịch trái seqID 0 bit)

• Dịch trái, dịch phải nó cũng giống như chúng ta kéo cảnh cửa sang trái, sang phải. Nếu dịch trái n bit tức là sẽ điền n số 0 vào sau số đó. Ví dụ như dịch trái số 7 (dạng nhị phân là 110) sang trái 5 bit, khi đó nó sẽ thành: 11000000
• bitwise OR tức là thực hiện OR từng bit 1 của 2 số từ phải sang trái. Nếu 2 bit đều là 1 thì sẽ cho kết quả là 1, ngược lại sẽ cho kết quả là 0. Ví dụ như 7 (dạng nhị phân là 110) OR 8 (dạng nhị phân là 111) khi đó kết quả là: 110 OR 111 = 110.

Ví dụ:

Giả sử như người dùng có user_id là 5001, post bức ảnh lên instagram vào thời điểm 2019/05/19 00:00. Tại thời điểm đó sequence hiện tại của table đang là 9000.

Cách tính:

Do thời gian được tính từ ngày 2011/01/01 00:00 nên từ thời điểm đó đến ngày 2019/05/19 00:00 có time = 264384000000 ms.

⇒ ID = 264384000000 « 23 (dịch sang trái 23 bit)

Do user_id = 5001, và instagram chỉ có 2000 shard. Nên shardId = 5001 % 2000 = 1001

⇒ ID |= 1001 « 10

sequence hiện tại của table đang là 9000, khi đó next_sequence_id là 9001. vậy seqId = 9001 % 1024 = 809

⇒ ID |= (809) « 0

Sau khi tính chúng ta ra kết quả ID = 2217813737473025832.

Vậy làm thế nào mà từ số 2217813737473025832 chúng ta có thể decode ngược lại ra time là 264384000000, shardId là 1001, seqId là 809?

Time      = (2217813737473025832 >> 23) & 0x1FFFFFFFFFF = 264384000000
Shard ID  = (2217813737473025832 >> 10) & 0x1FFF = 1001
seqID     = (2217813737473025832 >>  0) & 0x3FF = 809

Từ công thức trên ta có thể thấy được:

• Time sẽ được tính bằng cách dịch sang phải ID 23 bit, sau đó thực hiện AND với 1 số 41 bit toàn số 1. Cái số 41 bit toàn số 1 này chuyển sang dạng hex sẽ là 0x2FFFFFFFFFF.
• ShardID và seqId cũng được decode tương tự.

Ví dụ:

<?php
 
$uuid = 0;
 
$userId = 5001;
$currentSequenceId = 9000;
$time = 264384000000;
 
// ENCODE
 
$shardId = $userId % 2000;
$seqId = $currentSequenceId % 1024;
 
$uuid = $time << 23;
$uuid = $uuid | ($shardId << 10);
$uuid = $uuid | ($seqId);
 
echo $uuid . PHP_EOL;
 
// DECODE
 
$time = ($uuid >> 23) & 0x1FFFFFFFFFF;
$shardId = ($uuid >> 10) & 0x1FFF;
$seqId = ($uuid >> 0) & 0x3FF;
 
echo $time . PHP_EOL;
echo $shardId . PHP_EOL;
echo $seqId . PHP_EOL;

Sau khi lấy được shardId là chúng ta có thể dễ dàng truy cập vào từng shard để lấy ra record dựa vào ID (photo_id, post_id …) được rồi. Mà chẳng phải tốn công đi join, select làm gì cho mệt cả.

Hơn nữa nó thao tác giữa các bit nên cứ gọi là nhanh đừng hỏi.

Và đây là ví dụ về PL/PGSQL trong PostgreSQL:

CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$
DECLARE
    our_epoch bigint := 1293843600000;
    seq_id bigint;
    now_millis bigint;
    shard_id int := 5;
BEGIN
    SELECT nextval('insta5.table_id_seq') %% 1024 INTO seq_id;
    SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;
    result := (now_millis - our_epoch) << 23;
    result := result | (shard_id <<10);
    result := result | (seq_id);
END;
    $$ LANGUAGE PLPGSQL;

Khi tạo bảng sẽ làm như sau:

CREATE TABLE insta5.our_table (
    "id" bigint NOT NULL DEFAULT insta5.next_id(),
    ...rest of table schema...
  )

$bitCount = (int)(log(999999999999) / log(2)) + 1;
 
Eg. Encode 16bit
$a: 12bit -> shift left = 16 - 12 = 4
$b: 4bit -> shift left = 4 - 4 = 0
php > $a = 6;
php > $b = 2;
php > $a = $a << 4;
php > $b = $b << 0;
php > $c = $a | $b;
php > echo $c;
98
php > dechex(bindec(111111111111)); // https://www.rapidtables.com/convert/number/binary-to-hex.html
php > echo dechex(bindec(111111111111)); // 16 - x = 4: x là 12 số 1
fff
php > echo dechex(bindec(1111)); // 4 - x = 4: x là 4 số 1
f
php > $d_a = $c >> 4 & 0xfff;
php > echo $d_a;
6
php > $d_b = $c >> 0 & 0xf;
php > echo $d_b;
2

Example: 64 bit = 30 bit user id, 4 bit object type & 30 bit object id

    /**
     * @param $userId
     * @param $objectType
     * @param $objectId
     * @return int
     */
    function generateObjectId($userId, $objectType, $objectId)
    {
        return ($userId << 34) | ($objectId << 4) | ($objectType << 0);
    }
 
    /**
     * @param $id
     * @return array
     */
    function decodeObjectId($id)
    {
        $userId = $id >> 34 & 0x3FFFFFFF;
        $objectId = $id >> 4 & 0x3FFFFFFF;
        $objectType = $id >> 0 & 0xF;
 
        return [
            'user_id' => $userId,
            'object_type' => $objectType,
            'object_id' => $objectId,
        ];
    }