Cách tính toán phân phối (Biểu đồ) của lượng lớn dữ liệu trong một hệ thống phân tán?

Question

Tôi đang xây dựng một hệ thống báo cáo số liệu trên một hạm đội thể hiện chứa hơn 100.000 trường hợp đầu cuối. Đối với bất kỳ yêu cầu nào, mỗi cá thể sẽ có thời gian phản hồi. Và điều tôi cần là phân phối thời gian phản ứng của mọi loại yêu cầu trên toàn bộ hạm đội. Ví dụ: [Percentile 50, Percentile 90, Percentile 99, Percentile99.9 ...] của [requestType1, requestType2 ... requestType1000].

Mỗi trường hợp sẽ thu thập thời gian phản hồi diễn ra bên trong. Vì vậy, trong một phút, một ví dụ thu thập trong bộ nhớ là danh sách thời gian đáp ứng của tất cả các loại requestTypes. Ví dụ requestType1 - [1, 2, 3, 4, 1, 2], requestType2 - [2, 2, 3, 2, 1] ...... Vì vậy, những gì tôi cần làm là xử lý các dữ liệu và sản xuất kết quả cuối cùng.

Tôi đã thử nhiều thiết kế, điểm đau chính của tôi là kích thước lớn của các điểm dữ liệu tôi thu thập được từ mỗi requestType duy nhất và chi phí liên lạc giữa các phiên bản. Tôi sẽ giải thích thiết kế hiện tại của tôi dưới đây, nhưng tôi cũng muốn biết nếu có thiết kế tốt hơn hoặc một số thuật toán ưa thích có thể tổng hợp biểu đồ?

Hiện tại, câu trả lời hứa hẹn nhất là: Mỗi phiên bản đầu cuối sẽ gửi dữ liệu của họ đến một trường hợp ngẫu nhiên của một hạm đội thể hiện ở giữa. Trong hạm đội hạng trung này, mỗi trường hợp sẽ tổng hợp tất cả các điểm dữ liệu mà nó đạt được trong một khoảng thời gian ngắn, ví dụ: 5 giây. (Nó không có đủ bộ nhớ để giữ lâu hơn). Sau đó, thể hiện ở giữa lớp sẽ phân phối dữ liệu tổng hợp theo giá trị băm của các requestTypes tới các bản sao lưu. Điều đó có nghĩa là tất cả các thể hiện ở giữa lớp sẽ gửi các datapoints của cùng một requestTypes đến cùng một cá thể back-end. Sau đó, trong trường hợp back-end, tôi có thể sử dụng bộ chứa biểu đồ của bên thứ ba (biểu đồ CodaHale hoặc HDrHistogram) để tính P50, P90, P99 của các điểm dữ liệu đến ... Lý do tôi cần hạm đội trung cấp đang gửi dữ liệu từ phía trước trường hợp cuối là tốn kém, vì vậy tôi muốn tất cả dữ liệu của nó được gửi cùng một lúc, nhưng không thực hiện 100 cuộc gọi để gửi đến 100 trường hợp back-end khác nhau.

Vấn đề chính tôi có thể nghĩ về thiết kế này là độ phức tạp tương đối cao, và nếu một ví dụ ngược xuống, tôi có thể mất tất cả dữ liệu của một số requestTypes. Vì vậy, đối với phần thiết kế hệ thống, ai cũng có một số ý tưởng tốt hơn?

Cách khác tôi đang nghĩ là tìm một thuật toán ưa thích để tổng hợp các biểu đồ hiện có. Thiết kế ở trên, dữ liệu tôi nhận được sẽ chính xác 100%. Nhưng thực ra tôi có thể chịu đựng một số sai lầm. Ví dụ trong biểu đồ của CodaHale và HdrHistogram, tôi chắc chắn rằng họ thực sự không lưu tất cả các điểm dữ liệu, nhưng áp dụng một số thuật toán toán học nâng cao để có được kết quả chính xác tương đối cao với chi phí rất thấp. Và tôi có thể sử dụng thư viện Histogram trong các phiên bản front-end hoặc mid-layer. Nhưng vấn đề là mặc dù tôi có thể nhận được [P50, P90, P99 ...] của mỗi phiên bản front-end instance hoặc mid-layer instance với chi phí thấp, tôi không thể tìm cách tổng hợp chúng. Bởi vì các thể hiện front-end khác nhau có thể xử lý các loại yêu cầu khác nhau, và việc phân phối các yêu cầu đến các thể hiện front-end không xác định, vì vậy chỉ cần tính toán giá trị trung bình của ALL P50, P90, P99 sẽ có rất nhiều thiếu chính xác. Vì vậy, có ai có ý tưởng, làm thế nào tôi có thể tổng hợp nhiều biểu đồ CodaHale hoặc HDrHistogram với nhau? Hoặc có bất kỳ thuật toán nào có thể giúp tổng hợp biểu đồ thành một?

============================================= ===========================

Tôi có một số ý tưởng mới tối qua. Vì P50 và P90 đang đo lường "trung bình" của tất cả dữ liệu, tôi nghĩ đơn giản áp dụng mức trung bình có trọng số trên tất cả P50 và P90 được tính toán trong mỗi trường hợp giữa lớp phải đủ tốt. Nhưng P99, P99.9 và P99.99 đang đo lường những dữ liệu bên ngoài, do đó, trung bình P99 của tập con có thể không chính xác.Tuy nhiên, nếu giả sử dữ liệu trong thể hiện lớp giữa phân bố tương đối ngẫu nhiên, tôi có thể nhận được 5% dữ liệu trên cùng trong mỗi thể hiện lớp giữa và gửi chúng đến back-end. 5% của mỗi datapoints giữa lớp với nhau là 5% của datapoints tổng thể. Và tôi tự tin hơn, rằng P80 của 5% dữ liệu này gần với P99 của dữ liệu tổng thể, P98 của 5% dữ liệu này gần với P99.9 dữ liệu tổng thể và P99.8 của 5% dữ liệu gần với P99 .99 của dữ liệu tổng thể.

Tôi hy vọng theo cách này, tôi chỉ có thể chuyển 5% dữ liệu tổng thể, nhưng có kết quả chính xác cao. Bạn nghĩ gì về cách này? thiết kế

Answer 1

hệ thống:

Nếu cuộc gọi rất tốn kém thì có lẽ bạn có thể truyền dữ liệu? Tôi không thấy lợi ích thực sự của tầng giữa này trong mô tả của bạn - tại sao frontend-> chi phí cuộc gọi trung bình thấp hơn frontend-> backend?

Nếu bạn lo lắng về mất dữ liệu bạn có hai lựa chọn:

• gửi các sự kiện với nhiều nút. Nhưng bạn sẽ cần phải bằng cách nào đó tránh trùng lặp khi xử lý chúng.
• viết tất cả mọi thứ vào một log dai dẳng (Kafka có thể làm công việc ở đây)

Tất cả phụ thuộc vào số lượng các sự kiện (1/min/frontend hoặc 10k/s/frontend) và khoảng cách giữa các lối vào và chương trình phụ trợ (cùng trung tâm dữ liệu hoặc thiết bị di động -> trung tâm dữ liệu?).

Nếu đó là cùng một trung tâm dữ liệu bạn có thể liên lạc với chương trình phụ trợ qua nhật ký liên tục - điều này giải quyết được vấn đề mất dữ liệu. Nếu có rất nhiều sự kiện mà bạn có thể kết hợp chúng vào frontend và đẩy uẩn hạ lưu

Aggregation:

Có những thuật toán khác nhau, ví dụ q-digest, t-digest. Xem Quantiles over Data Streams: An Experimental Study

Nó cũng đáng chú ý là HdrHistograms can be combined