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

Jul 19, 2021

Những bài viết hay

Implementing memory management with Golang’s garbage collector — hub.packtpub.com

Garbage collection là quá tình giải phóng không gian memory mà chương trình không sửa dụng nữa, giúp tận dụng lại nguồn tài nguyên đó và hạn chế rò rĩ memory. Garbage Collector trong Golang có tính concurrent, xảy ra song song với chương trình chính, có tính non-compacting, non-generational và dựa trên thuật toán tricolor mark-and-sweep.

Nguyên tắc cơ bản của thuật toán tricolor mark-and-sweep là chia các object trong heap thành 3 tập hợp khác nhau tuỳ theo màu: trắng, xám, đen. Object màu trắng sẽ bị xoá ở cuối chu kì GC. Object màu đen được đảm bảo không có pointer nào tới các object màu trắng, ngược lại object trắng có thể có pointer đến object đen. Object xám có thể có hoặc không có pointer đến object trắng .

Khi quá trình GC bắt đầu, tất cả object được tô màu trắng. Sau đó, GC truy cập vào các root object và tô chúng thành màu xám. Root object là các variable trong ứng dụng, có thể được truy cập trực tiếp, gồm các global variable và những thứ khác trong stack.

Sau đó, GC chọn 1 object màu xám, tô thành màu đen và bắt đầu xem object này có pointer đến object trắng nào hay không, nếu có thì object trắng đó sẽ được tô màu xám. Quá trình này lặp lại cho đến khi không còn object nào màu xám. Lúc đó các object màu trắng được đảm bảo là không có pointer nào trỏ đến và được GC quét sạch.

Để hiểu rõ hơn chi tiết thuật toán tricolor mark-and-sweep, cũng như hiểu thêm về Golang Garbage Collector, mời bạn tham khảo bài viết chi tiết sau đây

7 Database Concepts You Should Know About

Cơ sở dữ liệu là xương sống của các ứng dụng. Khi bạn càng tìm hiểu về cách hoạt động của database, bạn sẽ càng nâng cao khả năng sử dụng, thiết kế và khắc phụ các sự cố liên quan đến database.

Qua bài viết, tác giả có đề cập đến 7 concepts mà chúng ta nên hiểu hơn về database:

Database lưu trữ transactions chứ không phải là state. Cốt lõi của database chỉ là các log files. Từ log files, một database có thể xây dựng lại tables, databases, schemas, ... Nhưng có một lưu ý quan trọng là sau khi một transaction được committed or rolled back, nó sẽ bị xóa khỏi log.
Lựa chọn đúng một database không phải là một việc đơn giản. Mỗi ứng dụng có sự khác biệt về kiến trúc, traffic, cách thức truy vấn và sử dụng dữ liệu. Có rất nhiều loại databases phục vụ các nhu cầu khác nhiều. Vì vậy, chọn được đúng database phù hợp với đặc thù của ứng dụng là rất quan trọng, đòi hỏi nhiều kinh nghiệm và sự am hiểu về nhu cầu truy vấn và cấu trúc dữ liệu.
Chuyển sang sử dụng một database phù hợp với business còn khó hơn. Đôi khi bạn không có sự lựa chọn và cơ sở dữ liệu đã được chọn cho bạn. Sau một thời gian sử dụng, một database khác được xác định là đáp ứng được nhiều nhu cầu của dự án hơn. Tuy nhiên, việc migration sang một database khác luôn thực sự phức tạp.
NoSQL không thay thế SQL, chúng bổ trợ cho nhau. Các cuộc tranh luận về việc sử dụng SQL hay NoSQL có thể sẽ diễn ra mãi mãi. Nhưng thực tế SQL và NoSQL không thay thế cho nhau, mà được sử dụng vào các mục đích truy vấn khác nhau để có thể đạt được hiệu quả cao nhất.
Scaling một database luôn có nhiều khó khăn. Scale một database có thể là vertically (tăng CPU, RAM) hay horizontally (thêm nhiều replica). Tuy nhiên có những vấn đề khác cần quan tâm như consistency, availability, partitioning (CAP) hay đơn giản là giới hạn/chi phí của cấu hình máy. Chúng ta chỉ có thể đạt được 2 trong 3 yếu tố của CAP. Vì vậy, tùy vào mục đích sử dụng, chúng ta có thể có các scaling strategy khác nhau.
Indexes không phải là magic. Khi chỉ xử lý một lượng nhỏ số indexes cho một table, sự tác động thường là không đáng kể. Nhưng khi số indexes nhiều hơn, performance sẽ bị ảnh hưởng khi mỗi write vào bảng sẽ cần update toàn bộ indexes.
Mỗi khi một thứ gì đó tương tác với database, nó sẽ sử dụng một cấu trúc được gọi là transaction. Điều này nghe có vẻ không phải là vấn đề lớn, nhưng nó có tác động đến hiệu suất và hoạt động của database, đặc biệt là đối với những database tuân thủ ACID.

Using parsers in practice

Đối với một dự án của chúng tôi, chúng tôi đã phải tạo ra một ngôn ngữ mới thay vì sử dụng một số serialization format. Ngôn ngữ mới này có thể được sử dụng bên trong các ngôn ngữ khác nhau (đặc biệt là Kotlin và Haskell). Phát triển ngôn ngữ mới của riêng bạn cũng có nghĩa là sẽ phải viết một trình phân tích cú pháp cho nó (parser). Tiếp theo đó là chia sẻ ngữ pháp (grammar) của ngôn ngữ đó. Và quan trọng hơn là làm sao để chứng minh các ngôn ngữ khác nhau (ví dụ như: Kotlin, Haskel) đều có thể sử dụng grammar của ngôn ngữ mới này một cách thống nhất. Bài viết này sẽ nói về hành trình phân tích, nghiên cứu cũng như nhưng bài học mà chúng tôi thu được trong quá trình này. Trong bài viết tác giả sẽ đi sâu và phân tích những phần sau:

1) Về quyết định tạo ra ngôn ngữ mới: Trước khi đi sâu vào phần kỹ thuật tác giả nêu ra một số lý do tại sao họ cần phát triển một ngôn ngữ mới mà không tận dụng các ngôn ngữ sẵn có như sau: 

Họ cần một ngôn ngữ có khả năng khai báo biến, và sử dụng các biến đó tương tự như cách chúng ta dùng arguments trong functions.
Extension của các serialization format (như JsonLogic) thường quá dài dòng và rất khó để cho developers đọc hiểu.
Một số ngôn ngữ khác như họ LISP hoặc Racket support rất tốt cho việc viết một ngôn ngữ mới nhưng việc chia sẻ ngôn ngữ mới là không dễ dàng.

2) Về việc phát triển cú pháp (grammar): Sau khi quyết định xong sự tồn tại của ngôn ngữ mới, việc tiếp theo là tìm cách mô tả grammar của ngôn ngữ đó và tạo ra trình phân tích cú pháp (parser) tương ứng. Tác giả đã chọn ANTLR - ANother Tool for Language Recognition - bởi vì sự phổ biến trên JVM cũng như các nền tàng khác. ANTLR thuộc về trường phái truyền thống với việc chia grammar thành hai phần lexer (hoặc tokenizer) và parser. Lexer có vai trò phát hiện keyword, hằng số, biến số; parser có nhiệm vụ mô tả cách mà các thành phần được phát hiện bởi lexer phối hợp với nhau. Tương ứng với ngôn ngữ nói, ta có thể hiểu như sau: lexer nhận ra từ, còn parser sẽ nhận ra câu.

3) Sự đơn giản của ANTLR: ở đây tác giả trình bày sự dễ dàng của việc tích hợp ANTLR parser trên nền tàng JVM.

4) Về việc kiểm tra và debug grammar: Một vấn đề thường gặp khi phát triển một ngôn ngữ mới là sự phức tạp và dài dòng chạy một test case đơn giản. Trong vấn đề này tác giả giới thiệu một plugin cho Visual Studio Code mà nó đã giúp tác giả rất nhiều trong việc debug quá trình parsing.

5) Haskell và quy tắc của riêng nó: Bước tiếp theo là tạo parser cho Haskell, nhưng không may ANTLR trên Haskell lại không tương thích với ANTLR trên JVM. Vì vậy tác giả đã phải tự viết parser trên haskell bằng Parser combinator

6) Kiểm tra sự thống nhất của ngôn ngữ: Để kiểm tra sự thống nhất của ngôn ngữ mới được tạo ra, tác giả đã sử dụng một công cụ được gọi là Grammarinator. Grammarinator có thể coi như sự đảo ngược của parser: nó nhận một tập grammar và sẽ tạo ra một số lượng lớn string mà thỏa mãn những grammar đó. Và bước cuối cùng là đưa những string mới tạo được vào parser của JVM và Haskell. Hai parser này đều phải có thể xử lý những string này một cách thống nhất.

7) Kết luận: Việc phát triển một ngôn ngữ mới có vẻ khá đáng sợ, nhưng với những công cụ phù hợp, bạn có thể làm được nó một cách không quá khó khăn.

Góc Distributed System

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

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 và 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 và 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)

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:

KMS Jobs with 1-month joining bonus

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.

― Donald E. Knuth