#205 - Netflix push notifications đến hàng triệu thiết bị như thế nào?

Jan 13, 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.

Những bài viết hay

How Ringpop from Uber Engineering Helps Distribute Your Application

Ringpop là một thư viện Node.js giúp các ứng dụng mang đến khả năng hợp tác và điều phối cho các ứng dụng phân tán. Ringpop có 3 phần: membership protocol, consistent hashing và khả năng forward request đến node được yêu cầu.

Lợi ích của Ringpop so với Dynamo hay Cassadra là việc mang cơ chế partitioning và điều phối lên tầng application mà không phụ thuộc vào tầng infratructure do một team khác hay bên thứ ba chịu trách nhiệm.

Ba phần chính của Ringpop có thể tóm tắt như sau:

1. Membership protocol: Giao thức thành viên tin đồn SWIM cho phép các node mới phát hiện ra nhau, phổ biến thông tin theo cách truyền nhiễm và liên tục ping lẫn nhau để mỗi node biết về sự tồn tại và trạng thái của mọi node khác. Như vậy mỗi lần thêm hoặc bớt node, chúng ta không cần thay đổi code.

2. Consistent hashing: Vòng tròn hash với consistent hashing cho phép phân công request vào các khoảng interval thay vì từ các node cụ thể. Điều này giúp loại bỏ nhu cầu assign lại bằng tay khi cụm ứng dụng thay đổi kích thước ( thêm hoặc bớt node)

3. Fowarding: request có thể vào bất kỳ node ngẫu nhiên nào và Ringpop sẽ chuyển tiếp request đó đến node thích hợp trong vòng.

Ringpop đã được Uber publish dưới dạng open-source trên github. Mời các bạn đọc bài viết gốc hoặc Ringpop document để tìm hiểu chi tiết hơn.

Góc Distributed System

Hybrid Logical Clock

Trong hệ thống phân tán, đồng hồ vật lý (physical clocks - PC) cho ta biết thời gian các sự kiện diễn ra nhưng lại thiếu tính chính xác vì mỗi đồng hồ có độ trễ (clock drift) và độ lệch (clock skew) khác nhau. Dù có giao thức đồng bộ thời gian qua mạng (Network time protocol - NTP), đồng hồ vật lý vẫn không đáng tin khi xây dựng hệ thống phân tán. Đồng hồ logic (logical clock - LC) được Leslie Lamport đưa ra vào năm 1978 để thay thế đồng hồ vật lý trong việc xác định thứ tự các sự kiện dựa vào quan hệ nhân quả (causal relationships), tuy vậy nó lại có hạn chế là không có tính kết nối với thời gian thực và do đó ta không thể truy xuất sự kiện dựa theo thời gian. Đồng hồ lai (hybrid logical clock - HLC) là một giải pháp cho việc kết hợp thông tin giữa đồng hồ vật lý và đồng hồ logic. HLC giúp nắm bắt quan hệ nhân quả như đồng hồ logic, cũng như nhận biết các consistent snapshots trong hệ thống phân tán. HLC có thể dùng để thay thế đồng hồ vật lý, do nó duy trì một đồng hồ logic có giá trị luôn gần sát với thời gian đồng hồ vật lý. Ngoài ra, HLC cũng phù hợp để lưu trữ trong định dạng 64-bit của NTP. Xem chi tiết thuật toán tại đây.

Bài toán:

Với l.e là thời gian logic và pt.e là thời gian vật lý, cần gán timestamp l.e cho từng sự kiện e sao cho:

Nếu sự kiện e xảy ra trước sự kiện f, l.e < l.f
l.e có thể được lưu trong không gian bộ nhớ O(1)
l.e gần pt.e nhất có thể, nói cách khác, luôn có một cận trên epsilon cho |l.e - pt.e|

Quy ước:

HLC(e) là HLC timestamp của event ebao gồm 3 thành phần (pt, l, c)
l: Largest physical timestamp known to current node - Thời gian vật lý lớn nhất biết được của các node, kể cả node hiện tại.
c: Logical (Causal) timestamp - Thời gian logic cho các event có quan hệ nhân quả.
pt: Physical timestamp - Thời gian vật lý.

Ý tưởng chính

Với mỗi node trong system, cần kết hợp thông tin giữa thời gian vật lý pt và thời gian logic c. Do ptkhông hoàn toàn chính xác, ta sẽ có thêm tham số l là thời gian vật lý lớn nhất biết được khi giao tiếp với các node khác tại mọi thời điểm.
l sẽ được dùng để so sánh HLC timestamp giữa 2 node trong mạng, thông tin từ node có l lớn hơn sẽ được xem là cập nhật hơn. Khi l bằng nhau, ta sẽ tiếp tục so sánh thời gian logic c.
Do thời gian vật lý pt luôn tăng còn l chỉ được cập nhật khi có event xảy ra, sẽ có thời điểm pt > l. Lúc này c sẽ được reset lại về 0 (và l được gán lại bằng pt.) Do tính chất này mà các tác giả chứng minh được giá trị c sẽ luôn bị chặn (bounded) bởi một cận xác định.

Tham khảo thuật toán HLC được phát biểu bằng mã giả tại:

Ray.io: Hệ thống phân tán mã nguồn mở cho AI (trí tuệ nhân tạo)

Năm 2018, viện nghiên cứu trí tuệ nhân tạo Berkeley (BAIR) của trường đại học California xuất bản bài báo khoa học về một hệ thống phân tán ứng dụng cho Artificial Intelligent: Ray.io. BAIR cũng là viện nghiên cứu từng tạo ra các hệ thống phân tán khác đang được sử dụng rộng rãi hiện nay như Spark, Apache Mesos, Caffe, vv.

Các thuật toán học máy trí tuệ nhân tạo ngày càng trở nên phức tạp, đòi hỏi khả năng xử lý dữ liệu lớn nhanh & hiệu quả với hệ thống phân tán và mô hình lập trình tính toán song song. Tuy nhiên, cơ sở hạ tầng phân tán dùng cho học máy thường ad-hoc, với nhiều giải pháp tốt khác nhau nhưng mỗi giải pháp chỉ giải quyết được một vài use-case hoặc một phần trong toàn bộ machine learning pipeline hoặc machine learning ecosystem (ví dụ: Hadoop, Spark). Các framework phân tán hiện có cũng không được xây dựng để hỗ trợ trực tiếp cho AI applications.

Các hệ thống hỗ trợ phát triển thuật toán machine learning, cho dù là thuật toán rất đơn giản như Evolution Strategies for reinforcement learning, đặc biệt là các thuật toán Reinforcement Learning, đòi hỏi rất nhiều effort để giải quyết vấn đề về software engineering thay vì vấn đề về machine learning.

Ray.io ra đời để giải quyết vấn đề đó. Ray cung cấp hệ thống framework đồng nhất cùng với mô hình lập trình phân tán tối thiểu hoá (minimalist), hỗ trợ cho các application phân tán tốc độ cao chỉ bằng một vài dòng lệnh đơn giản.

Ray hoàn toàn tương thích với các frameworks hiện có dành cho deep learning (ví dụ: TensorFlow, PyTorch, MXNet), và hiện chỉ hỗ trợ cho Python, Java.

Ray hiện tại đang được sử dụng rộng rãi tại các tập đoàn công nghệ với dữ liệu lớn như Amazon, Tencent. Tham khảo thêm bài giới thiệu về Ray.io, paper và GitHub.

Góc Database

Cách Rockset sử dụng RocksDB

Ở các kỳ Grokking Newsletter trước như #190 hay #197, chúng ta có được giới thiệu tới RocksDB, một storage engine mà các đội ngũ kỹ sư xây dựng để tối ưu hóa hệ thống database của họ. Ở bài viết này, chúng ta sẽ cùng tìm hiểu thêm cách mà Rockset, một công ty phần mềm xây dựng giải pháp cho Real-Time Analytics, sử dụng RocksDB như thế nào cho hệ thống của họ khi mà họ cần đáp ứng được nhu cầu viết và đọc nhanh. Đặc biệt, họ đã phải chỉnh sửa một vài configurations và cơ cấu hoạt động của RocksDB như là:

RocksDB-Cloud: Do RocksDB là một embedded key-value store cho nên dữ liệu sẽ được chứa chỉ trên một máy và không được replicated ở các máy khác. Dẫn tới, để tránh trường hợp dữ liệu bị mất khi máy chủ bị lỗi, đội ngũ kỹ sư ở Rockset đã xây dựng hệ thống RocksDB-Cloud, một hệ thống sẽ replicate tất cả dữ liệu và siêu dữ liệu từ RocksDB sang S3.
Disable Write Ahead Log (WAL): RocksDB sẽ viết tất cả lệnh nó nhận được vào WAL và memtable. Nhiệm vụ chính của WAL là dùng để hồi phục dữ liệu trong memtables khi khởi động lại. Tuy nhiên, WAL thường được chứa trên máy chủ mà RocksDB được chạy. Do đó, để tránh việc gặp lỗi mất dữ liệu WAL, Rockset đã sử dụng một distributed log store để chứa dữ liệu về WAL.
Dynamic Level Target Sizes: Do RocksDB sử dụng cơ chế leveled compaction nên các SST files ở mỗi level sẽ không được compact lên level tiếp theo nếu mà level đó chưa chạm đến giới hạn dữ liệu được đặt ra ở configuration. Để mà có thể tận dụng được cơ chế chuyển đổi giới hạn ở mỗi level từ RocksDB, các kỹ sư ở Rockset đã quyết định dùng flag AdvancedColumnFamilyOptions::level_compaction_dynamic_level_bytes thay vì để ở chế độ mặc định là false
Shared Block Cache: Do mỗi máy chủ ở Rockset có thể chứa nhiều shard replicas và mỗi shard replica sẽ chạy một tiến trình RocksDB, họ đã quyết định dùng chung một Block Cache cho tất cả tiến trình này thay vì mỗi tiến trình có một Block Cache riêng.

Các bạn có thể tham khảo thêm ở bài viết sau đây để hiểu rõ hơn kiến trúc mà Rockset sử dụng RocksDB như thế nào và đồng thời cách họ tối ưu cách sử dụng RocksDB thế nào.

Góc Lập Trình

Đề tuần này: Number of Matching Subsequences

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

Đề bài: All Nodes Distance K in Binary Tree

Lời giải:

Giải thuật tìm khoảng cách giữa 2 nút trong cây khá phức tạp, ta cần tìm nút chung thấp nhất - "Lowest Common Ancestor" của 2 nút và độ sâu (hoặc độ cao), rồi tính khoảng cách. Bạn đọc có thể giải thử với bài: Find Distance in a Binary Tree

Bài này yêu cầu tìm tất cả các nút có khoảng cách "k" với nút "target", nếu ta áp dụng giải thuật tìm nút chung thấp nhất, bài toán sẽ khá phức tạp. Tuy nhiên, nếu ta biểu diễn cây bằng đồ thị, ta có thể dễ dàng tìm các nút có khoảng cách "k" tới "target" bằng BFS.

Ta có thể mô tả giải thuật bằng 2 bước như sau:

1. Duyệt cây bằng DFS và xây dựng đồ thị vô hướng

2. Thực hiện BFS để tìm các nút có khoảng cách "k" tới "target"

Giải thuật được thực hiện như sau: https://pastebin.com/nyhnzXfC

Tech Talks

Scaling Push Messaging for Millions of Devices @Netflix

Qua buổi tech talk của Netflix, Susheel Aroskar chia sẻ về Zuul Push, một dịch vụ push notification có thể scale một cách dễ dàng, xử lý hàng triệu kết nối mở liên tục từ tất cả các ứng dụng Netflix đang chạy. Susheel cũng trình bày về thiết kế của máy chủ Zuul Push và giải thích chi tiết thiết kế của cơ sở hạ tầng định tuyến tin nhắn (message routing infrastructure), giúp mọi microservice của Netflix có thể đẩy thông báo đến bất kỳ ứng dụng đang được được kết nối của người dùng.

Code & Tools

Spark Kubernetes Operator - Spark Kubernetes Operator giúp chúng ta có thể triển khai các ứng dụng Spark dễ dàng và dễ hiểu như chạy các workload khác trên Kubernetes. Nó sử dụng các tài nguyên tùy chỉnh của Kubernetes (Custom Resources Definition - CRD) để chỉ định, chạy và hiển thị của trạng thái các ứng dụng Spark.
Flink Kubernetes Operator - Tương tự như Spark Kubernetes Operator, Flink Kubernetes Operator giúp chúng ta dễ dàng deploy các ứng dụng Flink một cách dễ dàng như các workload thông thường khác trên Kubernetes.

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

On two occasions, I have been asked [by members of Parliament], 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?' I am not able to rightly apprehend the kind of confusion of ideas that could provoke such a question.

― Charles Babbage