#201- Quy trình xử lý 400 tỷ events tại Twitter
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 — blog.twitter.com
Với dữ liệu được tổng hợp từ nhiều cơ sở dữ liệu, hệ thống phân tán khác nhau như Hadoop, Kafka, Twitter Eventbus, GCS, BigQuery,... Ở Twitter, mỗi ngày, các kỹ sư trong nhóm Data Platform tại đây phải vận hành hệ thống xử lý lượng dữ liệu khổng lồ lên tới 400 tỷ events, với quy mô petabyte (PB) mỗi ngày.
Để xử lý các loại dữ liệu đa dạng như vậy thì các kỹ sư tại Twitter đã xây dựng các công cụ nội bộ để có thể xử lý, tổng hợp và truy xuất dữ liệu. Tuy nhiên, với việc dữ liệu phát triển nhanh chóng, quy mô ngày càng lớn thì các kỹ sư tại đây đang phải đối mặt với những thử thách về cơ sở hạ tầng dữ liệu, độ trễ và độ chính xác khi xử lý dữ liệu.
Với cách thiết kế hệ thống xử lý dữ liệu cũ theo Lambda Architecture, nhóm Data Platform đã nhận ra được những hạn chế còn tồn đọng như là độ trễ khi xử lý dữ liệu còn cao, tính toán dữ liệu còn có sai sót, chi phí vận hành hệ thống còn cao v.v... Nhằm thay đổi điều này, hệ thống mới được thiết kế theo Kappa Architecture với việc kết hợp dùng các dịch vụ trên Google Cloud như là PubSub, Dataflow, BigTable để giải quyết các vấn đề còn tồn động. Việc này đã giúp hệ thống của nhóm Data Platform có thể xử lý hàng tỷ events trong thời gian thực, đạt được độ trễ thấp, độ chính xác cao, ổn định, đơn giản về kiến trúc và giảm chi phí vận hành cho các kỹ sư.
Bên cạnh việc nêu rõ quá trình chuyển đổi kiến trúc hệ thống, bài viết còn đem ra số liệu để chứng minh sự vượt trội của hệ thống mới so với hệ thống cũ thông qua việc đánh giá hiệu suất hệ thống và xác thực số liệu đã tính toán qua các từng giai đoạn xử lý trong hệ thống.
A Log4J Vulnerability Has Set the Internet 'On Fire' — www.wired.com
Tuần qua, thông tin về một lỗ hổng bảo mật của một thư viện logging đã trở thành một vụ nổ lớn đối với ngành an toàn thông tin, ảnh hưởng đến toàn bộ các hệ thống kỹ thuật số trên toàn internet.
Lỗ hổng này thuộc về Log4j, một thư viện Logging của Apache được sử dụng phổ biến bởi lập trình viên Java trên toàn cầu.
Log4j là một thư viện Java được sử dụng rất nhiều trong các hệ thống của doanh nghiệp, webapp... Ngay cả Minecraft, một trò chơi khá nổi tiếng cũng sử dụng thư viện này. Công ty sở hữu Minecraft - Microsoft - cũng đã phải đăng một hướng dẫn cụ thể để hướng dẫn người chơi sử dụng phiên bản Java của trò chơi cách vá lỗ hổng này.
Các nhà bảo mật đã bắt đầu vá lỗ hổng này, nhưng cũng trong cùng thời điểm đó, hacker cũng đang bắt đầu thực hiện scan toàn internet để tìm kiếm các hệ thống bị ảnh hưởng. Một số thậm chí đã phát triển những tool tự động khai thác lỗ hổng và cài các mã độc có thể lây lan một cách độc lập từ hệ thống này sang hệ thống khác.
Lỗ hổng này cho phép một attacker có thể thực thi một đoạn mã bất kì dưới dạng một chuỗi kí tự được log bởi Log4j phiên bản 2.0 hoặc cao hơn (phiên bản 2.15 đã được vá lỗ hổng này), cho phép hacker chiếm quyền điều khiển của hệ thống.
Tương tự như Minecraft, các công ty sẽ phải thực hiện vá lỗ hổng này ngay lập tức, tuy nhiên việc thực hiện nó sẽ không dễ dàng. Log4j không chỉ đơn thuần có thể vá ở các service trực tuyến bởi chỉ cần một sai sót nhỏ có thể làm cho hệ thống mất đi khả năng log lại các xử lý được thực thi, khi đó họ sẽ không biết được nếu như hệ thống của mình đã bị tấn công hay chưa.
Mời các bạn đọc bài viết chính và một số bài viết liên quan để hiểu hơn về lỗ hổng bảo mật này.
Link các bài viết liên quan:
https://kb.vmware.com/s/article/87073
https://www.lunasec.io/docs/blog/log4j-zero-day/
Góc Distributed System
Read-after-write consistency kì 2: Quorum
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:
Đề bài: Number of Closed Islands
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
Real-Time Stream Analytics with Google Cloud Dataflow: Common Use Cases & Patterns
Google Cloud Dataflow hỗ trợ xử lý và phân tích dữ liệu streaming với độ trễ thấp, qua đó chúng ta có thể dễ dàng thu thập và phân tích thông tin chi tiết trong thời gian thực. Qua buổi Tecktalk của Google Cloud, hãy cùng hiểu cách Dataflow có thể kết hợp với các công cụ khác như PubSub, Kafka, BigQuery, Bigtable hoặc Datastore, để xây dựng kiến trúc end-to-end streaming.
Một số vấn đề được đề cập cụ thể trong các mô hình streaming như: Grouping với Processing-Time Window, grouping với Event-Time window, tìm hiểu về Windowing, khi nàoTriggering xảy ra với Watermark, xử lý với dữ liệu lỗi v.v...
Các vấn đề được đề cập giúp chúng ta có cái nhìn chi tiết hơn về các yếu tố và vấn đề cần tính đến khi với làm việc với luống dữ liệu streaming, không chỉ trên GCP mà bất cứ nền tảng nào khác. Qua đó chúng ta có thể có thể áp dụng các giải pháp streaming với các vấn đề phổ biến như data ingestion, real-time reporting & analytics, real-time alerting, hay fraud detection, ...
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
