View profile

#201- Quy trình xử lý 400 tỷ events tại Twitter

Grokking Vietnam
Grokking Vietnam
Trong số này chúng ta cùng tìm hiểu về:
  • Quy trình xử lý hàng tỉ event tại Twitter.
  • Lỗ hổng Log4j.
  • Khái niệm “Quorum” trong các hệ thsoong phân tán.
  • Kỹ thuật HyperLogLog.
  • Lời giải của bài toán “Number of Closed Islands”.

Những bài viết hay
Processing billions of events in real time at Twitter
A Log4J Vulnerability Has Set the Internet 'On Fire'
Góc Distributed System
Trong tuần trước góc DS gửi tới bạn một vấn đề là Read-after-write consistency trong đó khi client thực hiện write vào hệ thống, nó kì vọng sẽ read được nội dung đó ngay mà không cần chờ sau một khoảng thời gian. Có một số giải pháp đưa ra trong kì trước nhưng không xử lý được triệt để vấn đề này. Kì này góc DS giới thiệu một cách tiếp cận cho vấn đề này là Quorum. Quorum trong hệ thống phân tán được định nghĩa là số lượng tối thiểu các node xử lý được một request (read hoặc write) để hệ thống xác định việc xử lý đó là thành công. Trong bài toán read-after-write consistency, client sẽ đồng thời gửi request tới toàn bộ các node, nếu nó nhận được kết quả thành công của số lượng quorum node, request đó được xác định là thành công. Cụ thể, gọi số node là N.
  • Read quorum: client read thành công giá trị từ r node.
  • Write quorum: client write thành công giá trị vào w node.
Để đảm bảo read-after-write consistency, điều kiện cần đạt được là: r + w > N. Nói cách khác, tập node xử lý thành công write request và tập node xử lý thành công read request cần có ít nhất một phần tử giao nhau.
Tuy nhiên, read request có thể xảy ra trường hợp read phải dữ liệu cũ. Cách khắc phục là timestamp-based read repair, trong đó server đính kèm timestamp trong response trả về. Từ đó client có thể chọn kết quả có timestamp lớn hơn. Đồng thời client có thể chủ động repair dữ liệu cũ bằng một write request trực tiếp tới node trả về dữ liệu cũ.
Quorum được áp dụng phổ biến trong các hệ thống leaderless, tức là không sử dụng leader duy nhất xử lý write request, ví dụ như Cassandra hay Spanner.
Góc Database
Hãy hình dung bạn cần xây dựng một bộ đếm số khách hàng viếng thăm website của bạn, bạn sẽ xây dựng như thế nào? Lưu ý là nếu cùng một khách hàng (cùng một browser) vào website nhiều lần thì bộ đếm cũng chỉ tính 1 lượt truy cập. Dạng bài toán này hay được gọi là bài toán Count-Distinct hoặc Cardinality Estimation.
Một giải pháp đơn giản đối với nhóm bài toán này đó là đối với mỗi client (browser) bạn sẽ sinh ra một client_id, và phía server có thể dùng hash-map để lưu tất cả các client_id đó. Bộ đếm sẽ chỉ tăng nếu client_id vừa nhận chưa tồn tại trong hash-map. Với giải pháp này, chi phí thời gian sẽ là O(1) và chi phí không gian sẽ là O(N). Giả sử bạn có 100 triệu client_id, mỗi id tốn 4 bytes thì bạn sẽ tốn 400 Megabytes bộ nhớ chỉ để duy trì một bộ đếm như thế này (chưa tính chi phí memory để duy trì hash-map). 
Bên cạnh một cách giải có độ chính xác tuyệt đối nhưng tốn nhiều memory như trên thì nhóm bài toán này có một số cách tiếp cận phổ biến hơn đó là tìm cách hy sinh tính chính xác (accuracy) để bù lại giảm chi phí thời gian và không gian. Một số kỹ thuật đã được phát triển theo hướng này như: MinHash, LogLog, HyperLogLog, SetSketch, HyperMinHash, … trong đó thông dụng nhất là HyperLogLog.
Là một trong các kỹ thuật phổ biến vì dễ hiện thực, HyperLogLog đang được sử dụng trong nhiều database như Oracle, MySQL, Redis, … Khi sử dụng HyperLogLog, bạn có thể chỉ cần một vùng nhớ vài KB để ước tính kích thước của một tập hợp có 400 triệu phần tử với độ chính xác có thể đạt đến 2-5% tùy cách lựa chọn thông số cấu hình.
Trong mục Góc Database kỳ này mời các bạn cùng tìm hiểu cách HyperLogLog vận hành thông qua clip này. Ngoài ra, để hiểu rõ hơn tại sao HyperLogLog có thể đạt được độ hiệu quả như thế bạn có thể tham khảo paper gốc (kèm các chứng minh toán học).
Góc Lập Trình
Đề tuần này: Maximal Square
Lời giải tuần trước:
Lời giải: Nếu bạn đọc đã từng giải bài tương tự như Number of Islands, ta có thể nhận ra ngay cách tiếp cận là sử dụng BFS hoặc DFS. Trong bài này, ta phải đếm số lượng các đảo được bao quanh bởi ô “1”, vì vậy nếu đảo nối với ô “0” ở các cạnh viền ta cần loại bỏ những đảo này.
Ta có thể tiếp cận theo 2 bước như sau:
1. Thực hiện BFS, hoặc DFS, đánh dấu tất cả những đảo kết nối với ô “0” ở cạnh viền là bất hợp lệ
2. Thực hiện BFS, hoặc DFS giống như bài Number of Islands để đếm số lượng đảo
Để dễ dàng thực hiện đếm đảo ở bước 2, ở bước 1 ta có thể đánh dấu những đảo bất hợp lệ bằng cách đổi giá trị của chúng thành “1” (hoặc một số bất kì khác “0”).
Giải thuật được thực hiện tại đây: https://pastebin.com/7xMpt635
Độ phức tạp của giải thuật Time Complexity là O(m*n) với m, n là số lượng hàng, cột của ma trận. Space complexity là O(1).
Tech Talks
Code & Tools
  • avrohugger: Schema-to-case-class code generation for working with Avro in Scala.
  • Cats-parse: A parser combinators library for Scala
Góc Sponsors
ENGINEERING RECRUITMENT FROM GRAB
Grab is Southeast Asia’s leading superapp, providing everyday services such as mobility, deliveries (food, packages, groceries), mobile payment and financial services to millions of Southeast Asians. At Grab, we believe that talent is the heart of the company. Therefore, we strive to create a wonderful working environment to optimize the potential of our Grabbers to achieve our common mission: drive Southeast Asia forward by creating economic empowerment for everyone.
Why you will love working at Grab:
  • MacBook and 24-inches-monitor are provided.
  • Attractive salary and performance bonus.
  • Extra Medical Insurance from 1st joined date.
  • 14 days Annual leaves + 5 days of other leaves
  • GrabFlex allowance (up to 4.500.000 VND per month) for Family’s vacation, Education, Gym, Learning, etc…
  • GrabLove as vouchers for using Grab’s services.
  • Relocation opportunities to Regional or other countries.
  • Online Learning System & Offline Training courses are provided.
  • Opportunity to work, learn & grow with world-class professional engineers.
  • Opportunity to work for South East Asian Tech Decacorn.
  • Working day: Monday - Friday.
Join our Squad team today to drive Southeast Asia forward!
Check out our open positions at https://grab.careers/jobs/
Apply directly to ta.vn@grab.com as: Full Name_Applied position_Grokking
Quotes
“Fix the cause, not the symptom.” – Steve Maguire
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

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Viet Nam