Tự tay xây dựng cơ sở dữ liệu chuỗi thời gian từ số 0

• Được viết bằng Go nhưng hầu như không phụ thuộc ngôn ngữ

• Dữ liệu chuỗi thời gian là tập hợp nhiều giá trị gắn kèm dấu thời gian. Mỗi mục là một điểm dữ liệu

→ Lượng dữ liệu rất lớn. Phải đủ lớn thì mới có ý nghĩa. Nhiều trường hợp được ghi nhận tới hàng triệu lần mỗi giây

→ Chỉ thêm vào (append-only), sắp xếp theo thời gian, ưu tiên dữ liệu gần đây

→ Đọc hàng loạt theo các đơn vị thời gian cụ thể

→ High Cardinality (đơn vị tập hợp rất lớn)

→ Phần lớn được sử dụng bằng cách đọc dữ liệu gần đây

• Dựa trên đặc tính ghi nhiều của dữ liệu chuỗi thời gian, tác giả phát triển thư viện engine DB TStorage bằng ngôn ngữ Go

• Mô hình dữ liệu

→ Mô hình dữ liệu tuyến tính

→ Phân vùng các điểm dữ liệu theo đơn vị thời gian

→ Mỗi phân vùng hoạt động như một DB độc lập riêng biệt chứa toàn bộ dữ liệu trong khoảng thời gian đó

→ Chỉ head và phân vùng kế tiếp được giữ trên heap nên có thể sửa thành phân vùng bộ nhớ

→ Để tránh mất dữ liệu, ghi vào WAL (Write Ahead Log) trước khi ghi thực tế

→ Dữ liệu của các phân vùng trước đó được lưu trên đĩa thành một tệp đơn. Các phân vùng trên đĩa là chỉ đọc

• Phân vùng bộ nhớ

→ Danh sách các điểm dữ liệu được biểu diễn thành mảng trên heap (tương tự Slice của Go)

→ Do độ trễ và đồng bộ hóa nên out-of-order xảy ra thường xuyên. Nếu trong cùng một phân vùng thì có thể sắp xếp lại khi lưu thông qua buffering; nếu ở phân vùng khác thì có thể thêm vào phía sau phân vùng trước đó thay vì head

→ Lưu đúng cùng dữ liệu với dữ liệu thực sự được ghi vào WAL để có thể khôi phục ngay cả khi có lỗi

• Phân vùng trên đĩa

→ Mỗi phân vùng lưu metadata và dữ liệu thực đã nén trong một thư mục duy nhất (phiên bản thu gọn của Prometheus V3 Storage)

→ Định dạng dữ liệu memory-mapped (có thể được kernel cache bằng mmap)

→ Metadata dùng định dạng JSON để tạo chỉ mục

• Phần mã hóa dữ liệu được biểu diễn bằng cặp timestamp và value sử dụng phương pháp mã hóa được đề xuất trong bài báo Gorilla của Facebook

→ Timestamp và value được mã hóa bằng các phương pháp khác nhau

→ timestamp là giá trị unsigned 64-bit integer và sử dụng mã hóa Delta-of-delta

→ Mã hóa Delta: chỉ ghi lại phần chênh lệch giữa giá trị trước đó và giá trị hiện tại

→ Mã hóa Delta-of-Delta: thông thường dữ liệu phát sinh theo các thời điểm nhất định nên chỉ ghi lại delta của delta

→ Vì được mã hóa với độ dài biến thiên nên Delta-of-Delta sử dụng ít không gian nhất

→ values là giá trị signed 64-bit floating-point và sử dụng mã hóa XOR

→ Giá trị đầu tiên được lưu nguyên trạng

→ XOR với giá trị tiếp theo, nếu bằng 0 thì giống giá trị trước nên chỉ lưu một bit 0

→ Nếu không phải 0 thì tính toán dựa trên các bit khác nhau (Meaningful Bit)

→ Tính số lượng số 0 ở đầu/cuối; nếu số lượng số 0 giống nhau thì chỉ lưu số 0 và các bit có ý nghĩa, nếu khác thì lưu số lượng leading zero, số lượng Meaningful Bit và chính các bit đó