View profile

#179 - Kiến trúc đơn hướng trong lập trình giao diện

Grokking Vietnam
Grokking Vietnam
Những bài viết hay
Building Data Platforms I The ETL bias
VALORANT's 128-Tick Servers
Unidirectional User Interface Architectures - André Staltz
Góc Distributed System
Bài viết tuần trước về Async@Facebook có đề cập tới việc sử dụng hệ thống priority queue để phân phối job tới các worker, tuần này góc DS giới thiệu cụ thể hơn về hệ thống Queue đó. Hệ thống này có tên là Facebook Ordered Queueing Service (FOQS), là hệ thống queue tập trung phục vụ cho các dịch vụ backend của Facebook, cũng là phần lõi của hệ thống Async.
Một số điểm trong thiết kế của FOQS bao gồm:
  • Sử dụng MySQL shared để lưu trữ item.
  • Sử dụng một hệ thống tập trung khác là Facebook Shard Manager để quản lý bài toán sharding.
  • Sử dụng Thrift để giao tiếp với các dịch vụ backend.
Phía producer: khi enqueue một item, client cần thiết lập thuộc tính cho item bao gồm:
  • Namespace và topic: là logical group mà item đó thuộc về.
  • Priority: số nguyên 32 bit mô tả độ ưu tiên của item. Giá trị càng thấp độ ưu tiên càng cao.
  • Metadata và Payload của item: dạng binary. Producer đặt bất kì thông tin gì vào theo nhu cầu.
  • Dequeue delay: client chỉ định rõ thời gian tối đa delay trong queue (hiểm nôm na là deadline cần phải dequeue).
  • Lease duration: khoảng thời gian từ lúc item được dequeue tới khi phía consumer phản hồi lại đã xử lý item thành công. Nếu không nhận được phản hồi, queue sẽ tiến hành gửi lại item.
  • FOQS unique ID định danh cho item.
  • TTL: là thời gian tối đa item được tồn tại trong queue, nếu vượt quá nó sẽ bị xoá vĩnh viễn.
Phía consumer: khi lấy item từ queue sẽ gọi qua API Dequeue với 2 tham số: topic và count. Queue sẽ trả về tối đa count items trong topic đó. item được lấy theo thứ tự ưu tiên như sau:
  • Lấy các item có Priority thấp nhất, tương ứng mức độ ưu tiên cao nhất.
  • Đối với những item cùng Priority, lấy những item có Dequeue Delay thấp nhất (sát với deadline cần phải xử lý nhất).
Hai thuộc tính Priority và Dequeue delay thể hiện rõ cách tính mức độ ưu tiên của một item trong FOQS.
Khi consumer xử lý item, nó cần phản hồi lại cho FOQS biết item được xử lý thành công hay không, để FOQS xác định có cần phải gửi lại item hay không qua hai bản tin ACK/NACK. Kỹ thuật cụ thể xử lý bản tin ACK/NACK với các sharded instances bạn tìm hiểu kĩ hơn trong bài viết.
Để xử lý truy vấn API Dequeue, FOQS thực hiện thao tác Reduce (do mỗi FOQS host sẽ được map vào một số lượng sharded MySQL nhất định) trên các hosts để tìm ra items có độ ưu tiên cao nhất và lưu chúng vào một cấu trúc dữ liệu là Prefetch Buffer; từ đó trả kết quả cho API. Để tối ưu tốc độ truy vấn, mỗi shard sẽ duy trì in-memory danh sách index của các primary keys của các items nó quản lý, sắp xếp theo priority. Các Dequeue Worker sẽ tổng hợp thông qua k-way merge và select trên những index đó. Prefetch Buffer được cập nhật liên tục theo thời gian, các topics được lấy items ra sẽ được làm đầy bằng các items tiếp theo.
Một số vấn đề khác về thiết kế FOQS: Pull/Push model, Checkpointing, Disaster Readiness bạn tham khảo bài viết chi tiết ở đây
Góc Lập Trình
Đề ra tuần này:
Cho một mảng các số nguyên arr và một số k với 1<= k <= arr.size().
Hãy tính giá trị lớn nhất của các mảng con có độ dài là k.
Ví dụ với mảng arr = [10, 5, 2, 7, 8, 7], k = 3, chúng ta sẽ có kết quả: [10, 7, 8, 8]
Giải thích:
  • 10 = max(10, 5, 2)
  • 7 = max(5, 2, 7)
  • 8 = max(2, 7, 8)
  • 8 = max(7, 8, 7)
Các bạn có thể thử sức tại đây:
Lời giải tuần trước:
Ta có thể dễ dàng nhận thấy, số đường đi từ điểm xuất (0, 0) tới đích (m-1, n-1) bằng tổng số đường đi từ điểm xuất phát tới ô bên trái và phía trên của đích. Ta có thể giải bài toán phương pháp đệ quy như sau:
def uniquePaths(m:Int, n:Int):Int={
  // base case
 if(m==1 || n==1) return 1 
uniquePaths(m-1, n) + uniquePaths(m, n-1)
}
Để giảm chi phí tính toán của chương trình, ta có thể tối ưu bài này bằng phương pháp quy hoạch động như sau:
def uniquePaths(m:Int, n:Int):Int={
 val dp= Array.fill(m, n)(1) for(r<-1 until m){
  for(c<-1 until n){
   dp(r)(c)= dp(r)(c-1)+dp(r-1)(c)
  }
 } dp(m-1)(n-1)  
}
Các bạn có thể thử làm bài này tại đây.
Code & Tools
This Week Sponsors
Discover your career at KMS with many available jobs, especially with a 1-month joining bonus: CLICK HERE.
More surprisingly, your next move could be even greater when referred by your buddies who are working at KMS:
  • One-month joining bonus
  • FULL 13th-month salary
  • Cut off HR screening and phone interview
  • Only 1 all-included interview
  • Employment results within 3 working days
We hope it impresses you in case you’re considering KMS Technology as your next career destination or you know someone who does.
Quotes
Any fool can write code that a computer can understand. Good programmers write code that humans can understand.
- Martin Fowler
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

Ngoài ra các bạn có thể gửi feedback cho Grokking Newsletter team ở https://bit.ly/3k3Jdw5 hoặc đóng góp bài viết tại https://bit.ly/2XaBUtF

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.
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam