View profile

#177 - Giới thiệu nền tảng Netflix Cosmos

Grokking Vietnam
Grokking Vietnam
Những bài viết hay
We need to talk about data governance
Góc Distributed System
Phát hiện lỗi (failure detection) là một trong những yếu tố cơ bản đối với khả năng chịu lỗi của các hệ thống phân tán (fault-tolerance).
Các phương pháp cổ điển sẽ trả về kết quả theo dạng boolean information (trust vs suspect).
Phương pháp Phi Accrual Failure Detection cung cấp một phương pháp tổng quan, trả về một con số động, cho phép linh hoạt hơn trong các hệ thống phân tán.
Thay vì cung cấp output theo dạng boolean (system up or down), phương pháp này sẽ cung cấp output theo một thang đo liên tục (continuous scale), với giá trị càng cao thể hiện khả năng system down càng lớn.
Ví dụ: Trong một ứng dụng phân tán, có 1 master node đóng vai trò điều tiết các job trong 1 queue, và gửi job tới các idle worker (pi) (giả sử master không bao giờ down). Accrual failure detection sẽ tính giá trị phi của các worker, giả sử với worker pw, giá trị phi đạt tới 1 ngưỡng thấp (0.7), master sẽ đánh dấu pw và ngừng gửi các job tới pw. Khi giá trị phi của pw đạt tới một ngưỡng cao hơn (0.8), master sẽ ngừng tất cả các job chưa finish trên pw và gửi tới các node khác. Khi đạt tới một ngưỡng cao nhất (1), master sẽ remove pw khỏi danh sách worker và tiến hành thu hồi tài nguyên.
Cách tính φ như sau:
Bước 1: Sampling heartbeat arrivals
Để mô hình đơn giản, ta giả sử chỉ có 2 process p và q, trong đó q sẽ tiến hành monitor p. p sẽ gửi các heartbeat tới q, và q lưu arrival time vào một sliding window có kích thước cố định WS (1000). Khi có arrival time mới, sẽ tiến hành xóa các arrival time cũ nhất. Ngoài ra còn lưu tổng và tổng các bình phương của arrival time, để tính giá trị bình quân và phương sai của tập arrival time nhanh nhất.
Bước 2: Estimating the distribution and computing
Giả sử rằng arrival time tuân theo phân phối chuẩn (normal distribution).
P(t): Xác suất một heartbeat sẽ tới sau t đơn vị thời gian kể từ message trước đó.
Bước 3: Phi calculation
Ta sẽ tính theo công thức sau:
Tlast: Thời điểm gần nhất nhận được heartbeat.
Tnow: Thời điểm hiện tại.
Khi xác suất nhận được heartbeat tăng lên, giá trị của φ giảm và tiến gần đến 0, và khi xác suất nhận được heartbeat giảm và tiến về 0, giá trị của φ có xu hướng đến vô cùng ∞.
Cho một threshold Φ, giả sử ta sẽ suspect p khi φ > Φ = 1.
Thì khả năng sẽ tạo ra một sai lầm (tức là quyết định sẽ mâu thuẫn trong tương lai do nhận được heartbeat muộn) là 10%. Khả năng xảy ra là khoảng 1% với Φ = 2, và 0,1% với Φ = 3, v.v
Nhóm tác giả đã thực hiện thực nghiệm trên 2 máy tính đặt tại Nhật Bản và Thụy Điển, đồng thời so sánh với các phương pháp của Chen và Bertier (thuộc cùng nhóm adaptive failure detection).
Thiết kế của φ accurial failure detector đáp ứng linh hoạt với điều kiện network thay đổi với bất kỳ số lượng ứng dụng chạy đồng thời.
Quá trình thực nghiệm cũng cho ra kết quả tốt với các tham số được điều chỉnh phù hợp. Trên thực tế, tác động của tham số Window Size là khá đáng kể. So sánh với các failure detector khác cho thấy hiệu suất tương tự và không gây ra chi phí đáng kể.
Phương pháp này đang được ứng dụng tại cassandra và akka.
Link bài báo gốc tại đây.
Góc Lập Trình
Đề ra kỳ này
Cho một list các số nguyên X, từ X1 đến XN ( 1 < N < 100, 1 <= Xi <= 10^9). Chúng ta muốn chúng được sắp xếp theo thứ tự tăng dần, nhưng lại không thể sắp xếp chúng lại! Có nghĩa là không thể sử dụng các thuật toán sắp xếp thông thường.
Lựa chọn của chúng ta lúc này là thay đổi chúng bằng cách thêm các số từ 0 đến 9 vào phía sau. Ví dụ nếu số đó là 10, bạn có thể đổi chúng qua 100 hay 109 với 1 thao tác, hoặc đổi qua 1034 với 2 thao tác (lần lượt thêm 3 và 4 vào phía sau).
Với danh sách cho trước, hãy tìm số thao tác nhỏ nhất để chúng ta có một danh sách sắp xếp theo thứ tự tăng dần.
Ví dụ với list 100, 7, 10, chúng ta sẽ cần 4 thao tác để biến danh sách đã cho thành 100, 748, 1034
Ví dụ: 10, 10 -> cần 1 thao tác để đổi thành 10, 100
Ví dụ: 4, 19, 3 -> cần 2 thao tác để đổi thành 4, 19, 311
Lời giải tuần trước:
Chúng ta có thể bắt đầu từ một phương án brute force, sau đó sẽ tối ưu dần bằng việc bỏ đi các tính toán không cần thiết.
Một giải pháp brute force trong bài này sẽ là duyệt qua tất cả các đường đi có thể và kiểm tra xem có đi tới điểm zero được không. Tuy nhiên nếu ta đã kiểm tra đi được tới một index bất kỳ, chúng ta sẽ không cần kiểm tra nó lại, do đó ta có thể đánh dấu đã đi đến đó.
Đây là một dạng của bài toán tìm đường, vì vậy ta có thể tiếp cận với phương pháp duyệt đồ thị (BFS hoặc DFS).
Nếu ta coi đỉnh là các ô, thì cạnh sẽ nối ô hiện tại tới những ô có thể nhảy tới. Ví dụ: input= [2, 1, 1, 4]. Ta sẽ có 4 đỉnh tương ứng với 4 ô: 0, 1, 2, 3
Từ ô 0, ta có thể nhảy 2 bước tới ô 2, vì vậy ta có thể nối đỉnh 0 tới đỉnh 2.
Time Complexity và Space Complexity là O(N)
Time Complexity và Space Complexity là O(N)
Code & Tools
  • Dhall is a programmable configuration language optimized for maintainability.
  • Kotlin Multiplatform Mobile - Write the business logic for your iOS and Android apps just once, in pure Kotlin
Tin Tức Khác
Từ nay đến hết 11/7, giải đấu lập trình Tiki Hackathon mở đơn đăng ký tham gia với 5 vòng đấu, giải thưởng lên đến 360 triệu đồng, tạo cơ hội để người tham gia xây dựng ứng dụng ngay trên nền tảng mở Tini App được phát triển bởi đội ngũ Tiki. Các bạn nào quan tâm đến cuộc thi có thể theo dõi chi tiết ở đây: link.
This Week Sponsors
10 năm liên tiếp nhận giải thưởng Sao Khuê từ Hiệp hội Phần Mềm VN (VINASA), Top những nơi làm việc tốt nhất Việt Nam do Anphabe vinh danh, Top những nơi làm việc tốt nhất Châu Á do tổ chức HR Asia công nhận,… là những danh hiệu danh giá và xứng đáng mà KMS Technology đạt được trong 12 năm hình thành, xây dựng và phát triển để trở thành một công ty dịch vụ phần mềm với đội ngũ 1000+ con người như hiện nay.
Nếu bạn đang tìm kiếm cơ hội làm việc, phát triển trong các dự án lớn, đồng nghiệp giỏi, môi trường làm việc xịn xò thì đừng bỏ lỡ những vị trí tuyển dụng hot từ KMS bên dưới nhé.
Quotes
The Internet was done so well that most people think of it as a natural resource like the Pacific Ocean, rather than something that was man-made. When was the last time a technology with a scale like that was so error-free?
Alan Kay, in interview with Dr Dobb’s Journal (2012)
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