View profile

#180 - Bài toán đồng bộ thời gian trong CockroachDB

Revue
 
 

Grokking Newsletter

July 19 · Issue #181 · View online

Tuyển tập những bài viết hay cùng sự kiện bổ ích dành cho kĩ sư phần mềm tại Việt Nam.


Những bài viết hay
Implementing memory management with Golang’s garbage collector Implementing memory management with Golang’s garbage collector
7 Database Concepts You Should Know About
Using parsers in practice
Góc Distributed System
Thiết kế của CockroachDB kế thừa từ thiết kế của Google Spanner. Trong khía cạnh đồng bộ thời gian để đảm bảo tính consistency, Spanner sử dụng hệ thống Google TrueTime bao gồm đồng hồ nguyên tử (Atomic Clock) và đồng hồ GPS giúp các nodes đồng bộ thời gian với nhau một cách “chính xác”. Tuy nhiên, CockroachDB là phần mềm mã nguồn mở với mục đích có thể chạy trên phần cứng phổ thông nên nó không thể có sự hỗ trợ của Atomic Clock. Vậy thì CockroachDB đã xử lý bài toán đồng bộ thời gian như thế nào ? Mời bạn tìm hiểu ở bài viết này
Phần đầu của bài viết, tác giả giải thích các khái niệm trong consistency liên quan tới linerizability và serializability thông qua các ví dụ trực quan và dễ hiểu, cũng như tính quan trọng của hai yếu tố này đối với distributed database. Bên cạnh đó, tác giả bài viết cũng đề cập tới cận trên (upper bound) trong sự sai lệch thời gian của hệ thống Google TrueTime là 7ms, trong khi đối với dịch vụ NTP độ sai lệch này là từ 100ms tới 250ms. Có nghĩa là kể cả Spanner cũng không đạt được sự đồng bộ thời gian tuyệt đối. Spanner đã khắc phục sai lệch 7ms này một cách khá đơn giản: các node trong Spanner sẽ thêm khoảng delay 7ms sau khi transaction được commit thành công rồi nó mới announce kết quả commit.
Có một điểm rất quan trọng để đảm bảo tính linerizability là thời gian ghi nhận trên đồng hồ của node trong hệ thống cần phải luôn lớn hơn hoặc bằng timestamp của transaction mới nhất được commit. Hệ quả là timestamp được chọn cho 1 transaction mới cần phải lớn hơn hoặc bằng timestamp lớn nhất của các transaction đã commit trên toàn bộ nodes trong hệ thống. Tuy nhiên, trong môi trường phân tán và các transaction read/write có thể thực hiện song song và không đoán được (non-deterministic), yếu tố này khó để thực hiện trên một node. Chẳng lẽ một node lại phải đợi node chậm nhất trong hệ thống response trước khi thực hiện một transaction mới, như vậy thì rất không hiệu quả. Cách cockroachDB xử lý vấn đề này cũng tương đối đơn giản như cách tiếp cận của Spanner:
“Spanner luôn thêm 7ms wait sau khi commit transaction, CockroachDB thỉnh thoảng sẽ thực hiện retry read”
Cụ thể của việc retry read và cách xác định timestamp cho một transaction mới trên CockroachDB như thế nào, mời bạn đọc chi tiết trong bài viết nhé.
Góc Database
Đối với các loại key-value database sử dụng hard-disk làm main storage thì bài toán memberships checking là một bài toán quan trọng. Giả sử trong database của bạn có 1 nghìn phần tử đánh số từ A1 đến A1000, trong đó có khoảng 100 phần tử thường được cache trên memory, còn lại sẽ được ghi ở đĩa. Tuy nhiên do đặc thù ứng dụng của bạn, nhiều client lại gửi lệnh đọc các key không tồn tại trên đĩa dẫn đến nhiều lệnh đọc đĩa sẽ được tạo ra, hệ thống sẽ tốn tài nguyên để thực hiện những tác vụ vô ích (tìm đọc thứ không tồn tại).
Giả sử có một cách nào đó để xác nhận liệu một key có tồn tại hay không trước khi đọc xuống đĩa thì cách này sẽ giúp hệ thống tiết kiệm được nhiều tài nguyên.
Giải pháp đơn giản nhất đó là đem các key lên lưu trên memory. Cách này sẽ có độ chính xác 100% và tất cả những lệnh đọc không cần thiết sẽ bị loại bỏ. Tuy nhiên cái giá phải trả là bộ nhớ phải bỏ ra cũng nhiều tương ứng với tất cả các key đang được lưu trữ.
Một cách tiếp cận khác cân bằng hơn đó là tạo ra các cấu trúc dữ liệu giúp lưu và “nén” có thất thoát thông tin của các key. Các cấu trúc dữ liệu này thường có các đặc tính được trông đợi như sau:
  • Lượng dữ liệu sử dụng để tổ chức cấu trúc dữ liệu trên memory sẽ ít hơn nhiều so với việc lưu toàn bộ thông tin keys lên memory.
  • Nếu một phần tử không thuộc về tồn tại trong database, cấu trúc dữ liệu này sẽ có khả năng trả về kết quả chính xác tuyệt đối.
  • Nếu một phần tử có tồn tại trong database, CTDL này có thể sẽ trả về kết qủa chính xác tương đối. Tức là có khi CTDL trả về kết quả là có tồn tại, nhưng khi đọc xuống đĩa thì hoá ra lại không có.
Bloom Filter, Cuckoo Filter, Quotient Filter là các loại cấu trúc dữ liệu loại này. Trong số newsletter kỳ này, mời bạn đọc cùng tìm hiểu về Cuckoo Filter, một CTDL dùng hash table, sử dụng cơ chế Cuckoo hashing để nén danh sách các khoá.
Góc Lập Trình
Đề ra tuần này:
Cho một string s chỉ chứa ba loại ký tự sau: '('')' và '*', Trả về kết quả true nếu s hợp lệ.
Tuân theo các luật sau để kiểm tra s có hợp lệ hay không:
  • Bất kỳ một dấu ngoặc đơn trái '(' nào cũng phải có một dấu ngoặc đơn phải ')' tương ứng.
  • Bất kỳ một dấu ngoặc phải ')' nào cũng phải có một dấu ngoặc đơn trái '('tương ứng.
  • Dấu ngoặc đơn trái '(' phải đứng trước dấu ngoặc đơn phải ')'.
  • Dấu '*' có thể được coi như một dấu ngoặc đơn trái, hoặc dấu ngoặc đơn phải, hoặc một chuỗi rỗng "".
Các bạn có thể làm thử tại đây.
Lời giải tuần trước:
Chúng ta có thể thử với giải pháp Brute Force, nhưng sẽ đòi hỏi Time Complexity ~ O(N*K). Lời giải sau bằng Kotlin tương đối ngắn gọn chỉ với 2 dòng code.
fun solution(nums: List<Int>, k: Int): List<Int> =
nums.windowed(k).map { it.max()!! }
Một giải pháp sử dụng heap hoặc quy hoạch động sẽ cho ta lời giải tối ưu hơn.
Chúng ta tiếp cận bài toán với tư tưởng quy hoạch động như sau:
  • Chia mảng arr ban đầu với N phần tử thành từng block k phần tử liên tiếp nhau.
  • Tạo hai array LEFT RIGHT có cùng kích thước với arr.
  • LEFT[j] sẽ chứa giá trị lớn nhất tính từ điểm bắt đầu của block cho tới vị trí index j, theo chiều từ trái qua phải. Với mảng RIGHT ta cũng làm tương tự, nhưng với chiều từ phải qua trái.
  • Sau khi tạo được hai array LEFT RIGHT, vậy lúc này, giá trị maximum của một sliding window của mảng arr tại index [i, i+k-1] sẽ được tính bằngmax(RIGHT [i], LEFT[i + k - 1])
Các bạn có thể thử sức tại đây.
Time Complexity và Space Complexity đều là O(N)
Time Complexity và Space Complexity đều là O(N)
Code & Tools
This Week Sponsors
KMS Technology là một trong những công ty dịch vụ phần mềm hàng đầu, với 12 năm hoạt động và phát triển trên thị trường Châu Âu, Mỹ, và khu vực APAC; hiện có 05 văn phòng tại Atlanta (Mỹ), TP.HCM và Đà Nẵng.
Số lượng KMSer hiện tại đã lên đến 1000+ và vẫn đang trên đà phát triển, mở rộng cho nhiều dự án lớn, quy mô toàn cầu với các chiến dịch tuyển dụng hấp dẫn, phúc lợi ấn tượng.
Nếu bạn đang tìm kiếm một cơ hội mới, thì đây là thời điểm khó bỏ lỡ với nhiều vị trí hấp dẫn cùng 1 tháng “joining bonus” dành cho ứng viên ứng tuyển và gia nhập trước 31/8/2021.
Khám phá ngay tại đây:
Quotes
The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.
Did you enjoy this issue?
If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Powered by Revue
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam