CSE 486 - Distributed Hash Table

这个项目中，我们要为一种名为 k-DHT 的分布式数据结构实现一个路由表，这种数据结构类似于分布式哈希表 Kademlia。它不如完整的 Kademlia DHT 协议稳健和复杂，但它将有助于加深学生对分布式哈希表、分布式数据结构、通信模式以及对等架构的理解。

1 Getting Started

First, read Kademlia: A Peer-to-peer Information System based on the XOR Metric [1]. Pay special attention to Section 2 of that document, which describes the routing table structure and the interactions of the data structure as nodes are added and removed.

Next, read this handout and all of the given code carefully. The given code contains numerous comments and some tests that will help you understand the requirements of this project. In particular, the tests in the directory tests/ in the given code are tests for the public API of the routing table, and demonstrate how it will be used.

Pay special attention to the figures in this section, as they will help you understand the structure of the routing table. Note that, while the routing table is repeatedly described as a tree (and it is a tree!), it can also be thought of as a particular division of the key space into logarithmically decreasing partitions surrounding the local node’s own key. At each partitioning, the remaining key space is divided in half, until the node is alone in its own “bucket” of the key space. While this forms a tree, it is a tree with nodes representing non-overlapping portions of the key space, and so you will probably want to represent it in your implementation as an array or list. Keep this in mind when reading the paper, and it may help to understand the requirements.

Notice that some data structures used in the routing table (such as kdht.NodeInfo) are defined in messages.proto and require building the Protobuf definitions. Running make in the top-level directory of the given code should build the Protobuf implementation (as well as update go.sum).

2 Requirements

You must implement the api/kdht.RoutingTable API in the given code of this project. Note that the given code includes another API, api/kdht.Node, which you will not need to implement yet. You may find it helpful to read the comments for that API to put your routing table in context, however.

You must use the same version of Go and the Protobuf external package for this project as you did for the previous project. You may not use any other external packages, although any package in the Go standard libraries is acceptable. (This corresponds approximately to allowing any package that does not begin with a domain name.)

Your implementation of the API will conform to the description of the Kademlia API in the original Kademlia paper [1], with a few simplifying differences. When in doubt, consult the paper! It is difficult to understand at first, but a few read-throughs of Section 2 (in particular) and some careful drawings will make things clearer.

There are no specific requirements for the method in which you implement the routing table or the data structures that you use, but your implementation should be reasonably efficient. In particular, if a very large number of nodes are placed into your routing table, your implementation must be able to find any given node in the table in time logarithmic in the size of the key space. If you do not meet this requirement, you may find that some tests time out and fail when your project is graded. No sophisticated analysis of algorithms or

data structures is required to meet this requirement; if you follow this handout and the Kademlia paper, your implementation’s performance will be satisfactory.

Your implementation of this API must not produce any output on standard output (os.Stdout in Go, used by default for certain output operations).

咨询 Alpha 小助手，获取更多课业帮助。