View profile

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

Revue
 
 

Grokking Newsletter

April 26 · Issue #169 · View online

Tuyển tập những bài viết hay cùng sự kiện bổ ích dành cho kĩ sư phần mềm tại Việt Nam.


Những bài viết hay
Leader election and Sharding Practices at Wix microservices Leader election and Sharding Practices at Wix microservices
Building the Future of Our Desktop Apps: Spotify Engineering Building the Future of Our Desktop Apps: Spotify Engineering
7 Absolute Truths I Unlearned as Junior Developer 7 Absolute Truths I Unlearned as Junior Developer
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:
  1. Hệ thống Edge tránh được single point of failure
  2. Đả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.
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à:
  1. 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
  2. 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
Did you enjoy this issue?
If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Powered by Revue
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam