#204 - Hệ thống Xử lý Sự kiện Quảng cáo của Uber

Jan 06, 2022

Thân chào quý bạn đọc Newsletter,

Trong các survey phản hồi trước đây, team Grokking có ghi nhận góp ý từ một số bạn đọc là việc tìm lại nội dung của các số newsletter cũ hơi khó.

Nhằm giải quyết vấn đề này, team Grokking đang phát triển một trang chỉ mục online dành cho các bài viết liên quan đến chủ đề Software Engineering nói chung, đặc biệt là các bài viết đã được đăng trên các số newsletter cũ.

Sắp tới, team product đang cần phỏng vấn một vài bạn đọc thường xuyên của Newsletter để có thêm ý tưởng giúp hoàn thiện trang chỉ mục này. Buổi phỏng vấn sẽ diễn ra online và dự kiến sẽ kéo dài 1-2 giờ đồng hồ.

Bạn đọc nào quan tâm và có thể tham gia phỏng vấn vui lòng đăng ký vào form này: Form đăng ký , team Grokking sẽ liên hệ để xếp lịch phỏng vấn tùy theo thời gian rảnh của bạn.

Rất cảm ơn quý bạn đọc đã ủng hộ Grokking Newsletter thời gian qua, và rất mong sẽ nhận được nhiều sự ủng hộ hơn nữa trong thời gian sắp tới.

---

Trong số này, chúng ta sẽ cùng tìm hiểu về:

Cách MongoDB cải thiện storage engine;
Cách Netflix xây dựng hệ thống tìm kiếm và khắc phục lỗ hổng an ninh;
Hệ thống xử lý event quảng cáo của Uber;
Thuật toán SetSketch;
Lời giải bài Swapping Nodes in a Linked List.

Những bài viết hay

Getting Storage Engines Ready for Fast Storage Devices

Hai thập kỷ vừa qua chứng kiến sự phát triển mạnh mẽ của công nghệ lưu trữ đĩa cứng, bắt đầu từ sự ra đời của SSD, thay đổi cổng kết nối từ SATA sang PCIe, và gần đây là công nghệ bộ nhớ non-volatile và các quy trình sản xuất. Với những tiến bộ trên, độ trễ trong việc truy xuất dữ liệu từ đĩa cứng đã giảm đáng kể so với trước đây.

Tuy nhiên, các hệ thống phần mềm hiện nay có vẻ vẫn chưa bắt kịp tốc độ phát triển này. Nhiều nghiên cứu cho thấy vẫn còn tồn tại nhiều điểm nghẽn khiến cho các phần mềm ở tầng ứng dụng chưa tận dụng được những tiến bộ của phần cứng. Một số điểm nghẽn thường gặp là cách tổ chức file system chưa được tối ưu hoá, và cách truy xuất dữ liệu của hệ điều hành.

Để cải thiện vấn đề này, các kỹ sư của MongoDB đã nghiên cứu giải pháp sử dụng memory-mapped files cho I/O và kỹ thuật cấp phát trước một vùng trống cho file.

Về cơ bản, memory-mapped files giúp giảm chi phí phát sinh từ system call bằng cách sử dụng Translation Lookaside Buffer (TLB là một bộ đệm dữ liệu nằm trong MMU của CPU được dùng để lưu dữ liệu ánh xạ địa chỉ vùng nhớ ảo sang địa chỉ vùng nhớ vật lý). Tuy nhiên phương án này chỉ hiệu quả khi truy cập một file có dung lượng cố định. Về sau, đội ngũ của MongoDB đã đưa ra một phương pháp giúp xử lý các thao tác liên quan đến file system theo khối, để tối ưu chi phí xử lý phát sinh.

Các thay đổi này đã giúp read throughput của storage engine tăng lên 63%, tuy nhiên trong một số trường hợp, xử lý liên quan đến việc ghi (như update và insert) tỏ ra kém hiệu quả hơn.

Mời các bạn tham khảo chi tiết giải pháp và cách thực hiện qua bài viết gốc dưới đây.

Snaring the Bad Folks

Trong những năm gần đây, các vụ rò rỉ dữ liệu trên cloud xảy ra ngày càng nhiều, với tính chất phức tạp và công phu hơn trước. Hiện tại trên thị trường có khá nhiều giải pháp giúp tìm kiếm và khắc phục các lỗ hổng an ninh, tuy nhiên các giải pháp này khó có thể đáp ứng được mọi trường hợp và nhu cầu đa dạng của nhiều hệ thống khác nhau.

Vào năm 2020, đội ngũ kỹ sư Netflix đã quyết định tự xây dựng hệ thống riêng để tìm kiếm và khắc phục các lỗ hổng an ninh, với tên gọi Snare. Snare sử dụng nhiều nguồn dữ liệu khác nhau như AWS Security Hub, AWS Config Rules, và các nguồn nội bộ để tìm kiếm lỗ hổng và lỗi. Tương tự những hệ thống an ninh khác, Snare được chia thành bốn giai đoạn: Detection, Enrichment, Reporting & Management, và Remediation. Trong bài viết sau, đội ngũ kỹ sư Netflix mô tả cách họ xây dựng và thiết kế từng giai đoạn của Snare sao cho phù hợp với mô hình hệ thống ở Netflix.

Real-Time Exactly-Once Ad Event Processing with Apache Flink, Kafka, and Pinot

Để ra mắt tính năng quảng cáo trên UberEats, đội ngũ kỹ sư Uber phải giải quyết các bài toán liên quan đến ngành quảng cáo như hệ thống đấu giá, phân bổ hay tổng hợp báo cáo doanh thu. Để làm được điều này, đội kỹ sư Uber xác định việc đầu tiên và quan trọng nhất là xây dựng hệ thống xử lý exactly-once events với độ trễ “near real-time”.

Hiểu một cách đơn giản, mỗi quảng cáo được hiển thị sẽ có event tương ứng cho mỗi hành động của người dùng, như impression hay click. Nhiệm vụ của hệ thống là tổng hợp, phân bổ và quản lý các event do người dùng tạo ra khi tương tác với quảng cáo trên ứng dụng Uber.

Để đạt tính chính xác tuyệt đối (100%) theo quy định về xử lý dữ liệu liên quan đến hoạt động quảng cáo của Uber, đội kỹ sư tại đây đã thiết kế một mô hình kiến trúc dựa trên 4 công nghệ mã nguồn mở: Stream Processing với Apache Flink, Message Queues với Apache Kafka, Real-Time Analytics với Apache Pinot và Data Warehousing với Apache Hive.

Việc xây dựng hệ thống nhằm xử lý exactly-once events được chia thành nhiều module nhỏ, tối ưu về mặt vận hành và chức năng như Data Cleansing, Aggregation, Record UUID Generation. Hiện tại, hệ thống này đang xử lý hàng trăm triệu event quảng cáo mỗi tuần, và con số này vẫn còn tiếp tục gia tăng.

Để tìm hiểu thêm về thách thức, lý do cũng như quá trình xây dựng hệ thống này, mời bạn đọc bài viết bên dưới.

Góc Database

Set Sketch

Data Sketch (gọi tắt là Sketch) là thuật ngữ để chỉ một cấu trúc dữ liệu ít chiếm dụng bộ nhớ được dùng để đại diện cho một tập dữ liệu lớn. Trong hơn 20 năm qua, nhiều thuật toán Sketch đã được phát triển để giải quyết các loại bài toán khác nhau. Nhìn chung, các thuật toán này được phân loại dựa theo các đặc tính như:

Idempotency (Tính lũy đẳng): Nếu insert cùng một giá trị vào một Sketch nhiều lần, thì trạng thái của Sketch đó vẫn không bị thay đổi.
Commutativity (Tính giao hoán): Thứ tự insert các phần tử không ảnh hưởng đến trạng thái cuối của Sketch.
Mergeability (Tính khả hợp): Giả sử chúng ta có một tập dữ liệu lớn, ta có thể chia tập này ra thành nhiều phần nhỏ, xây dựng Sketch cho từng phần, sau đó nhập các Sketch này lại thành Sketch tổng. Nếu Sketch tổng giống như Sketch được tạo ra từ tập dữ liệu ban đầu thì thuật toán đang sử dụng được gọi là có tính khả hợp.
Space efficiency (Hiệu năng bộ nhớ): Rõ ràng các Sketch cần có kích thước nhỏ hơn nhiều lần so với tập dữ liệu gốc. VD: HyperLogLog dùng ít bộ nhớ hơn Log(Log(N)) lần, với N là kích thước của tập dữ liệu gốc.
Recording speed (Tốc độ ghi): Các Sketch thường được dùng cho các phép tính toán nhanh, nên cũng cần hiệu quả về thời gian xử lý, đặc biệt là trong các bài toán liên quan đến Stream.
Cardinality estimation: Khả năng ước tính được kích thước của tập hợp gốc.
Joint estimation: Ước tính được kết quả giao, hợp, bù trừ của các tập hợp chỉ dựa vào các Sketch.
Locality sensitivity: Khi quản lý nhiều Sketch cho nhiều tập dữ liệu, các Sketch liên quan với nhau có thể được sắp xếp gần nhau.

Trong số những thuật toán đã được phát triển, MinHash và HyperLogLog là hai thuật toán được ứng dụng rộng rãi nhất. Ở kỳ trước, chúng ta cũng đã làm quen với một thuật toán mới là HyperMinHash (2015) được tạo ra với mục tiêu thống nhất MinHash và HyperLogLog lại với nhau. Ở kỳ này, chúng ta cùng làm quen với một thuật toán khác gọi là SetSketch vừa được công bố trong năm 2021. Link bài báo.

Góc Lập Trình

Đề tuần này: All Nodes Distance K in Binary Tree

Lời giải đề bài tuần trước:

Đề bài: Swapping Nodes in a Linked List

Lời giải:

Đề bài yêu cầu đổi chỗ của node thứ k tính từ đầu list, với node thứ k tính từ cuối list. Để giải đề này, ta cần tìm hai node thỏa mãn điều kiện đề bài và hoán đổi giá trị của chúng với nhau.

Để tìm vị trí của hai node, ta có các phương án như sau:

1. Nếu ta gọi độ dài của list là n, thì node thứ k tính từ cuối list chính là node thứ (n - k + 1) tính từ đầu list. Như vậy, ta có thể dùng một vòng lặp để tính độ dài của list, và một vòng lặp khác để tìm node thứ k và thứ (n - k + 1).

2. Ta có thể sử dụng hai con trỏ lệch nhau k vị trí để tìm hai node thoả mãn điều kiện đề bài:

Thiết lập hai con trỏ "first" và "second" là head của mảng.
Ta di chuyển con trỏ "second" lên phía trước k vị trí.
Ta đồng thời di chuyển "first" và "second" cho tới khi "second" == null, lúc này "first" ở vị trí của phần tử thứ k tính từ cuối list.

Với phương án 2, ta chỉ cần duyệt list một lần duy nhất. Xem chi tiết giải thuật này tại https://pastebin.com/tbdjusNw.

Ngoài hai phương án trên, chúng ta vẫn có thể thực hiện giải thuật chỉ với duy nhất một vòng lặp, mời bạn đọc thử thực hiện.

Code & Tools

IPFS: Giao thức P2P dùng để chia sẻ và lưu trữ dữ liệu.
Tantivy: Thư viện full-text-search viết bằng Rust.

Góc Sponsors

FPT Smart Cloud (FCI) – a subsidiary of FPT Corporation, is a leading provider of Artificial Intelligence (AI) and Cloud Computing solutions in Vietnam. FCI was established with a mission to offer best-in-class AI & Cloud platforms, creating a breakthrough in business operations. FPT Smart Cloud strives to be a pioneer in AI and Cloud with state-of-the-art technology, a diverse product ecosystem, and global connectivity.

Products and services within the FPT Smart Cloud ecosystem:

Infrastructure as a Service (IaaS)
Platform as a Service (PaaS)
Software as a Service (SaaS)
Artificial Intelligence (AI)

Open positions:

Senior Fullstack (AI Fullstack - Hanoi)
Senior Devops (AI DevOps - Hanoi)
Identity and access management engineer (Automation/ Software Engineer – Hanoi)
Cloud OpenStack engineer (Hanoi/HCMC)

Other positions at FPT Smart Cloud Careers Page

Quotes

I'm not a great programmer; I'm just a good programmer with great habits.

― Kent Beck