View profile

#174 - Xử lý bài toán reliable reprocessing với kafka tại Uber

Grokking Vietnam
Grokking Vietnam
Những bài viết hay
Building and Scaling Data Lineage at Netflix to Improve Data Infrastructure Reliability, and Efficiency
Góc Distributed System
Trong các hệ thống phân tán, vấn đề retry hay các vấn đề về network error, server crash là không thể tránh khỏi. Uber sử dụng Kafka cho hệ thống event messaging của họ. Cùng xem Uber xử lý bài toán reprocessing trong Kafka như thế nào?
Bài toán đặt ra là khi một service ở phía consumer có hiện tượng high latency, service phía publisher có thể sẽ thực hiện retry (kèm backoff) hành động publish event vào kafka cho tới khi có phản hồi thành công hoặc đạt điều kiện dừng. Vấn đề với cách tiếp cận retry đơn giản như vậy là:
  • Làm tắc nghẽn cơ chế batch processing của Kafka: xảy ra khi có quá nhiều retried message trong Kafka và consumer liên tục consume retried message
  • Metadata của các bản tin retry có thể gây phiền phức cho việc lập trình như lấy timestamp hay đếm số lần retry
Uber xử lý bài toán này thông qua việc sử dụng Dead-letter queue (DLQ), tức là xây dựng các retry queues (ở trên các topic khác nhau) để lưu trữ các event lỗi, phục vụ bài toán retry. Cụ thể như sau:
  1. Khi consumer không thể response thành công một request event X nhận từ queue, sau số lần retry nhất định (config sẵn), consumer sẽ publish event X đó qua 1 retry topic tương ứng để reprocessing về sau. Đồng thời publish offset của X đó vào một topic cố định khác để đánh dấu là event X đã bị retry nhiều lần. Rồi consumer tiếp tục thực hiện với các event khác
  2. Các consumer khác được thiết lập từ trước sẽ consume từ các retry topic để lấy event (X) cho việc thực hiện lại request (reprocessing). Nếu còn bị lỗi thì lại lặp lại thao tác như bước 1
  3. Sau một số lần reprocessing không thành công, event X sẽ được đẩy vào Dead-letter topic
  4. Các event trong dead-letter được thực hiện lại bằng cách được gửi trở lại topic nguồn
Cứ như vậy các event lỗi sẽ dần được retry. Cách làm này không những giúp Uber giải quyết được vấn đề tắc nghẽn trong queue mà còn có một số điểm lợi khác:
  • Tránh việc consuming bị tắc khi cứ phải xử lý message retry lỗi liên tục, thay vào đó consumer tiếp tục xử lý các message khác và quay lại xử lý message lỗi sau. Nguyên nhân vì khi một message bị delay khi xử lý sẽ ảnh hưởng tới toàn bộ message khác trên cùng một partition
  • Việc tách ra nhiều topic cho retry message (thay vì chỉ một retry topic) cũng có lợi hơn khi bản thân retry message vẫn tiếp tục bị delay trên retry topic
  • Dễ dàng cấu hình, tinh chỉnh cho các topic retry
  • Tăng khả năng observability
Và một số điểm lợi khác. Mời bạn đọc bài viết cụ thể ở đây. Để hiểu thêm về DLQ trong Kafka, bạn tham khảo bài viết này
Góc Database
Monitoring là một nhu cầu quan trọng trong các hệ thống ngày nay. Việc liên tục phải theo dõi xem CPU của bạn đang ở mức nào, API này đang serve bao nhiêu QPS, tỉ lệ lỗi của API này là bao nhiêu, … là điều cần thiết để có thể đưa ra các cảnh bảo.
Tuy nhiên bạn có tự hỏi một hệ thống database dùng để lưu trữ dữ liệu tracking như vậy sẽ có những đặc tính gì, hay có những kỹ thuật gì đã được áp dụng để xây dựng nên nó?
Trong số kỳ này, mời các bạn tham khảo bài báo về Gorilla, một in-memory time series database được phát triển bởi Facebook nhằm phục vụ cho việc theo dõi traffic và performance của các hệ thống khác ở Facebook. Bài báo sẽ đề cập đến một vài kỹ thuật được sử dụng Timestamp Compression, Value Compression cũng như cấu trúc dữ liệu trên memory được dùng để tổ chức các dữ liệu này.
Góc Lập Trình
Đề ra tuần này:
Cho một cây nhị phân, hãy thiết kế thuật toán để tạo 1 list chứa tất cả các node của cây theo từng độ sâu. Nếu cây có độ sâu bằng n, thuật toán sẽ trả lại 1 list với n list con.
Input:
Output: [[1], [2,3], [4, 5, 6], [7, 8, 9, 10]]
Lời giải tuần trước:
Một phương án ta có thể nghĩ tới ngay đó là tính giá trị của một chiếc bánh theo tỉ lệ value/weight. Ví dụ với input cake_tuples = [ (1, 10), (5, 100)], ta thấy loại bánh thứ nhất có ratio là 10/1 = 10, loại thứ 2 có ratio là 100/5 = 20. Ta sẽ lần lượt lấy loại bánh thứ 2 nhét đầy vào túi, sau đó tới loại bánh thứ 1.
Tuy nhiên phương án này không phải lúc nào cũng cho ra kết quả tối ưu nhất. Giả sử với trường hợp cake_tuples = [ (3, 40), (5, 70) ], capacity = 9. Loại bánh thứ 2 có ratio lớn hơn loại thứ 1 (70/5 > 40/3), do đó với cách làm ở trên, ta sẽ ưu tiên loại bánh thứ 2 trước. Vậy với capacity = 9, ta sẽ cần 1 bánh loại 2 và 1 bánh loại 1, cho ta tổng giá trị là 110. Tuy nhiên đáp án chính xác sẽ là 3 bánh loại 1 với tổng giá trị là 120. Vậy cách tính value/weight sẽ không cho ta phương án tối ưu nhất. Ta có thể dùng quy hoạch động để giải bài toán này.
Chúng ta sẽ bắt đầu với việc chia nhỏ bài toán, bắt đầu bằng việc giả sử capacity = 1. Nếu capacity = 1, chúng ta chỉ cần duyệt qua tất cả loại bánh và chỉ quan tâm tới các loại bánh có weight = 1, chọn ra loại bánh nào có value lớn nhất. Ta tạm lưu giá trị value này là maxValueAtCapacity1.
Tiếp theo, tương tự nếu trường hợp capacity = 2. Ta cũng muốn tìm ra giá trị value lớn nhất và lưu vào maxValueAtCapacity2. Chúng ta cũng làm tương tự bằng cách duyệt lại toàn bộ loại bánh, và sẽ chỉ cần lưu ý tới các loại bánh có weight = 1 hoặc 2 (rõ ràng 1 chiếc bánh có trọng lượng lớn hơn 2 sẽ không để vừa túi).
  • Nếu bánh có weight = 2, ta chỉ cần kiểm tra value của loại bánh này có lớn hơn maxValueAtCapacity2 hay không để cập nhật lại giá trị maxValueAtCapacity2.
  • Nếu bánh có weight = 1, nếu ta bỏ 1 chiếc bánh có trọng lượng 1 vào túi thì ta cũng sẽ cần bỏ thêm 1 chiếc bánh khác có trọng lượng 1 vào để lấp đầy túi. Rõ ràng ta có thể sử dụng giá trị maxValueAtCapacity1 đã tính trước đó để có giá trị tối ưu và không cần phải xử lý lại. Do đó, ta sẽ so sánh với maxValueAtCapacity2 để tìm ra giá trị lớn nhất cho maxValueAtCapacity2.
Tới đây chắc bạn đọc đã có thể hình dung được một cách tổng quát, chúng ta có thể dùng maxValueAtCapacity1 để tính maxValuleAtCapacity2, thì cũng có thể dùng maxValueAtCapacity1 và maxValueAtCapacity2 để tính maxValueAtCapacity3. Để tránh việc phải tính lại, ta sẽ lưu các giá trị maxValueAtCapacity vào một mảng. Khi đó gía trị value sau cùng sẽ là maxValueAtCapacityK (capacity = k).
Độ phức tạp của bài toán là O(k*n) time complexity và O(k) space complexity, với k là trọng lượng tối đa chiếc túi mang được, n là số loại bánh ta có.
Nhận xét:
  • Đây là một bài toán tương đối kinh điển trong quy hoạch động. Tuy nhiên lời giải tối ưu cũng đòi hỏi độ phức tạp cao O(k*n) và sẽ cần nhiều thời gian hơn khi k hoặc n quá lớn. Lời giải ban đầu với giá trị ratio của value/weight có thể kém tối ưu hơn nhưng lại nhanh hơn với độ phức tạp O( n lg n) (Cần thực hiện thao tác sort). Trong thực tế, ta có thể tùy theo tình huống để lựa chọn phương án phù hợp. Không phải lúc nào lời giải tối ưu cũng sẽ là lời giải hiệu quả nhất (sẽ thế nào nếu tên trộm phải chạy đua với thời gian và kịp tẩu thoát trước khi bị phát hiện?)
  • Trong lời giải trên, chúng tôi vẫn chưa xử lý cho tình huống weight = 0 hoặc value = 0. Bên cạnh đó các bạn đọc có thể điều chỉnh lời giải trên để trả về số lượng chính xác của mỗi loại bánh ta mang được.
  • Ngoài ra, sẽ thế nào nếu thay vì có một kho vô tận, ta chỉ có một số lượng giới hạn các loại bánh? Có những loại bánh rất nặng hoặc rất kém giá trị và gần như không bao giờ nằm trong phương án tối ưu, vậy ta thể dùng ý tưởng này để xử lý không?
Hãy coi những câu hỏi trên như những bài tập nhỏ dành cho bạn đọc trong việc khám phá những bài tóan lập trình thú vị, và đừng quên chia sẻ với chúng tôi nhé.
Code & Tools
This Week Sponsors
KMS Technology luôn nằm trong Top các nơi làm việc lý tưởng trong ngành IT. Điều gì đang chờ đón bạn tại đây?
  • Nhiều phúc lợi không phải ở đâu cũng có (thử việc, bảo hiểm xã hội 100% lương; bảo hiểm sức khoẻ cao cấp cho KMSer ngay từ ngày đầu tiên, và cho người thân sau thử việc; linh động, thoải mái về thời gian và nơi làm việc, thưởng theo năng lực,…)
  • Gia nhập đội ngũ trẻ, giỏi, năng động trong các dự án lớn, quy mô toàn cầu
  • Nhiều cơ hội đào tạo, học tập, luân chuyển dự án, làm việc on-site
  • Văn hoá làm việc rõ ràng, tôn trọng, minh bạch
Vẫn còn nhiều điều có 1-0-2 tại KMS. Bạn hãy đích thân khám phá nhé!
Góc Tuyển Dụng
Quotes
The Analytical Engine has no pretensions whatever to originate any thing. It can do whatever we know how to order it to perform.
- Ada Lovelace
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

Ngoài ra các bạn có thể gửi feedback cho Grokking Newsletter team ở https://bit.ly/3k3Jdw5 hoặc đóng góp bài viết tại https://bit.ly/2XaBUtF

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.
Created with Revue by Twitter.
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam