毕设英译汉原文 协作数据共享系统的可靠存储和(4)

at the node whose hashed IP address lies ahead of them on the ring;in Pastry the keys are placed at the node with nearest hash value.The Pastry scheme is visualized in Figure2(a).Both of these approaches can determine the range a node“owns,”given its ID and the IDs of its neighbors.These schemes are optimized for settings with large numbers of nodes,and assume the nodes will be more or less uniformly distributed across the ring.Each node maintains information about the position of a limited number of its neighbors,as it has a routing table with a number of entries logarithmic in the membership of the DHT.When there are only dozens or hundreds of nodes, we often see highly nonuniform distributions of values among the peers.Indeed,in thefigure,nodes n3and n4are together

responsible for more than3

4of the key space,while node n2

is only responsible for1

16

of it.

Our substrate adopts Pastry’s routing approach for large numbers of peers(with an expanded routing table,as discussed later in this section).However,for smaller numbers of peers, we support an alternative solution that provides more uniform data distribution(which we use for the experiments in this paper).We divide the key space into evenly sized sequential ranges,one for each node,and assign the ranges in order to the nodes,sorted by their hash ID.Such an assignment for the same network we examined for Pastry-style routing is shown in Figure2(b);it distributes the key space,and therefore the data,uniformly among the nodes.In principle, we could also use many virtual nodes at each physical node to better distribute the key space.However,it is advantageous to assign a single contiguous key range to each node;in addition to reducing the size of the routing table,this improves data retrieval performance,as discussed in Section IV.In response to node arrival or failure,we redistribute the ranges over the new node set.We consider the implications of this when we describe node arrival and departure later in this section.

B.Data Retrieval

As mentioned above,a traditional DHT node maintains a routing table with only a limited number of entries(typically logarithmic in the number of nodes).This reduces the amount of state required,enabling greater scale-up,but requires mul-tiple hops to route data.Recent peer-to-peer research has shown[13]that storing a complete routing table(describing all other nodes)at each node provides superior performance for up to thousands of nodes,since it provides single-hop communication in exchange for a small amount of state;we therefore adopt this approach.Our system requires a reliable, message-based networking layer connection withflow control. We found experimentally that,for scaling at least to one hundred nodes,maintaining a direct TCP connection to each node was feasible.With the use of modern non-blocking I/O, a single thread easily supports hundreds or thousands of open connections.For larger networks,a UDP-based approach could be developed to avoid the overhead of maintaining TCP’s in-order delivery guarantees,as all of the techniques in this paper are independent of message ordering.

C.Node Arrival and Departure

Traditional DHTs deal with node arrival and departure through background replication.Each data item is replicated at some number of nodes(known as the replication factor).

In Pastry,for example,for a replication factor r,each item is replicated at

r

2

nodes clockwise from the node that owns it, and the same number counterclockwise from it,leading to r total copies.In the ring of Figure2(a),if r=3,each data item that is owned by node n1will be replicated to n4and n2as well.When a node joins,background replication slowly brings all data items that a node owns to it,as they must be stored at one of its neighbors.If a node leaves,each of its neighbors already has a copy of the data that it owned,so they are ready to respond to queries for data stored at the departed node.

This approach makes an implicit assumption that all of the state at the nodes is stored in the DHT,and therefore that any node that has a copy of a particular data item can handle requests for it.If a node joins or fails,certain requests will suddenly be re-routed to different nodes,which are assumed to provide identical behavior(and hence do not get notified of this change).This does not work in the case of a distributed query processor,where in addition to persistent stored data there may be distributed“soft state”that is local to a query and is not replicated;this includes operator state,such as the intermediate results stored in a join operator or an aggregator.

If data for a particular range is suddenly rerouted from one node to another,tuples might never“meet up”with other tuples they should join with,or data for a single aggregate group may be split across multiple nodes,causing incorrect results.

To solve this problem,our system works on snapshots of the routing table.When a participant initiates a distributed computation,it sends out a snapshot of its current routing table,which all nodes will use in processing this request.

Therefore,if a new node joins in mid-execution,it does not participate in the current computation(otherwise it may be missing important state from messages prior to its arrival).If

a node fails,the query processor can detect what data was

owned by the failed node,and thus can reprocess this state (this is discussed in Section V-D).

Our system must still handle replication of base data, which is done in a manner very similar to that of Pastry;

each data point is replicated at

r

2

nodes clockwise and counterclockwise from the node that owns it.This ensures that data can survive multiple node failures,and that in the event of a node failure,the nodes that take over for a failed node have copies of the base data for the …… 此处隐藏：4408字，全部文档内容请下载后查看。喜欢就下载吧 ……