Sharding & IDs at Instagram

Instagram · 2011 · 1. Khởi đầu · Độ khó: Trung bình — bài gốc

Bối cảnh

Khoảng 25 ảnh và 90 like mỗi giây (2011). Họ shard để dữ liệu quan trọng luôn vừa trong bộ nhớ.
App Django + PostgreSQL. Họ đã cân nhắc vài giải pháp NoSQL nhưng quyết định giữ Postgres và shard trên nhiều server Postgres.
Hệ quả đầu tiên: auto-increment của một DB không còn cho ID duy nhất khi ghi vào nhiều DB.

Thay đổi chính

Yêu cầu cho ID: sắp được theo thời gian (không cần tra thêm thông tin để sắp ảnh); vừa 64 bit (index nhỏ, lưu tốt trong Redis); càng ít "thành phần chuyển động" càng tốt.
Ba phương án đã cân nhắc:
- ID sinh trong app (UUID, Mongo ObjectId): độc lập, nhưng ≥96 bit, UUID ngẫu nhiên không sắp được.
- Dịch vụ riêng như Twitter 2010: 64 bit, sắp được, nhưng thêm ZooKeeper + service phải vận hành.
- Ticket server kiểu Flickr: đơn giản, nhưng có thể thành nút thắt ghi; dùng nhiều DB thì mất thứ tự thời gian.
Giải pháp: hàng nghìn shard logic ánh xạ trong code vào ít shard vật lý. Mỗi shard logic là một schema Postgres. Khi cần thêm máy, chỉ việc dời shard logic sang máy mới, không phải chia lại dữ liệu.
ID 64 bit sinh trong Postgres bằng PL/pgSQL: 41 bit thời gian (ms, epoch riêng, đủ ~41 năm) + 13 bit shard logic + 10 bit sequence (mod 1024), tức 1024 ID mỗi shard mỗi ms. ID trả về app bằng RETURNING.

Vì sao

Theo Instagram: Snowflake gần nhất với nhu cầu, nhưng thêm một service là thêm độ phức tạp. Phần lớn cách họ scale được với ít kỹ sư là chọn giải pháp đơn giản, dễ hiểu, đáng tin. Họ lấy ý tưởng của Snowflake rồi đưa vào bên trong DB.

Bài học cho SWE

Shard logic nhiều hơn máy vật lý giúp sau này mở rộng chỉ bằng cách dời shard.
ID mang sẵn shard ID nên biết ngay bản ghi nằm đâu.
So sánh các phương án theo yêu cầu cụ thể (sắp xếp, số bit, thành phần vận hành) thay vì theo độ "xịn".