A. D. Birrel, R. Levin, R. M. Needham, M. D. Schroeder @ Xerox
CACM April 1982, 260-274
![]() |
Description of Grapevine and its implementation |
||||||||
![]() |
Grapevine: all-in-one distributed service having:
|
||||||||
![]() |
How to achieve cache consistency in an environment which requires loose consistency
|
![]() |
Nothing special for us of 21C
|
![]() |
Primary service is mail delivery. Reason? Mail delivery is:
|
||||||
![]() |
MIME concept: Grapevine does NOT interpret the message content and appropriate client program interprets it |
||||||
![]() |
Another services
|
||||||
![]() |
Distribution of programs
|
![]() |
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
|
![]() |
accept message (sender, password, recipients = list of individuals and/or groups, body)
|
||||||||
![]() |
message polling (individual)
|
||||||||
![]() |
retrieve messages (individual, password)
|
||||||||
![]() |
authenticate (individual, password)
|
||||||||
![]() |
membership (name = individual or subgroup, group)
|
||||||||
![]() |
resource location: given input -> output returned
|
||||||||
![]() |
registration database inquiry & administration functions |
![]() |
RName is the character string in the form of F.R
|
![]() |
Each Grapevine server has both a registration server and a message server |
||||
![]() |
Distribution and replication of registration database
|
||||
![]() |
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
|
||||||||||||||||||||||
![]() |
A user P.Q ftps a file Z from a file server
|
![]() |
Grapevine as an authentication facility: not bad |
||
![]() |
Grapevine as a means to partition user community: not bad
|
![]() |
Almost everything has been explained in 3.5. A little more detail:
|
![]() |
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.GV
|
![]() |
Each message server has an RName in MS registry
|
||||||||
![]() |
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
|
||||
![]() |
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?
|
![]() |
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
|
||||||
![]() |
merge list: merge the list with the current list in the server based on the timestamp
|
||||||
![]() |
Why deleted list?
|
![]() |
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:
|
||||
![]() |
Client of registration server can interpret those ACL quite differently from the server
|
![]() |
Basically registration server and messaging server uses each other
|
||||
![]() |
However the update to registry is more interwined
|
||||
![]() |
=> 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
|
||||
![]() |
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
|
![]() |
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 messaging server
|
![]() |
Pros
|
||||||||||||
![]() |
Cons
|