View profile

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

Grokking Vietnam
Grokking Vietnam
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
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
Lời giải đề bài tuần trước:
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:
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
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