Sharding, Snowflake Instagram trong bài toán đối soát dữ liệu

Có 3 vấn đề về chất lượng dữ liệu của hệ thống:
- Dữ liệu không đồng nhất giữa các phiên bản được lưu trữ tại các kho khác nhau
- Dữ liệu bị trùng lặp
- Dữ liệu bị sai bản chất ngữ nghĩa. Việc sai này có thể do định nghĩa sai, hoặc do nghiệp vụ thay đổi.
Xem thêm tại Quản lí chất lượng dữ liệu

Việc đối soát dữ liệu trong hệ thống có sự trao đổi thông tin(trao đổi nội bộ giữa các phân hệ hoặc giữa ứng dụng với ứng dụng khác) là nghiệp vụ thường xuyên nhằm duy trì chất lượng dữ liệu. Trong bài này, tôi chỉ tập trung vào việc đối soát dữ liệu giữa các phiên bản được lưu trữ tại các kho khác nhau. Kho trong trường hợp này, tôi xem xét là 1 cơ sở dữ liệu quan hệ(oracle, mysql, sql server).

Nguyên lý quản lý đối soát dữ liệu:
1.RÀNG BUỘC
- Nguyên tắc: chỉ đối soát sự tồn tại với phiên bản dữ liệu (data version), không đối soát chi tiết thuộc tính của thực thể(item)
- Lý do: Tất cả các nghiệp vụ trao đổi thông tin đã được xử lý theo giao dịch
2. VẤN ĐỀ MỤC TIÊU
- Đối soát với dữ liệu lớn, bảng lớn, đảm bảo không gây ảnh hưởng hiệu xuất
- Đối soát đảm bảo dữ liệu đầy đủ, trong điều kiện có ít nhất 1 trong các phần tử đối soát bị biến động
3. GIẢI PHÁP
Sử dụng 1 cột tên VER kiểu number, sử dụng kỹ thuật tạo id của Instagram gán giá trị tăng dần khi dòng bị thay đổi dữ liệu. Cách này giải quyết được 2 vấn đề mục tiêu nêu ở trên do:
- VER đóng vai trò chứa giá trị phiên bản dữ liệu
- VER chứa thông tin nguồn gốc của dữ liệu gốc (thuật toán của Instagram có thể dịch ngược để biết được nguồn gốc của dữ liệu )
- VER định danh được thực thể (row-item)  -> giúp đối soát gia tăng (incrementall).
- VER index tốt
Giải pháp này sử dụng kỹ thuật đối soát gia tăng. Đối soát gia tăng thực hiện lần lượt với các thực thể dữ liệu. Đối với các thực thể phát sinh mới, việc đối soát chỉ cần thực hiện với các thực thể mới, lần lượt cho đến hết. Trong 1 số trường hợp, dev có xu hướng sử dụng việc chụp(snap) dữ liệu tại 1 thời điểm của dữ liệu nguồn và đích và thực hiện so sánh toàn bộ dữ liệu. Cách chụp dữ liệu và đối soát chỉ đúng trong trường hợp, trong thời gian so sánh, dữ liệu nguồn và đích không bị thay đổi.

Sharding là gì?

Sharding là công việc tác Database thành nhiều Database khác nhau, mỗi database sẽ chứa 1 phần dữ liệu. Ví dụ tách bảng user ra nhiều database, mỗi database sẽ chứa 1 phần dữ liệu của bảng user.

Instagram là 1 trong những mạng xã hội chia sẻ ảnh nổi tiếng nhất cái hành tinh này. Theo thống kê năm 2016 thì cứ mỗi giây sẽ có 915 photos, 1k post được tạo ra. Quá khủng khiếp phải không nào. Khi dữ liệu tăng lên kinh khủng như thế thì 1 database sẽ không thể lưu trữ hết được dữ liệu, cùng với tốc độ truy vấn sẽ trở nên ì ạch và tốn nhiều dung lượng bộ nhớ.

Để đảm bảo tất cả dữ liệu quan trọng luôn được lưu trữ trên memory, và sẵn sàng trả về kết quả nhanh nhất cho người dùng thì Instagram bắt đầu thực hiện Sharding dữ liệu.

Tuy nhiên tại thời điểm này có 1 bài toán được đặt ra. Làm thế nào có thể sinh ra ID duy nhất trên từng shard mà không sợ bị trùng lặp (Ví dụ như mỗi photo được upload vào trong hệ thống)? Cùng đi đọc tiếp phần tiếp theo nhé.

Yêu cầu về mặt chức năng

Trước khi đi vào giải quyết bài toán bên trên, thì cùng xem hệ thống Instagram yêu cầu những gì về ID của từng shard nhé.

• ID được tạo ra phải được sắp xếp theo thời gian. Ví dụ như với 2 ID thì có thể phán đoán được ID nào tạo ra trước, ID nào tạo ra sau.
• ID sẽ bao gồm 64 bits. (Vì sao lại cần 64 bits? Vì nó tương thích với các hệ thống như Redis …)
• Thuật toán sinh ra ID phải đơn giản, dễ hiểu và đặc biệt không được làm thay đổi architecture server của Instagram.

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

Hiện tại có rất nhiều giải pháp cho việc sinh ra ID unique. Cụ thể như:

Sử dụng auto increment trong database

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.

Sử dụng UUID

Đâ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.

Thế nhưng cùng xem nó có ưu điểm nhược điểm gì nhé.

Ư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.

Snowflake

Đâ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. (Xem thêm cách Twitter ngăn người dùng view page source.)

Ư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 Instagram.

Giải pháp của Instagram

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 nhé. 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:

1 2 3 4 5 6 7 8

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)

Để mình tổng hợp lại kiến thức về bitwise cho mọi người hiểu nhé:

• 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 thô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?

Đây có lẽ là phần mình thấy hay nhất. Chúng ta cùng xem tiếp nhé:

1 2 3 4 5

Time      = (2217813737473025832 >> 23) & 0x2FFFFFFFFFF = 264384000000 Shard ID  = (2217813737473025832 >> 10) & 0x2FFF = 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ự.

Đây là 1 example về encode và decode mình đã chuẩn bị được. Dành cho ai muốn test:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

<?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) & 0x2FFFFFFFFFF; $shardId = ($uuid >> 10) & 0x2FFF; $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/SQL trong Oralce:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

CREATE SEQUENCE snowflake_seq MINVALUE 1 MAXVALUE 999999999999999999999999999 START WITH 1 INCREMENT BY 1 CACHE 50; / CREATE OR REPLACE FUNCTION bitor (x NUMBER, y NUMBER) RETURN NUMBER DETERMINISTIC IS BEGIN RETURN x - BITAND (x, y) + y; END; / CREATE OR REPLACE FUNCTION timestamp_diff (a TIMESTAMP, b TIMESTAMP) RETURN NUMBER IS BEGIN RETURN EXTRACT (DAY FROM (a - b)) * 24 * 60 * 60 + EXTRACT (HOUR FROM (a - b)) * 60 * 60 + EXTRACT (MINUTE FROM (a - b)) * 60 + EXTRACT (SECOND FROM (a - b)); END; / CREATE OR REPLACE FUNCTION snowflake_next_id RETURN NUMBER DETERMINISTIC IS our_epoch TIMESTAMP := TO_TIMESTAMP ('2015-01-01', 'yyyy-mm-dd'); seq_id NUMBER (15); now_millis NUMBER (15); shard_id NUMBER (5) := 5; result NUMBER; BEGIN seq_id := snowflake_seq.NEXTVAL MOD 1024; now_millis := timestamp_diff (SYSTIMESTAMP, our_epoch); result := now_millis * POWER (2, 23); --Bitwise Left Shift result := BITOR (result, (5 * POWER (2, 10))); result := BITOR (result, (seq_id)); RETURN result; END; / SELECT snowflake_next_id () FROM DUAL; /

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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:

1 2 3 4 5 6

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