Sơ lược về các dạng DHT (Distributed Hash Table)

rogp10 · February 4, 2019, 2:14am

Nhắn gửi: Đây là bài về 4 loại DHT. Rất mong được nhận sự góp ý và phản hồi của các bạn. - rogp10

DHT là một hệ thống phân tán dùng để tìm kiếm (siêu) dữ liệu, dựa trên bảng hash table cổ điển. DHT có hai cặp hash:

ID -> địa chỉ IP: mỗi client (còn gọi là node) có một định danh ID riêng để nhận và truyền tin.
HID -> (meta)data: mỗi gói dữ liệu có một fingerprint riêng để nhận dạng, lưu trên client và giữ toàn vẹn dữ liệu.
Mỗi client trong mạng DHT sẽ lưu các HID “lân cận” với ID của nó.

DHT có những mục tiêu cơ bản như sau:

Dữ liệu được phân bố đều về mặt địa lí. (chia tải)
Chỉ cần một (vài) node bất kì để hòa mạng. (phân tán)
Kích thước bảng định tuyến và chi phí tìm kiếm tối đa tăng theo hàm log của số node đang trong mạng. (mở rộng)
Duy trì kết nối luận lí trước sự hòa mạng và rời mạng liên tục. (ổn định)

Sự linh hoạt trong việc chọn node kết nối có thể tăng tốc đồng bộ và thiết lập DHT.

Hàm hash thường được chọn từ 128 bit trở lên để đáp ứng cho hàng chục triệu node (khoảng 59 bit với khả năng đụng là 50%) và gói dữ liệu. Client dùng đặc điểm của nó kèm theo 1 chuỗi ngẫu nhiên (nonce) để hash và tự đặt ID cho mình.

Có ba thao tác chung:

Kiểm tra xem node có ID này còn sống hay không.
Tìm dữ liệu theo HID.
Tìm thông tin của một ID xác định, hoặc những ID lân cận với ID đó.

I. Chord

Không gian ID trong Chord được thiết kế thành vòng tròn kín, với mỗi node đều có node liền trước (pred) và các node đứng sau. Node X trong Chord lưu một bảng “finger table” lưu các cặp (ID, IP) sao cho finger[i] có ID thuộc (X+2^(i-1), X+2^i], nghĩa là X+2 trong slot 1, X+[3…4] slot 2, slot 3 lưu X+[5…8], v.v. cùng với ID liền trước nó (pred) để hỗ trợ thao tác hòa mạng. Đồng thời node X lưu hết thảy các dữ liệu nó biết có HID nằm trong nửa khoảng (pred, X].

pred ====> X ====> finger[1..w]

Tìm HID

Để tìm một HID (get) ta sẽ đi theo slot có nhiều khả năng nhất. Ta sẽ minh họa với vòng 128 slot, HID là 09 (Z/128Z, +)
ID 37: 9 - 37 (= 128+9 - 37) = 100 > 64, slot 7 có máy 103 (< 9).
ID 103: 9 - 103 = 34 > 32, slot 6 có máy 14 > 9, slot 5 có máy 123
ID 123: 9 - 123 = 14 > 8, slot 4 có máy 6 < 9.
ID 6: succ(6) = 10, vậy trả về (10, IP_10) cho ID 37.

Hòa mạng

Hàm succ(ID) dùng để tìm ID của client nằm sau một client cho trước. Để hòa mạng, một client có ID tự đặt là M kết nối với client X trong mạng:

M tự xưng danh với X.
X truy vấn succ(M).
X trả về kết quả succ(M) cùng bảng finger.
M liên lạc với succ(M), ta gọi là M’.
M’ kiểm tra tham số pred của mình

Nếu pred nằm sau M và còn sống thì M’ phải trả về pred. M tiếp nhận M’ này vào bảng finger. (TH1)
Ngược lại M’ báo lại cho pred của mình và cập nhật lại M’.pred = M. M’ trao lại bảng finger của mình cho M. (TH2) Hoặc M’ phải điều chỉnh bảng node của mình (xem phần sau).
(TH2): M hòa mạng thành công. M yêu cầu M’ trao lại các key M’ đang giữ.
(TH1): M liên lạc với pred, hoặc nếu pred không kết nối được thì lại tiếp tục qua bảng finger đã nhận từ X.

Điều chỉnh

Sau một khoảng thời gian, node X xem lại tất cả những kết nối của mình. Có hai thao tác chính:

Gọi succ(pred), nếu bằng X thì thôi, ngược lại yêu cầu cho succ(pred) kiểm tra pred và nhận key, tương tự như khi hòa mạng.
Ping tất cả các ID trong bảng finger để điều chỉnh.

Phát hành

Để đưa một HID mới vào mạng, ta phát yêu cầu succ(HID) qua bảng finger, sau đó yêu cầu ID này lưu HID của ta.

Các thông điệp truyền:

OK: gồm chữ “OK” và ID. NOK tương tự.
START + ID: xưng danh, nhận PAIR và FING.
JOINS + ID: liên lạc với succ(M) để hòa mạng, nhận (OK và FING) hoặc (NOK và PAIR)
PING + ID: trả về OK hay timeout.
FING + PAIRID(s): bảng finger.
SUCC + ID: trả về PAIRID.
LEAVE + ID: gửi cho tất cả liên kết.
STORE + PAIRHID: yêu cầu lưu một HID, trả về OK hay NOK (quá đầy hoặc hash không đúng).
RETK + PAIRHID(s): trả về (những) key mà node đang giữ.

Tóm tắt:

Để tìm một HID h trong Chord, ta cần phải hỏi những máy có ID (nằm sau) h.
Chord khá giống 1 DSLK đơn vòng với b con trỏ: 1, 2, 4, 8, 16, 32, …, 2^(b-1) vì pred không tham gia định tuyến.
Node pred rất quan trọng trong Chord.

rogp10 · March 1, 2020, 3:31am

II. Kademlia

Kademlia là một hệ thống có tính lan truyền cao và độ trễ thấp, cùng những tính chất lí tưởng khác nên rất thông dụng. Kademlia được sử dụng trong giao thức BitTorrent, với các ứng dụng như OpenBitTorrent, uTorrent, Azureus, v.v.
Thay vì sử dụng phép trừ làm khoảng cách như Chord, Kademlia sử dụng phép XOR ⊕ có hai đặc tính ưu việt:

Tính đối xứng: a ⊕ b = b ⊕ a. Hai node chỉ việc điền ID của nhau vào bảng, chứ không đi vòng vèo như Chord.
BĐT tam giác: a ⊕ b + b ⊕ c >= a ⊕ c do a + b >= a ⊕ b (phép cộng có thể xem là phép xor có nhớ)

Do nhu cầu thực tế, ngoài IP client còn phải lưu thêm port, nên cặp (ID, IP) trở thành (ID, IP:port). Kademlia sử dụng ID dài 160 bit, và mỗi client có một dãy bucket để lưu các cặp ID, mỗi bucket gồm tối đa k cặp như vậy. Nguyên tắc chọn ID của Kademlia là: ID càng kết nối lâu càng nhiều khả năng sống lâu, được phát biểu như sau:
Với x.alive(t) là biến cố node x sống tại thời điểm t >= 0s, thì P(x.alive(t + 3600s) | x.alive(t)) >= 1/2 và đơn điệu tăng theo t.

Đại diện cho mỗi bucket là một mặt nạ bit, sao cho các ID trong bucket đều khớp với mặt nạ bit đó, giống như 192 168 1 23 ứng với 192.168.1.0/24 vậy. Điều khác biệt là khi X có một bucket đã đủ túc số và tiếp nhận địa chỉ M phù hợp thì có hai trường hợp sẽ xảy ra:

Nếu X thỏa mặt nạ bit thì bucket sẽ bị chia thành hai nửa: 0 và 1, đưa M vào bucket tương ứng.
Ngược lại, nếu node cũ nhất (last-recently-used, LRU) bị timeout thì sẽ thêm M vào bucket và đá node cũ ra ngoài. Bằng không, X đưa M vào danh sách dự bị cho bucket và ghi nhận node cũ còn sống.
Khi vẽ ra sẽ giống một cây nhị phân.

Dễ thấy rằng mỗi bucket thu hẹp khoảng cách hơn một nửa, nên số thông điệp truy vấn sẽ vào khoảng O(logn) với n là số client trong mạng. Ngoài ra, một client sẽ biết rõ những ID gần mình nhất hơn là những ID xa hơn, đây là đặc trưng của DHT, không chỉ của Kademlia.

Kademlia quy định bốn câu lệnh cơ bản:

PING: kiểm tra node có đang sống hay không.
FIND_NODE + ID: lấy thông tin của ID, hoặc (tối đa) k node gần ID nhất.
STORE + HIDPAIR: lưu (siêu) dữ liệu và HID của nó
FIND_VALUE + HID: trả về (siêu) dữ liệu, hoặc (tối đa) k node gần ID nhất.

Trong truy vấn lặp, chỉ có máy khởi truy vấn hỏi và máy trung gian trả lời bằng ID trung gian tiếp theo, hoặc đích. Ngược lại, với truy vấn đệ quy, máy trung gian thứ k sẽ hỏi máy trung gian tiếp theo, nhận câu trả lời để trả lời lại cho máy trung gian thứ k-1.

Truy vấn lặp: X <-> 1, X <-> 2, X <-> 3, … , X -> goal
Truy vấn đệ quy: X -> 1, 1 -> 2, 2 -> 3, …, n -> n-1, n-1 -> n-2, …, 1 -> X, X -> goal.

Để tìm một ID, X chọn một bucket của mình gần với ID đó nhất và phát truy vấn ID đến α máy cùng lúc trong bucket đó (tham số a này được chọn cẩn thận và α << k). X tiếp nhận tất cả ID trả về vào bucket của mình. X duy trì α (thường là 3) truy vấn chưa trả lời. Nếu không thể tiến gần đến ID hơn nữa, X sẽ phát lookup tới những node còn lại trong kết quả trả về (tối đa α node cùng lúc) và thất bại sau nỗ lực cuối cùng này. Bạn đọc tinh ý sẽ thấy đây chính là quá trình “leo đồi”.

Để hòa mạng, client M xưng danh với client X, gửi FIND_NODE(M) cho X và thực hiện quá trình vừa nêu trên. Sau đó M thực hiện “Làm tươi” những bucket không thể có X trong đó.

Để phát hành (HID, value) X phát lệnh STORE cho bucket gần HID nhất. Một HID được lan truyền bằng cách: nếu một node Y phát hiện Z gần với HID hơn (xor nhỏ hơn) thì Y phát STORE cho Z. Đồng thời, trong quá trình tìm kiếm, ID gần nhất mà không trả lời được sẽ nhận STORE từ ID yêu cầu, nếu tìm được để giảm số yêu cầu trong mạng. Ở đây có hai loại client:

Client loại 1 lưu trữ HID phải phát lệnh STORE sau mỗi khoảng thời gian nhất định.
Client loại 2 chỉ cache tạm HID, sau một khoảng thời gian tùy vào khoảng cách với HID sẽ loại bỏ nó khỏi bộ nhớ, bao gồm tất cả client tiếp nhận STORE ban đầu.

Để duy trì mạng, client tiến hành “làm tươi” các bucket với những bucket đã nguội lạnh bằng cách thực hiện một truy vấn FIND_NODE với một ID ngẫu nhiên ứng với mỗi bucket đó.

Trình bày xong phần Kademlia.

Nói thêm: Dùng truy vấn đệ quy thì các node tham gia sẽ phải duy trì kết nối trong khoảng thời gian dài, và còn dễ bị lợi dụng (amplification) nữa. Nhưng dùng truy vấn lặp thì không phải máy nào cũng liên lạc trực tiếp được.
Với các mạng lưu metadata, có thể cân nhắc cho client loại 2 (ứng với HID cụ thể, không phải role đặc biệt) cũng có thể kích hoạt STORE (phát tán) nhưng vẫn bị hết hạn. Loại 3 (cache) mới không phát tán và chỉ lưu trữ trong thời gian ngắn.
Ngoài ra, các node nên ưu tiên cho những range IP gần mình hơn để hòa mạng và giữ kết nối tốt hơn. Tapestry và Pastry bổ sung bảng neighbor vào để phần nào giải quyết vấn đề này.

rogp10 · March 1, 2020, 3:33am

III. Tapestry

Tapestry và Pastry là hai DHT thuộc họ Plaxton. Mỗi node trong Tapestry có một ma trận định tuyến (gọi tắt là “ma trận”) Mx gồm m dòng [0…m-1] và 2^w cột đánh số [0…2^w - 1].

Dòng thứ i có chung ít nhất w*i bit đầu với ID của node.
Ô Mx[i][j] có bit thứ w*i+1 là j.
Mỗi ô gồm 1 node chính và 2 node dự bị, node có ping thấp nhất làm node chính.

VD: Trong ma trận của node 687, ID 631 sẽ nằm ở dòng 1, cột 3; 682 là dòng 2 cột 2; 793 là dòng 0 cột 7.

Để tìm một node, client so sánh ID với ID đang tìm để tìm cột cho đúng. Nếu ô đó không có ID nào thì dùng những ô lân cận.
VD: lookup(4807): 3622 -> 4931 -> 4824 -> 4806, dòng 3 hết.

Để phát hành một HID, client X xác định node nào có ID “liền sau” (không giống Chord & Pastry, 2999 và 3000 thuộc về hai mạch khác nhau) HID sẽ trở thành root R (hay surrogate) của HID này. Nguyên tắc là 1 HID chỉ được có 1 surrogate, nhưng nhiều client có thể phát hành một HID. Các client trung gian lưu cặp (HID, X) cho đến R thì dừng lại. Để tìm một HID, client phát lệnh tìm kiếm HID cho đến khi gặp một client có cặp (HID, X). Do mỗi ô trong bảng định tuyến có ping thấp nhất cục bộ, nên client tìm được cũng có ping nhỏ nhất.
Các client lưu dữ liệu phải định kì “làm tươi” HID đang giữ, để đảm bảo root không mất.

Để hòa mạng:

Client M liên lạc với client X trong mạng,
X so sánh M với ID X của mình xem M sẽ rơi vào dòng thứ mấy [i]. X trả về dòng tương ứng kèm những dòng phía trên [0…i], và báo cho những node ở những dòng sau [i+1…n-1] để thêm M vào ma trận.
Trên đường tìm ID M, node nào tiếp nhận sẽ trả về dòng ứng với M, đồng thời tranh thủ điền M vào ma trận định tuyến của mình.
Sau cùng, M tìm một node có ID gần nó nhất có thể và yêu cầu nhượng root HID nếu có. Đây là một cách nữa để lan truyền HID. Khi nhượng root thành công, root cũ M’ sẽ trở thành cache và M là root. M’ thông báo cho tất cả ID trong ma trận của mình node M này.

VD: Node 168 chọn node 840 làm bootstrap

Q168: join 168 -> A840: id {273 439 504 667 301 194}
Q168: lookup 168 -> A301: id {184 124}, A667: id {100}
Q168: rank 168 -> A184: id {131 175 154 109 124} A194: {154 109 116 100}
Q168: lookup 168 -> A175: id {167 164}, A116: id {}
Q168: rank 168 -> A167: id {160 164}, A164: id {160 167}.
Q168: knock 168 -> A167: hid {163 839} {163 031} hoặc hid {}
Q168: lookup 163 … (166 không tồn tại)
Q168: reg 166 -> A839: OK A031: OK
Ma trận 168: [tg: chữ mờ là do markdown, không có ý nghĩa gì]

031 194 273 301 439 504 667 ... 839 ...
109 116 124 131 ... 154 ... 175 184 194
160 ... ... ... 164 ... ... 167 168 ...

Khi rời mạng, client gửi m ID (bằng 5 là ổn) từ những dòng thấp nhất để gửi cho tất cả ID ở phía trên dòng đó. Sau đó, nếu client đang là root thì client chọn một ID gần HID nhất trong bảng, yêu cầu tiếp nhận các HID mình đang giữ. Client đáp lại thực hiện như những bước trên.

Để ổn định mạng:

Khi thực hiện bất cứ lệnh nào, nếu gặp một node bị timeout, thì client đặt 1 cooldown ngắn để kết nối lại một lần nữa (second wind). Trong khi đó, client đọc ô tiếp theo có ID.
Nếu một ô đang còn cooldown thì sử dụng node dự bị, khi nào node dự bị timeout thì mới đọc ô tiếp theo.
Client định kì “làm tươi” các ô trống và bỏ qua những ô có ID, trừ những ô có cooldown hết hạn sẽ được ping một lần nữa. Nếu tiếp tục timeout thì xóa và “làm tươi” sao cho đủ túc số.

IV. Pastry

Ngoài ma trận định tuyến đã trình bày ở phần III, mỗi client Pastry còn lưu trữ thêm u node “hàng xóm” (leaf set) ở hai bên ID của mình (giống Chord: khoảng cách tính bằng phép trừ), kèm theo u’ node có ping thấp (neighborhood set). Thường chọn u bằng w hoặc 2w và u’ bằng 8w hoặc 16w.

Tìm node: Pastry sử dụng truy vấn đệ quy, nếu ID cần tìm rơi vào u node trong leaf set thì có thể kết luận ngay; ngược lại, nếu ID ứng với ô trống trong ma trận thì (hiếm) sẽ chọn 1 node trong neighborhood set càng gần ID càng tốt.
Sau đó, nếu ô ứng với ID cần tìm bị timeout thì việc sửa chữa sẽ tiến hành qua việc lookup qua ô tiếp theo.

Hòa mạng: Để client M hòa mạng, M chọn một bootstrap node X gần mình nhất và phát một yêu cầu đặc biệt, có ID của M.

M tiếp nhận neighborhood set của X, vì X cũng gần M.
Mỗi node từ sau đầu X tới cuối M’ (gần M nhất) trao ma trận, leaf set và neighborhood set cho X. [spoiler]Thực ra chỉ cần ma trận và leaf set thì có thể xem là tạm đủ.[/spoiler]
M’ tiếp nhận leaf set của M.
Sau khi tối ưu dựa trên những thông tin thu được, M hồi đáp cho tất cả các node từ sau X tới M’ cả ma trận, leaf set và n. set. M đã hòa mạng thành công.
M phát “hello” cho tất cả các node trong leaf set và n.set của mình.

Duy trì:

Sau mỗi khoảng thời gian d, M kiểm tra leaf set của mình. Những node bị timeout sẽ bị thay bằng cách gửi yêu cầu leaf set tới node xa nhất (khoảng cách lớn nhất) trong leaf set.
Các ô trong ma trận sẽ được thay thế sau mỗi khoảng thời gian d’ > d bằng một node trong neighborhood set để giảm ping.
Cũng sau mỗi khoảng thời gian d’, M kiểm tra lại neighborhood set của mình. Những node bị timeout sẽ bị thay bằng cách gửi yêu cầu đến node được chọn ngẫu nhiên trong neighborhood set.

Đó là phần lõi của Pastry. Phần lưu file được hiện thực bằng một “app” của Pastry gọi là PAST. Ý niệm là một HID được lưu trữ (không chỉ là quản lí như Tapestry) bởi một “surrogate” và toàn bộ leaf set của nó. Điều này làm cho ping thấp hơn, do ID rải đều khắp các vùng địa lí.

Hết phần III và IV.

Ngoài tính bất đối xứng, do khoảng cách giữa các ID không phân bố đều, một số node Chord phải lưu rất nhiều HID vì có khoảng cách với pred lớn hơn bình thường. Kademlia thông dụng hơn hẳn, với phần định tuyến đơn giản, cách chọn kết nối linh động và khoảng cách có tính đối xứng.

Để hiện thực hóa một mạng P2P, ngoài DHT còn có thể dùng hình thức gossip: các node liên lạc và trao đổi liên kết một cách ngẫu nhiên với nhau; thông qua việc tối ưu cục bộ, dữ liệu sẽ tập trung ở các node có băng thông lớn và sống lâu: Việc tạo node và hòa mạng dễ dàng mở ra khả năng tạo ra thật nhiều client phá hoại trong mạng. Những mạng có dùng DHT phải đối mặt với kiểu tấn công đặc trưng: để cô lập một node S, chỉ cần đánh sập S để tất cả kết nối từ S đều bị timeout, sau đó tạo nhiều ID (có thể cùng trên một máy vật lí) gần với S và kết nối với S. Với số node tạo ra lên đến hàng nghìn, node S bị cô lập hoàn toàn. Điều này cực kì nguy hiểm với những ứng dụng tài chính.

Ngoài ra, cấu trúc DHT làm cho việc phục hồi kết nối trong tình huống chia cắt và cô lập bị hạn chế rất nhiều, và tình trạng đó vẫn kéo dài sau khi kết nối tầng thấp hơn được tái lập. DHT có khả năng tìm kiếm nhanh và chọn lọc, nhưng gossip có thể tìm theo từ khóa, thay vì phải tag vào hash. Như vậy, nghiên cứu kết hợp gossip trên nền DHT là hướng thật sự có tiềm năng và lí thú▮

Tài liệu tham khảo

Antony Rowstron, Peter Druschel, Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems, 2001.
Ben Y. Zhao, Ling Huang, et al., Tapestry: A Resilient Global-Scale Overlay for Service Deployment, IEEE Journal on Selected Areas in Communications, Vol. 22(1), 2004.
Eng Keong Lua, Jon Crowcroft, et al., A Survey and Comparison of Peer-to-Peer Overlay Network Schemes, IEEE Communication Surveys and Tutorial, Vol. 7(2), 2005.
Heiko Niedermayer, Simon Rieche, et al., On the Distribution of Nodes in Distributed Hash Tables, 2005.
Ion Stoica, Robert Morris, David Karger, et al., Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, 2001.
Marin Bertier, François Bonnet, et al., D2HT: the best of both worlds, Integrating RPS and DHT. European Dependable Computing Conference, 2010.
Petar Maymounkov, David Mazières, Kademlia: A Peer-to-peer Information System Based on the XOR Metric, 2002.
Yuval Marcus, Ethan Heilman, Sharon Goldberg, Low-Resource Eclipse Attacks on Ethereum’s Peer-to-Peer Network, 2018.

rogp10 · February 4, 2019, 2:16am

Viết lại cho rõ hơn chút về phần Chord