Grapevine: An Exercise in Distributed Computing

Description of Grapevine and its implementation

Grapevine: all-in-one distributed service having:

	DNS service
	Resource locating service
	Authentication and access control service
	Mail service

How to achieve cache consistency in an environment which requires loose consistency

	Maintain recent changes and resolve conflicting ones
	Make applications--mail servers in this paper--cooperate to find and resolve cache inconsistency

Nothing special for us of 21C

	Servers and workstations connected by Ethernet and long distance network (mainly telephone line)
	Both of reliable and unreliable network services

Primary service is mail delivery. Reason? Mail delivery is:

	an important application of distributed computing
	a good test bed for ideas about how to structure distributed systems
	a representative application of store-and-forward messaging

MIME concept: Grapevine does NOT interpret the message content and appropriate client program interprets it

Another services

	Authentication
	Access control: File server may use these two services to grant an access to a file from a client
	Resource location: Please inform me of a printer which can print PDF files

Distribution of programs

	Server programs run on server computers dedicated to Grapevine
	Client programs run on usual workstations

Make the service available to many different clients -> Should not depend on the correct operation of every client -> Do not interpret the content of the message, and let the clients do

Reliable mail delivery with NAK message if something went wrong

No single point of failure

A few minutes of message delivery latency & a few seconds of interactive response. Interactivity is more emphasized than latency

Decentralized administration: adding users, ...

Secure messaging: authentication, encryption, protection of Grapevine database

Registration database maps names (RName) to information about the user, machines, services, distribution lists, and access control list

Two types of entry: individual & group

	Individual: represents a human or a Grapevine server RName of a human or a server Authenticator: password Ordered list of inbox sites: a user can have multiple inbox, thus providing multiple way to get to her Connection site: internet address - usually used only for entry for a server
	Group RName of the group The list of RNames of members -- like a Unix directory Also can be an ACL: for example the list of RNames who can read the file corresponding the RName

accept message (sender, password, recipients = list of individuals and/or groups, body)

	submit the message for delivery
	interesting: password
	returns ok

message polling (individual)

returns non-empty if a message is ready to receive or empty otherwise

retrieve messages (individual, password)

	returns all messages for the individual
	if the client sends OK, server deletes those message from the inbox

authenticate (individual, password)

returns ok or not-ok

membership (name = individual or subgroup, group)

	returns ok if the individual is in the group, otherwise not-ok
	direct membership or membership to transitive-closure of the group

resource location: given input -> output returned

	distribution list -> members of the list
	a service name -> list of servers that provide the service
	individual (server name) -> connection site = internet address
	individual (human) -> list of inbox sites

registration database inquiry & administration functions

RName is the character string in the form of F.R

	R = registry: partitions user community according to organization, geography, or whatever
	F: a unique name within the registry R

Each Grapevine server has both a registration server and a message server

Distribution and replication of registration database

	No registry spans multiple server! That is a server may contain all RNames of the registry or none of them: scalable?
	A registry may be copied into multiple servers

Any server containing the registry may accept changes to the registry and should propagate to appropriate servers

Any message server can accept any message for delivery

Message server responses to message polling and message retrieval for inboxes it contains

Grapevine user package, running on each client machine, performs resource location to choose the right server to contact

a user P.Q, using WS-1, sends a message to X.Y

Client program call delivery function of Grapevine user package on WS-1 -> The user package contacts any registration server and get a valid server which provides message service -> The user package submits the message to the message server. If the server is down, user package uses location service again to get another server -> The message server contacts the registration server(s): Server containing registry Q to authenticate the sender Server containing registry Y to get the members of the group and get the best inbox for X.Y -> The message server forwards the message to the inbox machine

Client for X.Y on WS-2 calls retrieval function of Grapevine user package -> User package contacts a registration server to get inbox sites of X.Y -> User package contacts each inbox machines and requests retrieval -> Each inbox machine contacts a registration server to authenticate X.Y and gives out messages for X.Y

A user P.Q ftps a file Z from a file server

	Grapevine user package contacts a registration server to get the location of the file server
	-> Grapevine user package at file server contacts a registration server to authenticate P.Q and check permission: remember the group as an ACL
	-> ftp occurs

Grapevine as an authentication facility: not bad

Grapevine as a means to partition user community: not bad

Mail to a group and file read permission to the group at the same time: just single group entry used for different purpose

Almost everything has been explained in 3.5. A little more detail:

	User package sends header info: sender RName, password, return RName, list of recipient RNames
	-> Messaging server authenticates sender and checks the validity of each recipient by contacting each registration server and notifies invalid recipients
	-> Messaging server prepares header part of the message: unique message id (time of submission + ip-addr of the server) is added
	-> User package sends the body part
	-> Messaging server completes the accepting process by replying OK

Store-and-forward message delivery occurs

Error message is delivered to "return RName" or the owner of the recipient group

Nothing new from 3.5

Any messaging server for submission

Any inbox server for delivery

Single message gets buffered in an inbox machine

GV registry, i.e. the set of RNames in the form of *.GV

	GV registry is replicated to every registration server
	Each registration server is represented by an RName in GV registry
	A group RName in GV registry corresponds to a registry and has RNames of registration servers containing the registry Mail Registry = MS.GV Ftp Registry = FTP.GV

GV.GV

	The group RName representing GV registry itself
	Members: all registration servers
	=> User package can get the correct registration server for a given RName by contacting any registration server

Each message server has an RName in MS registry

	=> Contact any registration server
	-> Get a registration server address for MS registry
	-> Contact the registration server and get a server in the MS registry
	-> Submit the message to the message server

Group RName in MS registry represents a set of messaging server which can accept a particular kind of message for delivery

Already explained in 3.5, 5.2

Any registration server: *.GV -> Specific registration server -> Get the server information for the service

Streamlined way: Query random registration server about the server info -> if fails, do the full process described above

How can a client find a registration server to start over?

	DNS setup with fixed name (GrapevineRserver)
	Broadcast the lookup packet -> Any registration server responses -> Start initial process

Characteristics of the service Grapevine provides requires a looser definition of consistency: a few minutes of propagation delay is acceptable

Every element in the registration database has a unique id: timestamp + ip-addr

Client compares the id which it caches against that in the server -> if matches, saves time to fetch info from the server

Group entry's member is partitioned into two disjoint lists: active and deleted members list

update an entry: add/delete an entry whose RName matches from active or deleted member list

	delete matching string from active or deleted sublist
	new id produced using the current timestamp
	add (RName, new id) into active (in case of add) or deleted (in case of delete) sublist

merge list: merge the list with the current list in the server based on the timestamp

entry with recent timestamp wins

Why deleted list?

	to handle the out-of-order arrival of update propagation (see 6.3)
	acts as a record of recent events

Administrator may make a change to any of registration servers containing the registry: to find the registration server, the same process as 3.5 is used

The registration server sends an update message to all servers containing the replica of the registry

In the case of conflicting changes, most recent one wins => Every machine should be synchronized :-(

Difference from update: update on an existing RName?

For name creation, earlier creation should win -> Human-level centralization per registry is enough :-(

Meaning of deletion?

Each group has two ACL lists: owners & friends lists

Registration server usually interprets those ACL as:

	any owner can update any entry in the group
	friend can only update her own entry

Client of registration server can interpret those ACL quite differently from the server

	owner of a group in MS registry: receive the message addressed to the group
	friend of a group in MS registry: may send a message addressed to the group

Basically registration server and messaging server uses each other

	Registration server: to propagate updates
	Messaging server: to authenticate a client, ...

However the update to registry is more interwined

If an inbox site is deleted from John's inbox list, the messaging server should get notified so John's message buffered in the server get redelivered to another valid inbox

=> To be general (= to support services other than mail), notification (or callback) list should be added to each database entry

Find an inbox site requires multiple steps and suffers from inefficiency

Each messaging server maintains

	a cache: (recipient, currently preferred inbox site)
	a hint: a list of down server

If possible, use the server in cache which is not in down server list

Cache can be out-of-date due to the registration database change--inbox change will be notified only to the machines in the original inbox list

If a mail gets routed to a wrong server, the receiving server sends 'cache refresh' packet to the sending server

Add an entry to GV registry

Propagate the update to all registration servers

Wait until the propagation has been done and no other update is going on: :-(

Contact any registration server to copy GV registry to the new server by manually: :-(

Remember that each server has (or may have) one registration server and one message server running

Add registration server

	Add an entry to all registration server because GV registry is replicated to every reg. server
	Copy the GV registry replica
	Copy other registry replicas that the server belongs

Add messaging server

	Update to MS registry
	Copy the MS registry replica

Pros

The division of registration service and user service (e.g. mail service)

Cons

	Does registration service have to be as distributed as user services do? I would have a kind of centralized registration service even if I have to have a highly distributed user service Registration service is too tightly coupled with user service Network configuration is dependent to how registration database is configured Adding a server or a service is complicated
	Too big is the propagation delay. Only suitable to services with the same properties as the mail delivery
	Too much indirection