DistOS 2014W Lecture 18 - Revision history

Eapache: /* Tapestry: */

2014-04-24T14:41:51Z

Tapestry:

← Older revision		Revision as of 14:41, 24 April 2014
Line 33:		Line 33:
	Tapestry was built for Oceanstore. Oceanstore was built for the open internet. Nodes would be constantly added and removed. Chances are, the network topology would change. That's why you'd need a dynamic routing system.		Tapestry was built for Oceanstore. Oceanstore was built for the open internet. Nodes would be constantly added and removed. Chances are, the network topology would change. That's why you'd need a dynamic routing system.

	* Decentralized and ~~P2P~~. ~~Self organizing~~.		In Tapestry, every object and node is identified by a UUID. The system is entirely distributed, decentralized and peer-to-peer. Each node stores a routing table of its various neighbours by the prefix of their UUID. This lets routing occur digit by digit, effectively turning lookup into the traversal of a distributed [https://en.wikipedia.org/wiki/Radix_tree Radix tree].
	* Distributed.
	* Simple key-value store.
	* look up table contains : key and value
	* DNS as tree but Tapestry as hercically structured.		* DNS as tree but Tapestry as hercically structured.
	* How does the information flow? Each node has a neighbour table which that contains the neighbour's number.		* How does the information flow? Each node has a neighbour table which that contains the neighbour's number.

Cdelahou: Added more Tapestry stuff. Cleaned up the page.

2014-04-19T02:01:39Z

Added more Tapestry stuff. Cleaned up the page.

← Older revision		Revision as of 02:01, 19 April 2014
Line 15:		Line 15:
	the hash table, as opposed to a full replica. They don't know exactly which other node is responsible for a given key. This has given rise to a number		the hash table, as opposed to a full replica. They don't know exactly which other node is responsible for a given key. This has given rise to a number
	of different routing techniques:		of different routing techniques:
	* A centralized server may maintain a list of all keys and associated nodes at which the value can be found. This method involves a single point of failure.		* A centralized server may maintain a list of all keys and associated nodes at which the value can be found. This method involves a single point of failure.
	** eg. Napster		** eg. Napster
	* Flooding: Each node may query all connected nodes. This method has performance and scalability shortcomings but had the benefit of being decentralized.		* Flooding: Each node may query all connected nodes. This method has performance and scalability shortcomings but had the benefit of being decentralized.
	** eg. Gnutella		** eg. Gnutella
	* [http://en.wikipedia.org/wiki/Consistent_hashing Consistent Hashing] The keyspace can be partitioned such that nodes will maintain the values for keys that hash to similar indices (e.g., within a certain hamming distance). Given a query, nodes do not know specifically on which node a key is located, but they do know a few nodes (a proper subset of the network) located "closer" to the key. The query then continues onto the closest node.		* [http://en.wikipedia.org/wiki/Consistent_hashing Consistent Hashing] The keyspace can be partitioned such that nodes will maintain the values for keys that hash to similar indices (e.g., within a certain hamming distance). Given a query, nodes do not know specifically on which node a key is located, but they do know a few nodes (a proper subset of the network) located "closer" to the key. The query then continues onto the closest node. This seems to be the most popular technique for DHTs. It's biggest benefit is that nodes can be added and removed without notifying every other node on the network.
	** eg. Tapestry		** eg. Tapestry

Line 29:		Line 29:
	Routing is performed in such a way that nodes are aware of their ''distance''		Routing is performed in such a way that nodes are aware of their ''distance''
	to the object being queried. Hence objects can be located with low latency		to the object being queried. Hence objects can be located with low latency
	without the need to migrate actual object data between nodes~~. Tapestry has been used in some academic applications such as OceanStore~~.		without the need to migrate actual object data between nodes.

	**Tapestry		Tapestry was built for Oceanstore. Oceanstore was built for the open internet. Nodes would be constantly added and removed. Chances are, the network topology would change. That's why you'd need a dynamic routing system.
	* Distributed .
			* Decentralized and P2P. Self organizing.
			* Distributed.
	* Simple key-value store.		* Simple key-value store.
	* using DHT ( distributed hash table).
	* look up table contains : key and value		* look up table contains : key and value
	* DNS as tree but Tapestry as hercically ~~structure~~.		* DNS as tree but Tapestry as hercically structured.
			* How does the information flow? Each node has a neighbour table which that contains the neighbour's number.
			** From initialization, each node has a locally optimal routing table that it maintains
			** Routing happens digit by digit

	**More dtails about Tapestry:		* Tapestry API:
	** ~~how the information flow?~~		** have four operations called PublishObject, UnpublishObject, RouteToObject, RouteToNode.
	* each ~~nod~~ has ~~neighbour table which that contains the node neighbour number~~.		** each node has ID and each endpoint object has a GUID (Globally unique identifier).

	** Tapestry ~~API:~~		* Tapestry look like operating system.
	* ~~have four operations called~~		** it has two models,one is built on UDP protocol and the other on TCP protocol.
	* ~~each node~~ has ID and ~~each endpoint has GUID (Globally unique identifier)~~.

	**Tapestry look like operating system.		Fun fact, it is now called [http://current.cs.ucsb.edu/projects/chimera/ Chimera].
	* it ~~has two models,one~~ is ~~built on UDP protocol and the other on TCP protocol~~.

Cdelahou: Added info about DHT's and tapestry

2014-04-19T01:31:05Z

Added info about DHT's and tapestry

← Older revision		Revision as of 01:31, 19 April 2014
Line 1:		Line 1:
			==Distributed Hash Tables (March 18)==

			* [http://en.wikipedia.org/wiki/Distributed_hash_table Wikipedia's article on Distributed Hash Tables]
			* [http://pdos.csail.mit.edu/~strib/docs/tapestry/tapestry_jsac03.pdf Zhao et al, "Tapestry: A Resilient Global-Scale Overlay for Service Deployment" (JSAC 2003)]


	== Distributed Hash Table Overview ==		== Distributed Hash Table Overview ==

Line 4:		Line 10:
	distributed across many nodes in a network. Keys are hashed to generate the		distributed across many nodes in a network. Keys are hashed to generate the
	index at which the value can be found. Depending on the nature of the hash		index at which the value can be found. Depending on the nature of the hash
	function, only exact queries may be returned. ~~Each~~ node has a partial view of		function, typically, only exact queries may be returned.
	the hash table, as opposed to a full replica. This has given rise to a number
	of different ~~search~~ techniques:		Usually, each node has a partial view of
	* A centralized server may maintain a list of all keys and associated nodes at which the value can be found. This method involves a single point of failure.		the hash table, as opposed to a full replica. They don't know exactly which other node is responsible for a given key. This has given rise to a number
	* Each node may query all connected nodes. This method has performance and scalability shortcomings		of different routing techniques:
	* The keyspace can be partitioned such that nodes will maintain the values for keys that hash to similar indices (e.g., within a certain hamming distance). ~~This method~~ is ~~not suitable for all applications~~, ~~as it involves bandwidth-intensive migration~~ of ~~data stored in~~ the ~~DHT~~.		* A centralized server may maintain a list of all keys and associated nodes at which the value can be found. This method involves a single point of failure.
			** eg. Napster
			* Flooding: Each node may query all connected nodes. This method has performance and scalability shortcomings but had the benefit of being decentralized.
			** eg. Gnutella
			* [http://en.wikipedia.org/wiki/Consistent_hashing Consistent Hashing] The keyspace can be partitioned such that nodes will maintain the values for keys that hash to similar indices (e.g., within a certain hamming distance). Given a query, nodes do not know specifically on which node a key is located, but they do know a few nodes (a proper subset of the network) located "closer" to the key. The query then continues onto the closest node.
			** eg. Tapestry

	===Tapestry:===		==Tapestry:==
	Tapestry is an overlay network which makes use of a DHT to provide routing for		Tapestry is an overlay network which makes use of a DHT to provide routing for
	distributed applications. Similar to IP routing, not all nodes need to be		distributed applications. Similar to IP routing, not all nodes need to be

Askillen: /* Distributed Hash Table Overview */

2014-03-18T15:26:17Z

Distributed Hash Table Overview

← Older revision		Revision as of 15:26, 18 March 2014
Line 18:		Line 18:
	Routing is performed in such a way that nodes are aware of their ''distance''		Routing is performed in such a way that nodes are aware of their ''distance''
	to the object being queried. Hence objects can be located with low latency		to the object being queried. Hence objects can be located with low latency
	without the need to migrate actual object data between nodes.		without the need to migrate actual object data between nodes. Tapestry has been used in some academic applications such as OceanStore.

	**Tapestry		**Tapestry

Askillen: /* Tapestry: */

2014-03-18T15:24:05Z

Tapestry:

← Older revision		Revision as of 15:24, 18 March 2014
Line 18:		Line 18:
	Routing is performed in such a way that nodes are aware of their ''distance''		Routing is performed in such a way that nodes are aware of their ''distance''
	to the object being queried. Hence objects can be located with low latency		to the object being queried. Hence objects can be located with low latency
	without the need to migrate actual object data between nodes~~. It would be interesting~~		without the need to migrate actual object data between nodes.
	~~to see if Tapestry could be adapted for anonymity similar to ant-colony routing~~
	~~schemes~~.

	**Tapestry		**Tapestry

Askillen: /* Distributed Hash Table Overview */

2014-03-18T15:14:29Z

Distributed Hash Table Overview

← Older revision		Revision as of 15:14, 18 March 2014
Line 7:		Line 7:
	the hash table, as opposed to a full replica. This has given rise to a number		the hash table, as opposed to a full replica. This has given rise to a number
	of different search techniques:		of different search techniques:
	* A centralized server may maintain a list of all keys and associated nodes		* A centralized server may maintain a list of all keys and associated nodes at which the value can be found. This method involves a single point of failure.
	at which the value can be found. This method involves a single point of failure.		* Each node may query all connected nodes. This method has performance and scalability shortcomings
	* Each node may query all connected nodes. This method has performance and		* The keyspace can be partitioned such that nodes will maintain the values for keys that hash to similar indices (e.g., within a certain hamming distance). This method is not suitable for all applications, as it involves bandwidth-intensive migration of data stored in the DHT.
	scalability shortcomings
	* The keyspace can be partitioned such that nodes will maintain the values
	for keys that hash to similar indices (e.g., within a certain hamming distance).
	This method is not suitable for all applications, as it involves
	bandwidth-intensive migration of data stored in the DHT.

	===Tapestry:===		===Tapestry:===

Hariz at 15:13, 18 March 2014

2014-03-18T15:13:54Z

← Older revision		Revision as of 15:13, 18 March 2014
Line 43:		Line 43:

	**Tapestry look like operating system.		**Tapestry look like operating system.
			* it has two models,one is built on UDP protocol and the other on TCP protocol.

Askillen at 15:10, 18 March 2014

2014-03-18T15:10:27Z

← Older revision		Revision as of 15:10, 18 March 2014
Line 1:		Line 1:
	== Distributed Hash Table Overview ==		== Distributed Hash Table Overview ==

	A Distributed Hash ~~Tables~~ (DHT) is a fast lookup structure of <key,value> pairs,		A Distributed Hash Table (DHT) is a fast lookup structure of <key,value> pairs,
	distributed across many nodes in a network. Keys are hashed to generate the		distributed across many nodes in a network. Keys are hashed to generate the
	index at which the value can be found. Depending on the nature of the hash		index at which the value can be found. Depending on the nature of the hash

Askillen at 15:09, 18 March 2014

2014-03-18T15:09:49Z

← Older revision		Revision as of 15:09, 18 March 2014
Line 1:		Line 1:
			== Distributed Hash Table Overview ==

			A Distributed Hash Tables (DHT) is a fast lookup structure of <key,value> pairs,
			distributed across many nodes in a network. Keys are hashed to generate the
			index at which the value can be found. Depending on the nature of the hash
			function, only exact queries may be returned. Each node has a partial view of
			the hash table, as opposed to a full replica. This has given rise to a number
			of different search techniques:
			* A centralized server may maintain a list of all keys and associated nodes
			at which the value can be found. This method involves a single point of failure.
			* Each node may query all connected nodes. This method has performance and
			scalability shortcomings
			* The keyspace can be partitioned such that nodes will maintain the values
			for keys that hash to similar indices (e.g., within a certain hamming distance).
			This method is not suitable for all applications, as it involves
			bandwidth-intensive migration of data stored in the DHT.

			===Tapestry:===
			Tapestry is an overlay network which makes use of a DHT to provide routing for
			distributed applications. Similar to IP routing, not all nodes need to be
			directly connected to each other: they can query a subset of neighbours for
			information about which nodes are responsible for certain parts of the keyspace.
			Routing is performed in such a way that nodes are aware of their ''distance''
			to the object being queried. Hence objects can be located with low latency
			without the need to migrate actual object data between nodes. It would be interesting
			to see if Tapestry could be adapted for anonymity similar to ant-colony routing
			schemes.

	**Tapestry		**Tapestry
	* Distributed .		* Distributed .

Hariz at 15:06, 18 March 2014

2014-03-18T15:06:49Z

← Older revision		Revision as of 15:06, 18 March 2014
Line 13:		Line 13:
	* have four operations called		* have four operations called
	* each node has ID and each endpoint has GUID (Globally unique identifier).		* each node has ID and each endpoint has GUID (Globally unique identifier).

			**Tapestry look like operating system.