View profile

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

Revue
 
 

Grokking Newsletter

June 21 · Issue #177 · 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
Open-sourcing a 10x reduction in Apache Cassandra tail latency | by Instagram Engineering Open-sourcing a 10x reduction in Apache Cassandra tail latency | by Instagram Engineering
Post-Mortem / Root Cause Analysis (April 2021) - Codecov
Bulldozer: Batch Data Moving from Data Warehouse to Online Key-Value Stores Bulldozer: Batch Data Moving from Data Warehouse to Online Key-Value Stores
Góc Distributed System
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é.
PostgreSQL Optimizer Methodology (Robert Haas)
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é!
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
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