membership

README

Distributed Group Membership Service

Our distributed group membership service places each member in the group on an extended virtual ring sorted by their IDs. An member's ID consists of its IP address and join time. Each member keeps a complete group membership list but can only directly communicate with some of its close neighbors on the ring.

Join and leave

There is one fixed contact process that acts as the introducer and all potential members know about. When a new member wants to join the group, it sends a join request to the introducer, which then sends the current membership list back and disseminates the new node join information. During the time the introducer is down, no new member can join the group. When a member wants to leave the group, it disseminates its leave information. Each member will update its membership list upon receiving a join/leave message.

Failure detection

Each member in the group sends one heartbeat message per second to its three closest successors on the ring. A member is marked as failed and removed from the membership list if any of its heartbeat receiver fails to receive its heartbeat message for 4 s. A node fail message will be disseminated and each member will update its membership list upon receiving a node fail message. As there can be at most three simultaneous failures in the group, if a node fails, its three heartbeat receivers cannot all fail, and its failure must be reported. Furthermore, assuming synchronous clock in the group, it is guaranteed that a machine failure must be reflected within 5 s, for the maximum possible delay of detecting a node's failure takes place when a node fails as soon as it acks a ping, and it takes at most 1 s before the next ping to it is sent, and another 4 s to wait for timeout, which is a total of 5 s. We can also decrease the timeout to achieve a faster fail detection, while the trade-off is higher false positive rate in a lossy network.

Introducer election

When the introducer leaves or fails, a new introducer will be elected. Since our system is operated on virtual machines cluster provided by the university, we assume that the network is synchronous. The election is done via using the Bully algorithm.

Dissemination of messages

The membership update (join/leave/fail) messages are sent to its four closest successors. If a successor finds the message already received, it stops relaying it, otherwise it further sends the message to its four closest successors. By using our protocol for a ten-node group, it takes only 3 rounds of relaying to have one message sent from a node received by all nodes, and it is guaranteed that node failure can be reflected in at least one membership list within 5 s regardless of network latency. Assuming small network latency, a membership update can be reflected within 6 s at all membership lists at high probability.

Marshaled message format

Our message are all encoded in UTF-8 string, which has a fixed byte order and is endianness independent. Each message consists of a message type (join/leave/fail/ping/ack), and a payload. For join/leave/fail, the payload is just the id of the newly joined/left/failed node. For ping/ack, the payload is empty string.

Scalability

The design can easily be scaled up to large N. In our protocol, every node only sends heartbeat to a fixed number of targets. During dissemination of any type of message, each node only forwards the message to a fixed number of its neighbors. Such design avoids the issue of single point failure of multicast or broadcast. In addition, it also solves the problem of message load explosion of all-to-all communication by distributing the message load evenly to every node.

Documentation

Index

• Constants
• type MembershipList
• type MembershipService
  • func (ms *MembershipService) GetMembershipList() []string
  • func (ms *MembershipService) JoinGroup()
  • func (ms *MembershipService) LeaveGroup()
  • func (ms *MembershipService) ListMembers() []string
  • func (ms *MembershipService) ListSelf() string
  • func (ms *MembershipService) StartIntroducer()
  • func (ms *MembershipService) StartService(portNum string, lossRate int)

Constants

const (
	JOINGOSSIP int = 2
	LEAVE      int = 3
	FAIL       int = 4
	HEARTBEAT  int = 5
	MASTER     int = 6
	ELECTION   int = 7
	OK         int = 8
)

Type of messages

Types

type MembershipList

type MembershipList struct {
	// contains filtered or unexported fields
}

type MembershipService

type MembershipService struct {
	Successors      []string    // 4 successors
	Predecessors    []string    // 3 predecessors
	LeaveReportChan chan string // leave report channel
	FailReportChan  chan string // failure report channel
	JoinReportChan  chan string // join report channel
	// contains filtered or unexported fields
}

func (*MembershipService) GetMembershipList

func (ms *MembershipService) GetMembershipList() []string

func (*MembershipService) JoinGroup

func (ms *MembershipService) JoinGroup()

func (*MembershipService) LeaveGroup

func (ms *MembershipService) LeaveGroup()

func (*MembershipService) ListMembers

func (ms *MembershipService) ListMembers() []string

func (*MembershipService) ListSelf

func (ms *MembershipService) ListSelf() string

func (*MembershipService) StartIntroducer

func (ms *MembershipService) StartIntroducer()

StartIntroducer starts introducer service

func (*MembershipService) StartService

func (ms *MembershipService) StartService(portNum string, lossRate int)

StartService starts membership service