Giả sử bạn có một hệ thống lưu trữ phân tán như bittorrent hoặc ipfs và bạn muốn theo dõi tỷ lệ tải lên/tải xuống (hoặc phản hồi/yêu cầu) của các máy ngang hàng. Tuy nhiên, bạn không muốn sử dụng trình theo dõi tập trung và giữ mọi thứ ngang hàng? Bạn có thể ước lượng tỷ lệ u/d một cách an toàn theo cách phân tán mà không áp đảo hệ thống?
Một suy nghĩ của tôi là sửa đổi HyperLogLog (HLL) bằng sự kết hợp của câu trả lời này: Có thể tạo hệ thống "bằng chứng tải lên" để theo dõi tỷ lệ BitTorrent không?.
Trong hệ thống này, mọi người đều có các cặp khóa công khai/riêng tư và người yêu cầu bao gồm các mã thông báo đã ký cho mỗi Xmb dữ liệu (mỗi mã thông báo dành cho cùng một lượng dữ liệu). Trên mỗi yêu cầu tới một nút khác, nút xử lý sẽ lưu trữ hàm băm của mã thông báo trong một siêu nhật ký bên dưới id người yêu cầu và trả về một mã thông báo phản hồi đã ký mới cùng với phản hồi. Nếu nút xử lý trả về phản hồi tốt, thì người yêu cầu sẽ lưu trữ mã thông báo phản hồi trong một hyperloglog dưới id nhà cung cấp.
Nếu bạn có các đồng nghiệp: p1, p2, p3 và bạn muốn tính tỷ lệ các yêu cầu được thực hiện so với các yêu cầu được cung cấp cho p1, bạn có thể làm như sau:
- P2 và p3 hợp nhất các siêu nhật ký của mã thông báo phản hồi từ p1 vào
hll_1
- p2 và p3 hợp nhất siêu nhật ký của mã thông báo yêu cầu từ p1 vào
hll_2
Tỷ lệ cổ phần là cardinality(hll_1)/cardinality(hll_2)
Để tạo HLL “an toàn”, đối với mỗi HLL “binâ đếm các số 0 ở cuối của hàm băm, hãy ghi lại mã thông báo và chữ ký tạo ra hàm băm có số lượng 0 lớn nhất trên mỗi thùng. Bằng cách này, khi p2 và p3 hợp nhất các HLL của chúng lại với nhau, chúng có thể xác nhận rằng HLL của nhau được tạo từ các mã thông báo đã ký và từ chối nếu các chữ ký không khớp. P1 có thể xem xét các HLL kết hợp và xác nhận rằng chúng đến từ các yêu cầu mà họ đã ký. Điều này sẽ buộc mỗi nút phải chứng minh rằng họ đã nhìn thấy các mã thông báo tạo nên HLL của họ.
tấn công
P1 có thể xác minh p2 và p3 là trung thực bằng cách kiểm tra các HLL được báo cáo của họ. Nếu p2 hoặc p3 báo cáo thiếu phản hồi (họ đã nhận được phản hồi từ p1 nhưng quyết định không đưa nó vào HLL) hoặc báo cáo quá mức yêu cầu (nghĩa là p2 có thể đã nhận được yêu cầu từ p1 nhưng chưa gửi phản hồi) thì P1 có thể chỉ cần chặn họ khỏi bảng định tuyến của nó.
P1 và P2 hoặc P3 có thể thông đồng bằng cách trao đổi mã thông báo mà không thực hiện công việc, vì vậy bạn vẫn cần một số loại dịch vụ trung tâm phát hành JWT để kiểm soát tư cách thành viên của nhóm và tìm kiếm thông đồng.
Một góc tấn công khác là những người yêu cầu có khả năng lọc các yêu cầu của họ và chỉ gửi các yêu cầu không tăng HLL (nghĩa là đảm bảo hàm băm của mã thông báo không có số 0 ở cuối). Để ngăn chặn điều này, bạn có thể yêu cầu mỗi nút thêm một muối vào mã thông báo trước khi nó được băm và chèn vào HLL. Nó cũng sẽ ngăn việc tái sử dụng mã thông báo.
Nén mất dữ liệu
Có vẻ như với HyperLogLogs, bạn chỉ cần giữ bao nhiêu chữ ký tùy mức bạn có thùng để xác minh số lượng rất lớn (hàng tỷ) yêu cầu với độ chính xác hợp lý. Những chữ ký này trong HLL sẽ chiếm nhiều dung lượng nhưng ít dung lượng hơn nhiều so với việc lưu trữ mọi yêu cầu!
Bạn có thể hợp nhất một lượng lớn HLL bằng cách sử dụng một DHT như kademlia để chọn các nút để gửi HLL để bầy có thể báo cáo thông tin về một nút cụ thể đến một địa điểm chung.
Tôi chắc chắn rằng tôi đã bỏ lỡ điều gì đó cơ bản về lý do tại sao điều này không hoạt động hoặc các cách để làm cho nó tốt hơn. Chương trình này có hoạt động hay có cách nào dễ dàng hơn để thực hiện?
