#176 - TiKV đã cải thiện system read throughput chỉ với 26 LoC

Jun 21, 2021

Những bài viết hay

Open-sourcing a 10x reduction in Apache Cassandra tail latency | by Instagram Engineering — instagram-engineering.com

Cassandra được các đội ngũ kỹ sư ở Instagram bắt đầu sử dụng vào năm 2012 để thay thế cho Redis ở vài dự án như là phát hiện gian lận, instagram news feed, và inbox. Tuy nhiên, với vài dự án cần độ trễ thấp cho việc truy vấn dữ liệu thì các đội ngũ kỹ sư ở Instagram nhận thấy rằng Cassandra thường có latency spikes cho một vài trường hợp. Sau một quá trình điều tra thì họ thấy rằng Cassandra của họ thường tốn 1.5% tới 2.5% thời gian cho việc chạy JVM garbage collector. Và việc chạy GC thường xuyên sẽ xuất hiện các latency spikes nhiều hơn.

Do đó, vào năm 2018, các đội ngũ kỹ sư ở Instagram đã bắt đầu thử nghiệm việc dùng RocksDB cho storage engine của Cassandra. Tuy nhiên, do codebase của Cassandra khá là khó để sử dụng một storage engine ở ngoài nên việc kết nối với RocksDB trở nên thách thức hơn. Bài viết sau đây được Dikang Gu, một kỹ sư ở Instagram, nói về các vấn đề họ gặp phải khi tích hợp RocksDB cho Cassandra ở mảng storage engine. Đồng thời, bài viết cũng nói về các benchmarks họ đã thực hiện để so sánh sự cải thiện của RocksDB trên Cassandra từ 2.5% thời gian cho GC nói trên xuống còn 0.3%

Post-Mortem / Root Cause Analysis (April 2021) - Codecov

Vào đầu tháng 4 năm nay, các đội ngũ kỹ sư ở Codecov đã được báo về một lỗ hổng an ninh trong hệ thống của họ. Do đó, họ đã dồn nhiều công sức để ngăn chặn và sửa lỗ hổng này. Sau sự cố trên thì các đội ngũ kỹ sư ở Codecov đã rút ra được vài kinh nghiệm và bài học khá là bổ ích như là:

Software Distribution & Signing: Lỗ hổng an ninh kỳ này nói lên sự quan trọng trong việc cải thiện và giám sát chặt cách phân bố và sign phần mềm. Mặc dù, bài toán này đã có rất nhiều giải pháp, nhưng nếu chúng ta không hiểu rõ và dùng một cách đúng đắn thì các lỗ hổng an ninh vẫn có thể xảy ra một cách dễ dàng
Key Management: Các thách thức về việc chuyển đổi keys hay quản lý keys vẫn còn tồn tại trong ngành phần mềm. Mặc dù đã có nhiều giải pháp để giúp việc lưu trữ và phân bố keys, nhưng chúng ta hiện tại lại có ít giải pháp để theo dõi tất cả metadata liên quan tới một key hay một secret. Lỗ hổng an ninh kỳ này của Codecov có liên quan tới vấn đề này, do đó đội ngũ kỹ sư ở Codecov đã quyết định xây dựng một hệ thống riêng để giải quyết

Bài viết sau đây được tác giả nói cụ thể hơn về lỗ hổng an ninh Codecov gặp phải và cách họ đã khắc phục và cải thiện hệ thống của họ như thế nào

Bulldozer: Batch Data Moving from Data Warehouse to Online Key-Value Stores — netflixtechblog.com

Cũng giống như những công ty phần mềm khác, các data scientists và engineers ở Netflix thường viết ETL jobs hay data pipelines ở trong data warehouse của họ dựa trên Apache Spark hay Apache Presto để phân tích dữ liệu thu thập được từ người dùng hay là từ hệ thống. Tuy nhiên, thường thì sẽ có một vài dịch vụ cần phải truy cập các dữ liệu này với yêu cầu là phải có độ trễ thấp. Do data warehouse thường không được thiết kế cho các trường hợp này, đặc biệt là khi cần truy vấn dữ liệu một cách nhanh chóng.

Do đó, các kỹ sư ở Netflix đã lập ra Bulldozer, một hệ thống tự phục vụ có thể giúp các kỹ sư thiết lập việc chuyển dữ liệu từ data warehouse sang các key-value stores được hỗ trợ ở Netflix. Nhìn chung về mặt kiến trúc hệ thống thì Bulldozer cũng không phải quá phức tạp. Tuy nhiên, hai bài toán mà Bulldozer cần giải quyết cặn kẽ ở đây là về mặt mô hình dữ liệu khi cần phải chuyển đổi schema từ các bảng dữ liệu ở data warehouse qua key-value stores và về cách quản lý nhiều phiên bản dữ liệu từ data warehouse sang key-value stores. Bài viết sau đây được các đội ngũ kỹ sư ở Netflix giới thiệu về Bulldozer và đồng thời nói cụ thể hơn cách họ đã giải các bài toán Bulldozer gặp phải như thế nào.

Góc Distributed System

TiKV đã cải thiện system read throughput chỉ với 26 LoC

TiKV là phần mềm mã nguồn mở về distributed transactional key-value database và là một trong các dự án được chứng nhận "graduated" bởi CNCF. Bài viết này mời bạn tìm hiểu một bài toán cải thiện hiệu năng của TiKV chỉ với 26 dòng code.

Đầu tiên bạn cần biết TiKV lưu dữ liệu trên các đơn vị cơ bản được gọi là Region. Nhiều replicas của Region tạo thành một Raft Group, sử dụng thuật toán Raft để làm replication. Khi có quá nhiều request read gọi tới một Region Leader, nó có thể bị nghẽn. TiKV đã giới thiệu tính năng Follower Read giúp cải thiện khả năng truy cập của TiKV client và giảm tải cho Raft leader bằng cách: Follower Read cho phép đọc dữ liệu trên các Follower nodes.

Tính năng Follower Read được implement chỉ trong 26 dòng code để đạt điều kiện sau: Cho phép bất kì Follower replica nào trong Region Group có thể serve read request mà vẫn đảm bảo strongly consistent reads và linearizability

Follower Read được viết dựa vào thuật toán ReadIndex, với một cải tiến nhỏ về timeout (và được TiKV gọi là LeaseRead). Cụ thể thuật toán ReadIndex như thế nào?

Vấn đề linearizability trong Raft:

Trong Raft, ta không thể đọc dữ liệu trực tiếp từ replica bởi vì Raft là quorum-based. Nghĩa là để commit một log, ta không cần phải ghi dữ liệu vào tất cả các replicas, mà thay vào đó chỉ cần ghi vào số đông (majority) các replicas là đã được công nhận. Như vậy, dữ liệu trên một node có thể sẽ bị sai sót so với các node khác. Hoặc trong trường hợp network bị partition, sẽ có nhiều hơn 1 leader trong mạng, dữ liệu các node cũng sẽ khác nhau.

ReadIndex là để giải quyết vấn đề này. Xuất phát từ việc old leader trong Raft không thể biết được liệu nó có còn là leader mới nhất hay không ? ReadIndex cho phép leader xác định liệu nó có còn là leader không, cụ thể như sau:

Khi leader xử lý một read request, nó lưu lại latest committed index ứng với request đó
Leader gửi heartbeat tới quorum (Theo raft protocol) để xác định leadership
Sau khi leader xác nhận trạng thái leader, nó sẽ gửi lại các follower thông tin latest index đề cập ở bước 1, rồi mới trả lời read request đó

Latest index này sẽ đảm bảo toàn bộ follower tuân theo. Phía followers, khi nhận request sẽ dựa vào ReadIndex để thực hiện hai bước:

Follower yêu cầu latest committed index của Leader.
Follower nhận được index, nó sẽ apply dữ liệu và trả kết quả cho request.

Tuy nhiên, do trong Raft việc apply dữ liệu là asynchonorous, do đó có thể xảy ra trường hợp Follower đã apply dữ liệu thành công nhưng Leader thì vẫn chưa. Bạn hãy đọc tiếp bài viết để có câu trả lời nhé. Bài viết cũng đề cập thêm vấn đề về latency, benchmarking và hướng cải tiến tiếp theo.

Góc Database

Optimizer là một thành phần quan trọng khi nói đến thiết kế của các Database thuộc họ SQL. Nhiệm vụ của Optimizer là phân tích giữa các query plan và lựa chọn ra chiến lược phù hợp nhất để thực thi câu query của bạn. Nghe có vẻ đơn giản nhưng để lựa chọn ra chiến lược phù hợp là một trong các bài toán mà đến thời điểm hiện tại vẫn còn được xem là khó.

Để hình dung về bài toán này, giả sử bạn có một câu query như sau

Gỉa sử mỗi lần join sẽ chỉ lấy hai bảng bất kỳ join lại với nhau, sau đó mới lấy kết quả join với bảng thứ ba, ... và lặp lại chu kỳ đến bảng thứ N. Với cách làm trên chúng ta đã có N! tổ hợp cách join. Vậy bộ Optimizer sẽ làm cách nào để biết nên thực hiện phép join nào trước, phép join nào sau?

Không chỉ vậy, đôi khi một câu query tưởng chừng đơn giản như SELECT * FROM foo WHERE a=1 ORDER BY b LIMIT 1 lại có thể trở thành một vấn đề lớn khi tập dữ liệu của a và b có nhiều trường hợp có thể xảy ra.

Góc Database kỳ này mời các bạn cùng nghe bài chia sẻ của anh Robert Haas để hiểu thêm về những thử thách gặp phải khi xác định các chiến lược cho bộ Optimizer của Postgres nhé.

Góc lập trình

Đề ra kỳ này

Cho một mảng các số nguyên không âm arr, bạn được đặt ở 1 vị trí start nằm trong mảng. Cách nhảy như sau: khi bạn ở tại một vị trí có index i, bạn có thể nhảy tới vị trí i+ arr[i] hoặc i - arr[i]. Kiểm tra xem bạn có thể nhảy tới bất kỳ index nào với giá trị 0 hay không? Lưu ý là bạn không thể nhảy ra khỏi ngoài mảng.

Ví dụ 1:

Input: arr = [4,2,3,0,3,1,2], start = 5

Output: true

Explanation:

Các cách có thể để nhảy tới vị trí index 3 với giá trị 0 là:

index 5 -> index 4 -> index 1 -> index 3

index 5 -> index 6 -> index 4 -> index 1 -> index 3

Lời giải tuần trước

Lời giải bài Jump Game II:

Giống những bài toán tìm đường, cách tiếp cận với giải thuật quay lui (backtracking) chắc chắn sẽ cho ta lời giải. Để tìm cách nhảy với số bước nhảy ít nhất, ta có thể sử dụng thuật toán quay lui, tìm tất cả những cách nhảy tới đích, kết quả sẽ là cách nhảy có số bước nhảy ít nhất. Tuy nhiên các làm này có time complexity khá lớn. Ta sẽ thử với tiếp cận bài toán với thuật toán tham lam (greedy).

Ví dụ:

input = [2, 3, 1, 1, 4]

index= [0, 1, 2, 3, 4]

start position = 0 Tại vị trí bắt đầu input[0] = 2, ta có 2 lựa chọn:

Nhảy 1 bước tới vị trí input[1] = 3
Nhảy 2 bước tới vị trí input[2] = 1

Mục tiêu của ta là tìm số bước nhảy ít nhất tới đích, vì vậy ta nên nhảy tới ô giúp ta có thể nhảy được xa nhất ở bước tiếp theo. Ở đây, input[1] = 3 sẽ giúp ta nhảy xa được xa hơn ở bước tiếp theo.

Tại mỗi ô ta nhảy tới, ta cần thực hiện nhảy tiếp, vì vậy ta sẽ tăng số bước nhảy lên 1.

Code & Tools

This Week Sponsors

"KMSer = làm hết sức + chơi hết mình"

Với hai tính cách trên, bạn sẽ bắt gặp con người KMS mỗi ngày trong những dự án lớn với nhiều thử thách, choàng vai nhau cùng học, cùng chia sẻ kiến thức, cùng dẫn dắt bạn mới, cùng nghiên cứu sáng kiến để đạt được mục tiêu chung.

Bạn sẽ bắt gặp người KMS nhuộm xanh các giải chạy bằng màu áo đặc trưng, đổ mồ hôi trong các câu lạc bộ thể thao (cầu lông, bóng bàn, bi lắc, đá bóng,...) hay đơn giản là vỗ vai, đập đùi trong một trận PES giờ nghỉ trưa hay sau giờ làm ngay tại văn phòng.

Bạn đã thấy hình ảnh mình là một KMSer sẽ như thế nào chưa?

Ứng tuyển và gia nhập KMS Technology trước ngày 31/8 để có cơ hội nhận ngay 01 tháng "joining bonus" nhé!

Senior Java Software Engineer (1-month joining bonus)
Senior Python Software Engineer (1-month joining bonus)
Fresher Java Software Engineer

Các vị trí khác tại KMS Technology Careers

Quotes

Before software can be reusable it first has to be usable.

– Ralph Johnson