Đối với phần nhiều hệ thống nhỏ tuổi chỉ buộc phải 1 Database thì có thể chẳng mấy ai suy nghĩ việc tạo nên ID cho bạn dạng ghi. Bởi dùng auto increment trong MySQL là hoàn toàn có thể làm được rồi, chẳng yêu cầu phải làm gì thêm.

Bạn đang xem: Shard là gì

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


*
*
*

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

Yêu ước về phương diện 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 khối hệ thống Instagram yêu cầu các gì về ID của từng shard nhé.

ID được tạo nên phải được bố trí theo thời gian. Ví như với 2 ID thì hoàn toàn có thể phán đoán được ID nào tạo thành trước, ID nào tạo ra sau.ID sẽ bao hàm 64 bits. (Vì sao lại buộc phải 64 bits? vị nó tương hợp với các hệ thống như Redis …)Thuật toán ra đời ID phải solo giản, dễ nắm bắt và đặc trưng không được làm chuyển đổi architecture server của Instagram.

1 số chiến thuật generate ID

Hiện tại bao gồm rất nhiều chiến thuật cho việc sinh ra ID unique. Ví dụ như:

Sử dụng tự động hóa increment vào database

Về tác dụng này thì người nào cũng biết rồi. Lúc sinh sản bảng chỉ việc khai báo tự động increment là xong.

Ưu điểm:

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

Nhược điểm:

Chỉ triệu tập vào 1 database với không thể phân loại sang database khác được.Không thể bảo đảm rằng câu hỏi sinh ID ở những database là không trở nên trùng nhau.

Sử dụng UUID

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

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

Ưu điểm:

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

Nhược điểm:

Nó bao hàm 128 bits yêu cầu hơi to, không phù hợp với yêu cầu của khối hệ thống (là 64 bits)Với 2 ID thì không thể rành mạch ID nào sản xuất trước, ID nào chế tạo ra sau.

Snowflake

Đây đó là 1 hình thức sinh ra ID random được cải tiến và phát triển bởi Twitter. Mẫu này áp dụng Apache Zookepper nhằm phối phù hợp với các node để chế tạo ra ID 64 bit duy nhất.

Ưu điểm:

Snowflake ID tất cả 64 bitCó thể áp dụng time vào component thứ nhất của ID nên rất có thể sắp xếp được

Nhược điểm:

Phải gửi ZooKeeper, Snowflake vào trong phong cách thiết kế của Instagram.

Giải pháp của Instagram

Những phương án trên phần nhiều không đáp ứng nhu cầu được yêu ước của Instagram phải họ ra quyết định tự xây dừng cho bản thân 1 chiến thuật riêng.

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

ID sinh hoạt đâ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ó độ lâu năm 64 bits, sẽ bao hàm những bộ phận sau:

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

Câu trả lời là ko nhé. Bởi vì lúc đó thằng sản phẩm công nghệ 1025 hình thành ID sẽ ảnh hưởng trùng cùng với thằng máy 1. Với cả ID là khoá chính nên lúc insert vào sẽ bị lỗi. Nên lúc đó chỉ cần try cach đoạn chính là ok.

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


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

**ID = (Dịch trái time quý phái 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òa hợp lại kỹ năng và kiến thức về bitwise mang đến mọi bạn hiểu nhé:

Dịch trái, dịch cần nó cũng tương tự như bọn họ kéo cảnh cửa ngõ sang trái, sang cần thôi. Trường hợp 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) quý phái trái 5 bit, khi ấy nó đang thành: 11000000bitwise OR có nghĩa là thực hiện nay OR từng bit 1 của 2 số từ buộc phải sang trái. Giả dụ 2 bit đều là 1 trong những thì vẫn cho kết quả là 1, trái lại sẽ cho tác dụng là 0. Ví như 7 (dạng nhị phân là 110) OR 8 (dạng nhị phân là 111) lúc đó kết quả là: 110 OR 111 = 110.

Ví dụ:

Cách tính:

=> ID = 264384000000 ID |= 1001 ID |= (809) Time = (2217813737473025832 >> 23) & 0x1FFFFFFFFFF = 264384000000Shard ID = (2217813737473025832 >> 10) và 0x1FFF = 1001seqID = (2217813737473025832 >> 0) và 0x3FF = 809
Từ phương pháp trên ta hoàn toàn có thể thấy được:

Time sẽ tiến hành tính bằng cách dịch sang bắt buộc ID 23 bit, sau đó thực hiện nay AND với cùng một số 41 bit toàn số 1. Chiếc số 41 bit toàn tiên phong hàng đầu này gửi sang dạng hex vẫn là 0x1FFFFFFFFFF.ShardID và seqId cũng được decode tương tự.

Đây là một example về encode với decode bản thân đã chuẩn bị được. Giành cho ai mong test:


> 23) và 0x1FFFFFFFFFF;$shardId = ($uuid >> 10) & 0x1FFF;$seqId = ($uuid >> 0) & 0x3FF;echo $time . PHP_EOL;echo $shardId . PHP_EOL;echo $seqId . PHP_EOL;
Sau khi đem được shardId là bạn cũng có thể dễ dàng truy vấn vào từng shard để lấy ra record phụ thuộc ID (photoid, postid …) được rồi. Nhưng mà chẳng nên tốn công đi join, select làm những gì cho mệt cả.

Hơn nữa nó làm việc giữa những bit cần cứ call 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)
Khi sản xuất bảng sẽ có tác dụng như sau:


Kết luận

Từ 1 số lượng mà có thể dễ dàng decode nó ra để lấy các thông tin bên trong nó. Đoạn này mình thấy thiệt vi diệu.

Đúng là mấy anh kĩ sư có tay nghề về kiến thiết mấy bo mạch, chip những thứ áp dụng vào thấy nó khác bọt thật.

Xem thêm: Cà Phê Capuchino Là Gì ? Cách Uống Cafe Capuchino Và Các Loại Capuchino

Hi vọng qua bài này đang giúp chúng ta có 1 kỹ năng mới về việc sinh ra ID random, cùng decode ngược lại.