#168 - Bài toán Rate limiting tại Cloudflare

Apr 26, 2021

Những bài viết hay

Leader election and Sharding Practices at Wix microservices — medium.com

Hệ thống phân tán gồm 2000 clustered microservices của Wix được yêu cầu khả năng xử lý hàng tỷ event mỗi ngày với tốc độ rất cao.

Một yêu cầu đặt ra là hệ thống cần phải có khả năng cân bằng tải giữa các cluster node khác nhau, sao cho không có tắc nghẽn (bottleneck) nào được tạo ra. Để phục vụ các request HTTP, vấn đề này có thể được xử lý bởi các bộ cân bằng tải như NGINX hoặc Amazon’s ELB.

Cũng có nhiều trường hợp các event và hành động phải được xử lý trong ngữ cảnh atomic, để đảm bảo dữ liệu được lưu trữ vẫn hợp lệ. Ví dụ: thay đổi số dư tài khoản hoặc cập nhật hàng tồn kho.

Trong bài đăng trên blog này, chúng ta sẽ khám phá các phương pháp khác nhau được sử dụng bởi các microservices của Wix nhằm đảm bảo các hoạt động atomic để cập nhật trạng thái của một số tài nguyên (ví dụ: bộ nhớ cache hoặc DB entry), do đó giữ cho dữ liệu hợp lệ nhưng không ảnh hưởng đến thông lượng cao (high throughput) và đảm bảo độ trễ thấp (low latency).

Các phương pháp sau được chia theo "mức độ chi tiết" của hoạt động:

Chọn một node leader duy nhất (single leader service node) để chạy một nhiệm vụ hoặc một loạt các nhiệm vụ.
Sharding một tập dữ liệu lớn bằng "multiple leader nodes".
Xử lý tuần tự các sự kiện cho single domain bởi bất kỳ một service node ngẫu nhiên nào.

Building the Future of Our Desktop Apps: Spotify Engineering — engineering.atspotify.com

Spotify là một trong những dịch vụ cung cấp nhạc tốt nhất hiện nay, nổi tiếng với trải nghiệm sử dụng ứng dụng và được tối ưu rất tốt trên mọi nền tảng (web, mobile, PC).

Trong bài viết sau đây, các kĩ sư tại Spotify đã chia sẻ về quá trình và những thách thức mà họ đã gặp phải khi phát triển UI cho Spotify Client app và web một cách đồng nhất. Từ lúc ban đầu web và client là 2 codebase riêng biệt. Tuy nhiên, sau đó họ quyết định tận dụng các công nghệ web để tạo ra một WebPlayer (được phát triền bằng React.js) duy nhất có thể chạy đa nền tảng, tối ưu rất nhiều chi phí và thời gian về mặt phát triển cũng như đồng bộ được giao diện trên nhiều thiết bị.

7 Absolute Truths I Unlearned as Junior Developer — monicalent.com

Chắc hẳn các bạn kỹ sư phần mềm đều phải trải qua giai đoạn junior để thu thập kiến thức và kinh nghiệm cho việc trở thành một senior engineer. Giai đoạn này khá là quan trọng cho mọi ngành nghề và cho mọi kỹ sư. Tuy nhiên, mỗi người sẽ có mỗi trải nghiệm khác nhau và ý kiến khác nhau về bản thân họ trong giai đoạn phát triển đó. Bài viết sau đây của tác giả Monica Lent nói về những bài học và những kinh nghiệm mà tác giả rút ra được sau 10 năm làm việc trong lĩnh vực phần mềm.

Đặc biệt, tác giả nêu rõ về cách mà suy nghĩ của tác giả đã thay đổi theo thời gian như thế nào khi mà có nhiều kinh nghiệm hơn. Trong đó, một chủ đề khá là hay được tác giả nêu lên và học được ở đây là: các engineers cần phải phát triển những kỹ năng khác ngoài lập trình như là giao tiếp, quản lý dự án, ước lượng dự án, … để mà có thể trở thành senior engineers tốt

Góc Distributed System

Rate limiting tầng Edge ở Cloudflare

Rate Limiting là một kỹ thuật đang được sử dụng tại rất nhiều hệ thống lớn hiện nay như Google, Facebook, LinkedIn v.v... nhằm đảm bảo hệ thống hoạt động trơn tru, tránh spam, ddos. Mục đích của Rate Limiting là chỉ cho phép hệ thống xử lý một số lượng request nhất định trong một khoảng thời gian.

Tại Cloudflare, họ đã phát triển service Rate Limiting để giúp khách hàng sử dụng dịch vụ của họ có thể tránh được các cuộc tấn công như từ chối sử dụng dịch vụ (ddos), brute force password, v.v... nhằm vào application layer.

Thông thường, rate limting sẽ dựa trên việc theo dõi các địa chỉ IP gửi request, theo dõi khoảng thời gian giữa mỗi request. IP address là phương pháp chính một ứng dụng xác định ai là người đang thực hiện request.

Một giải pháp cho rate limiting là đo lường thời gian giữa các request được gửi từ một địa chỉ IP, và đo các request gửi trong một khoảng thời gian nhất định. Nếu có quá nhiều request từ 1 IP trong một khoảng thời gian, rate limiting sẽ không hoàn thành các request này.

Rate Limiting truy vấn tới tầng Edge của Cloudflare là một bài toán phức tạp hơn bởi số lượng lớn các domains và số lượng lớn các Rate Limiting rules mà Cloudflare đáp ứng. Vậy họ xây dựng Rate Limiting như thế nào?

Thứ nhất, Cloudflare sử dụng kĩ thuật Anycast ở tầng Edge, nghĩa là dù sử dụng cùng 1 địa chỉ public IP cho khách hàng thì traffic luôn được route tới data center gần khách hàng nhất chứ không phải toàn bộ đẩy về 1 location. Điều này có hai tác dụng:

Hệ thống Edge tránh được single point of failure
Đảm bảo truy vấn từ cùng 1 địa chỉ IP nguồn sẽ luôn được route tới 1 đích đến PoP. Note: PoP (Points of Presence) là một khái niệm trong CDN, nghĩa là điểm truy cập, ý chỉ các server vật lý đặt ở những vị trí địa lý mà tập trung toàn bộ lượng truy cập cho vùng địa lý đó. Những server này được tối ưu về phần cứng và phần mềm đảm bảo hiệu năng truyền tải dữ liệu cao

Đối với bài toán Rate Limiting, việc đếm request là mấu chốt đảm bảo tính chính xác của Rate Limiter. Dữ liệu đếm request cần phải share giữa các server bởi tính phân tán của hệ thống. Đối với lượng truy vấn cực lớn ở Cloudflare, rõ ràng các implementation "naive" của leaky bucket hay fixed window không đáp ứng được nhu cầu bởi tính không chính xác khi reset counter.

Cloudflare đã dựa vào thuật toán Sliding Window để xử lý tốt hơn vấn đề reset counter. Thuật toán của CloudFlare có thể "suy luận" request rate cho timeframe hiện tại dựa vào thông tin về counter ở timeframe trước đó. Cụ thể:

Nếu Rate được cấu hình là 50 request/phút, counter của phút trước đó là 42 và counter của thời điểm hiện tại trong timeframe 1 phút là 18 ở giây thứ 15. Rate được tính như sau:

rate = 42 * ((60-15)/60) + 18

= 42 * 0.75 + 18

= 49.5 requests

Như vậy, chỉ cần 1 request nữa trong timeframe hiện tại, Rate Limiter sẽ được trigger

Thuật toán này có một số ưu điểm:

Dễ hiểu và dễ lập trình, không có burst
Chỉ cần 2 biến số cho mỗi counter => memory usage rất thấp
Việc tăng biến đếm chỉ tốn 1 lệnh INCR và lệnh này là atomic
Việc tính rate rất nhanh vì chỉ là các phép toán cơ sở

Thực tế cho thấy thuật toán hoạt động khá chính xác, số liệu của 400 triệu requests từ 270,000 sources cho thấy:

0.003% số request bị rate limit sai.
Rate thực tế và rate của thuật toán sai lệch 6%
Chỉ có 3/270,000 sources bị rate limit sai.

Tuy nhiên, việc tính rate ở đây lại cần 1 thao tác truy cập Memcached (một ràng buộc ở Cloudflare) và các DDOS attack tới Cloudflare ghi nhận hệ thống Memcached đã nhiều lần bị quá tải. Để giảm tải cho Memcached, Cloudflare đã thiết kế thao tác này về dạng async:

Khi request rate đã quá threshold, toàn bộ server trong PoP được thông báo để chặn request có source-dest đó.
Còn khi request đó chưa bị rate limit (đối với source-dest đó), PoP sẽ cho phép truy vấn đi qua và thực hiện việc tăng counter sau (async).
Ngoài ra, một điểm tối ưu (theo kiểu trade-off) nữa là CloudFlare có đưa ra đơn vị timeout cho Rate Limiter, khi request (source-dest) đã bị rate limited thì những request sau đó sẽ không cần cập nhật counter nữa cho tới khi hết timeout.

Bài viết gốc: https://blog.cloudflare.com/counting-things-a-lot-of-different-things/

Góc Data Warehouse

Pocket: Elastic Ephemeral Storage for Serverless Analytics

Serverless computing như AWS Lambda, Google Cloud Functions, hay Azure Functions hiện đang trở nên phổ biến hơn khi mà người dùng có thể chạy chương trình của họ chỉ trong những lúc mà họ cần. Điều này sẽ giúp người dùng giảm chi phí hơn khi mà họ không cần phải quản lý và trả tiền thuê một máy chủ mỗi tháng khi họ không sử dụng. Serverless computing thu hút khá là nhiều trường hợp sử dụng, đặc biệt là về các tác vụ phân tích truy vấn tương tác (interactive data analysis).

Tuy nhiên, các tác vụ interactive analysis thường có một lượng lớn dữ liệu trung gian tạm thời ở các query execution stage thường được gọi là intermediate data. Thông thường, những hệ thống phân tích dữ liệu như Spark sẽ thiết lập việc truyền tải các dữ liệu trung gian bằng cách xây dựng các đặc vụ (agent) ở mỗi máy chủ để chứa các intermediate data ở local storage rồi trao đổi trực tiếp dữ liệu với các máy chủ khác qua network.

Việc truyền tải intermediate data như thế này khá là hợp lý khi mà hệ thống Spark của bạn được triển khai lâu dài trên các máy chủ và các máy chủ có thể liên lạc trực tiếp lẫn nhau. Nhưng ở môi trường serverless computing thì cách vận hành không được khả thi cho lắm. Cụ thể là:

Các máy chủ serverless thường sẽ không có các agent chạy lâu dài để quản lý local storage
Các ứng dụng ở trên serverless computing sẽ không có thể kiểm soát trong việc điều khiển lịch trình tác vụ và liên lạc qua lại giữa các tác vụ hay máy chủ

Do đó, một điều hiển nhiên ở đây cho các ứng dụng interactive data analysis trên serverless computing là sử dụng các hệ thống remote storage như là S3, DynamoDB, … Tuy nhiên, các dịch vụ storage này thường không phải là một lựa chọn đúng đắn cho việc chia sẻ dữ liệu trung gian tạm thời khi mà các dữ liệu này sẽ được xóa đi khi query chạy xong. Lý do ở đây là các hệ thống này thường được thiết kế và tối ưu cho các dữ liệu cần được chứa lâu dài và bền vững.

Bài báo sau đây ở hội nghị OSDI 2018 giới thiệu về hệ thống Pocket, một hệ thống được thiết kế chuyên về việc lưu trữ và truy vấn dữ liệu trung gian tạm thời cho các ứng dụng chạy trên serverless computing. Pocket cũng là hệ thống đầu tiên tập trung vào lĩnh vực này khi mà các intermediate data không cần phải được chứa quá lâu và quá bền vững.

Code & Tools

This Week Sponsors

Sự kiện TECHTALK cuối tuần vừa qua tại LINE Technology Vietnam đã diễn ra với chủ đề System Design & Architecture, với sự tham gia thảo luận sôi nổi của hơn 100 kỹ sư từ nhiều công ty trong ngành.

Hãy follow chúng tôi để cập nhật về các sự kiện sắp tới nhé!

Vài hình ảnh từ event:

Tham khảo các vị trí đang cần tuyển tại LINE Technology Vietnam

Quotes

The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.

- Donald E. Knuth