Transcript Understanding our Isis Example Program

UNDERSTANDING OUR ISIS
EXAMPLE PROGRAM
Ken Birman
Code for full program
using
using
using
using
using
using
System;
System.Collections.Generic;
System.Linq;
System.Text;
Isis;
System.Threading;
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
Console.WriteLine("=== Query for arg=" + arg);
List<int> answer = new List<int>();
int index = 0;
foreach (tuple tp in database)
if (index++ % 3 == myRank)
{
Console.WriteLine("Looking at " + tp.rank + "/" + tp.value);
if (tp.rank == arg)
{
Console.WriteLine("Including " + tp.rank + "/" + tp.value);
answer.Add(tp.value);
}
}
g.Reply(answer);
};
g.Join();
while (!go)
Thread.Sleep(10);
for (int n = 0; n < 5; n++)
g.OrderedSend(UPDATE, myRank, n);
while (!dbfull)
Thread.Sleep(10);
if(myRank == 1)
for (int n = 0; n < 3; n++)
{
List<List<int>> results = new List<List<int>>();
g.OrderedQuery(Group.ALL, LOOKUP, n, new Isis.EOLMarker(), results);
Console.WriteLine("\r\nAnswers for Query rank=" + n);
foreach (List<int> list in results)
foreach (int value in list)
Console.Write(value + " ");
}
IsisSystem.WaitForever();
namespace ConsoleApplication3
{
public class tuple
{
public int rank;
public int value;
public tuple(int r, int v)
{
rank = r; value = v;
}
}
class Program
{
static List<tuple> database = new List<tuple>();
public const int UPDATE = 0;
public const int LOOKUP = 1;
static void Main(string[] args)
{
IsisSystem.Start();
Group g = new Group("foo");
int myRank = 0;
bool go = false, dbfull = false; ;
g.ViewHandlers += (ViewHandler)delegate(View v)
{
Console.WriteLine("New View: " + v);
myRank = v.GetMyRank();
if (v.members.Length == 3)
go = true;
};
g.Handlers[UPDATE] += (Action<int,int>)delegate(int rank, int n)
{
database.Add(new tuple(n, rank));
Console.WriteLine("New tuple: " + rank + "/" + n);
if (database.Count() == 15)
dbfull = true;
};
}
}
}
What the program does




Forms a process group
When there are 3 members, each of the 3
simultaneously sends updates to the group
They store these updates in “tuple” objects, as a list,
called the “database” list.
Then 2 members wait (Isis.WaitForEver) while the 3rd
member sends queries to the list
 The
queries are designed to select a subset of the data
 We “subdivide” the work of searching the list
What the program does




First member starts
the system
If several start at
same time, a Consensus
within Isis2 decides which
will be the first member
When it calls g.Join(),
group is created
We see a first View
report
static void Main(string[] args)
{
IsisSystem.Start();
Group g = new Group("foo");
. . .
g.Join();
while (!go)
Thread.Sleep(1);
. . .
}
Consensus “in action”: IsisSystem.Start()

Step 1: Discovery


Copy A
B
C
“Is anyone running Isis?”
Step 2: Collision
They hear each other!
 Consensus: The process with
the smallest id is picked
by fault-tolerant algorithm

Step 1
{A, B, C}
{A, B, C}
Add B
Step 2
{A, B, C}
Add C
B added

Step 3: A starts first. B
and C are added next
C added
Notice: A “wins the race”


IsisSystem.Start()
finishes first in A
B and C join “in
background” but user
code is already
running in A
A is active before B,C
Copy A
B
C
Step 1
{A, B, C}
{A, B, C}
Add B
Step 2
{A, B, C}
Add C
B added
C added
FLP impact?

It is impossible to guarantee progress for a correct
consensus protocol that tolerates even one fault

Clearly Isis2 startup is solving consensus

Thus we can guarantee that startup will succeed
 However,
we can make it “very likely” that it will
succeed, and this is enough
What does A do now?
Type signature
g.ViewHandlers += (ViewHandler)delegate(View v)
Anonymous method
{
. . . Code for when a new membership view is defined . . .
};
g.Handlers[UPDATE] += (Action<int,int>)delegate(int rank, int n)
{
. . . Code for doing an UPDATE action . . .
};
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
. . . Code for doing a LOOKUP action . . .
};
g.Join();
“Delegate” concept


In C++ every method must have a name
In Java and C# you don’t need to name a method if
you are happy to use “anonymous” naming
 The
compiler takes the “delegate” and creates a
method with a name the compiler itself assigns
 Then it compiles this method

So we are simply registering a method with Isis2
What does A do now?
g.ViewHandlers += (ViewHandler)delegate(View v)
{
. . . Code for when a new membership view is defined . . .
};
g.Handlers[UPDATE] += (Action<int,int>)delegate(int rank, int n)
{
. . . Code for doing an UPDATE action . . .
};
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
. . . Code for doing a LOOKUP action . . .
};
g.Join();
Variables in a delegate



Arguments are provided during the “upcall”
But a delegate can also access variables that were
accessible in the method where it is placed
Thus our delegates can use variables created by the
Main method.
 We
use this to access the “database” variable
Access to the database variable
Declared “outside”
class Program
{
static List<tuple> database = new List<tuple>();
public const int UPDATE = 0;
public const int LOOKUP = 1;
static void Main(string[] args)
{
. . .
g.Handlers[UPDATE] += (Action<int,int>)delegate(int rank, int n)
{
database.Add(new tuple(n, rank));
Console.WriteLine("New tuple: " + rank + "/" + n);
if (database.Count() == 15)
dbfull = true;
};
. . .
}
}
Access to the database variable
class Program
{
static List<tuple> database = new List<tuple>();
public const int UPDATE = 0;
public const int LOOKUP = 1;
static void Main(string[] args)
{
. . .
Can be used “inside”
g.Handlers[UPDATE] += (Action<int,int>)delegate(int rank, int n)
{
database.Add(new tuple(n, rank));
Console.WriteLine("New tuple: " + rank + "/" + n);
if (database.Count() == 15)
dbfull = true;
};
. . .
}
}
But the methods don’t run yet!
g.ViewHandlers += (ViewHandler)delegate(View v)
{
. . . Code for when a new membership view is defined . . .
};
g.Handlers[UPDATE] += (Action<int,int>)delegate(int rank, int n)
{
. . . Code for doing an UPDATE action . . .
};
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
If group does not exist, creates it. A will run this first
. . . Code for doing a LOOKUP action . . .
};
g.Join();
What the program does
So… the three
members
tryORACLE...
to start
Isis: Searching
for the Isis
New View:
View[gname=<foo>,
Isis2,
but A “wins”gaddr=(0:224.0.69.120/0:0), viewid=0;

1 members={ [(5656)]}, hasFailed=[*-],
nextIncomingMSGID={ <0:0> 0:0 }, StableTo={ ** 0 },
joining={ [(5656)]}, leaving={ []}, IamLeader = True

As a result, A runs the
g.ViewHandlers += (ViewHandler)delegate(View v)
{
g.Join() first
Console.WriteLine("New View: " + v);
myRank = v.GetMyRank();
if (v.members.Length == 3)
go = true;

A “new view” event };
occurs with 1 member
What is in the View object?




Array of members (Address[n]), in v.members
Who just joined (v.joined), left/failed (v.leaving)
View id number, increments for each new view
Group address: an Address object
 Both

groups and individual processes have Addresses
The “rank” of the member: 0..n-1 in the v.members
v.GetMyRank(), v.GetRankOf(someone)
What is in the View object?


Group “foo” has Address (0:224.0.69.120/0:0)
There is one member: (5656). It just joined.
 If
“long format” is used, we would also see the host
IPv4 address: (5656:123.64.88.2:2345/1212)

The viewid is 0: the group was just created
Isis: Searching for the Isis ORACLE...
New View: View[gname=<foo>, gaddr=(0:224.0.69.120/0:0), viewid=0;
1 members={ [(5656)]}, hasFailed=[*-],
nextIncomingMSGID={ <0:0> 0:0 }, StableTo={ ** 0 },
joining={ [(5656)]}, leaving={ []}, IamLeader = True
Next B and C join the group

New views are reported
 Viewid
0: 1 member: A
 Viewid 1: 2 members: A, B
 Viewid 2: 3 members: A, B, C


Notice that ALL group members see the same view
events, starting when they join
“Old” members have smaller rank than “new” ones
State transfer


Our sample program didn’t transfer any state to the
joining member.
Homework task: Add state transfer
State: contents of the List<Address> database
 In an Isis2 group, the state consists only of the state-machine
replicated data you associate with the group
 You do not need to include every variable!


In our sample program, the state was “empty” until
after 3 members join, so state transfer was not needed
What did the program do next?

Look closely at the View event handler
g.ViewHandlers += (ViewHandler)delegate(View v)
{
Console.WriteLine("New View: " + v);
myRank = v.GetMyRank();
if (v.members.Length == 3)
go = true;
};

Each member
 Notes
its “rank”, in the variable myRank
 myRank=0
 Sets
in A, 1 in B, 2 in C
boolean “go” to true when 3 members are in the
View that was just reported
What did the program do next?

Now look at the Main method after g.Join
while (!go)
Thread.Sleep(10);

Every member loops, sleeping for 10ms at a time
So it checks go 100 times/second
 When go becomes true, we pass the “barrier”


Homework: Replace “go” with a C# Semaphore:
Semaphore go = new Semaphore(0, int.MaxValue);
 go.WaitOne() …. go.Release(1)

What did the program do next?

Now look at the Main method after go==true
for (int n = 0; n < 5; n++)
g.OrderedSend(UPDATE, myRank, n);

All three members concurrently begin to call
g.OrderedSend!
A Sends…
B Sends…
C Sends…
(0,0)
(1,0)
(2,0)
(0,1)
(1,1)
(2,1)
(0,2)
(1,2)
(2,2)
(0,3)
(1,3)
(2,3)
(0,4)
(1,4)
(2,4)
2
Isis

has many multicast options
g.SafeSend: Paxos, guarantees
 Total
ordering, all-or-nothing delivery, durability even if
all members crash. Logged into a disk file
 … this is stronger than we need! Our data is stored in
memory (in the “database” List<tuple> variable)

g.OrderedSend: Optimistic early delivery
 Total
ordering, all-or-nothing among processes that do
not crash. No logging, much faster than SafeSend
 … this is what we are using
2
Isis

has many multicast options
g.Send: Optimistic, reliable, FIFO
First message sent is first message delivered
 But ordered only if sent by the same sender process: A
sends X, then A sends Y. X delivered before Y


g.CausalSend: Optimistic, causal, reliable
Causal ordering
 First message sent is first delivered, even if different senders
(e.g. process B receives X from A, then sends Y. X delivered
before Y because B sent Y after receiving X)


g.RawSend: No guarantees, not even reliable
With g.Send…


Our multicasts could arrive in different orders
All database copies would have identical content but
perhaps the order in the list would differ


We saw this on Tuesday
With OrderedSend, all databases look the same



State machine replication in “practice”
Homework: In what ways does our application rely on ordering?
Would the code break if we used g.Send and not
g.OrderedSend?
Homework: Do we know what the ordering in database will be
before the program ran, or are there multiple possible outcomes?
Receiving the multicasts

The members get upcalls to the multicast event handler.
In fact these are done on a different thread: the
“multicast and view delivery thread”
g.Handlers[UPDATE] += (Action<int,int>)delegate(int rank, int n)
{
database.Add(new tuple(rank, n));
Console.WriteLine("New tuple: " + rank + "/" + n);
if (database.Count() == 15)
dbfull = true;
};

dbfull becomes true when database has 15 items.

Homework: replace dbfull with a Semaphore
What is a “tuple”?

A simple object that stores a rank and a value
public class tuple
{
public int rank;
public int value;
public tuple(int r, int v)
{
rank = r; value = v;
}
}
Could we put tuples in messages?

Yes… but we would need to provide “Marshalling”
code, and a null constructor, like this:
[AutoMarshalled]
public class tuple
{
public int rank;
public int value;
public tuple(int r, int v)
{
rank = r; value = v;
}
public tuple() { }
}

Then must call Msg.RegisterType(typeof(tuple),

The 0 is a “unique type id” in range 0…128
0);
Can we put tuples in messages?

Homework
 Modify
the test program to send tuples
 Store the received tuples into the database
 Thought question: Does UPDATE call “new tuple”?
What happens next?


Recall that tuple 15 sets dbfull to true
Look at Main again
g.OrderedSend(UPDATE, myRank, n);
while (!dbfull)
Thread.Sleep(10);

… all three programs (A, B and C) pass the while
What happens next?


Recall that tuple 15 sets dbfull to true
Look at Main again
g.OrderedSend(UPDATE, myRank, n);
while (!dbfull)
Thread.Sleep(10);

… all three programs (A, B and C) pass the while
What happens next?

Only member 1 (B) executes the last code:
if(myRank == 1)
for (int n = 0; n < 3; n++)
{
List<List<int>> results = new List<List<int>>();
g.OrderedQuery(Group.ALL, LOOKUP, n, new Isis.EOLMarker(), results);
Console.WriteLine("\r\nAnswers for Query rank=" + n);
foreach (List<int> list in results)
foreach (int value in list)
Console.Write(value + " ");
}

B creates a “results” list, then issues an OrderedQuery
asking for ALL responses


It does this three times: with n=0, n=1, n=2
Each time it simply prints the list of responses
What is a List<List<int>>?

In Java, C#, C++ we can create types that include
other types are “arguments”.
 These


are called Generics
The results variable is a List: it will have one value
in it for each member of the group
… and that value will be of type List<int>
 Each
group member sends a List in g.Reply
Finally… the query handler

Look at the LOOKUP code:
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
Console.WriteLine("=== Query for arg=" + arg);
List<int> answer = new List<int>();
int index = 0;
foreach (tuple tp in database)
if (index++ % 3 == myRank)
{
Console.WriteLine("Looking at " + tp.rank + "/" + tp.value);
if (tp.rank == arg)
{
Console.WriteLine("Including " + tp.rank + "/" + tp.value);
answer.Add(tp.value);
}
}
g.Reply(answer);
};
Finally… the query handler

… simplified version:
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
Console.WriteLine("=== Query for arg=" + arg);
List<int> answer = new List<int>();
int index = 0;
foreach (tuple tp in database)
if (index++ % 3 == myRank)
{
Console.WriteLine("Looking at " + tp.rank + "/" + tp.value);
if (tp.rank == arg)
{
Console.WriteLine("Including " + tp.rank + "/" + tp.value);
answer.Add(tp.value);
}
}
g.Reply(answer);
};
Each member…


Has identical data in the database
(g.OrderedSend).
… but has a different value of myRank: 0, 1 or 2
Database item
A: myRank=0
0: (1,0)
Looking at (1,0)
1: (0,0)
B: myRank=1
Looking at (0,0)
2: (1,1)
3: (2,0)
4: (1,2)
5: (0,1)
C: myRank=2
Looking at (1,1)
Looking at (2,0)
Looking at (1,2)
Looking at (0,1)
Homework question

Exactly what can we say about the order we will
see for tuples in database?
 Why
are the copies identical in A, B and C?
 Did it matter that we only set go=true after A,B and C
all joined?
 Change
the code to set go=true as soon as there are two
members, A and B
 Now use state transfer to fix the “bug” this causes
 Will
items sent by the same sender be in the sender
order? (0,0)… (0,1)… (0,2)… (0,3)… (0,4)
Finally… the query handler

Look at the LOOKUP code:
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
Console.WriteLine("=== Query for arg=" + arg);
List<int> answer = new List<int>();
int index = 0;
foreach (tuple tp in database)
if (index++ % 3 == myRank)
{
Console.WriteLine("Looking at " + tp.rank + "/" + tp.value);
if (tp.rank == arg)
{
Console.WriteLine("Including " + tp.rank + "/" + tp.value);
answer.Add(tp.value);
}
}
g.Reply(answer);
};
Finally… the query handler

Look at the LOOKUP code:
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
Console.WriteLine("=== Query for arg=" + arg);
List<int> answer = new List<int>();
int index = 0;
foreach (tuple tp in database)
if (index++ % 3 == myRank)
{
Console.WriteLine("Looking at " + tp.rank + "/" + tp.value);
if (tp.rank == arg)
{
Console.WriteLine("Including " + tp.rank + "/" + tp.value);
answer.Add(tp.value);
}
}
g.Reply(answer);
};
A, B and C each scan 5 tuples


Each one looks for rank==n, where n was from the
Query sender (n=0… then n=1… then n=2)
How many items will each one find?
 Thought
question: how many items have rank=0?
 … 5 have rank=0
 But which member will “see” these tuples?
… we cannot know!



Perhaps “luck” will cause all of these to be scanned
by A! But perhaps in a second run, A will see none
The situation depends on the data in database, and
the order was not fully determined
Thus until we know the order, we cannot be sure
which items A will look at, and until we know that,
we cannot know how many will have rank=0
… but we DO know that


Every tuple is scanned exactly once
And thus every rank=0 tuple will be seen by some
member.
 Example:
perhaps A finds (0,1) and (0,3)
 … and B finds none
 … while C finds (0,0), (0,2) and (0,4)

Each sends its own List<int>: A sends { 1, 3 }, etc
Back to the leader (process B)

Again, look at code in Main
if(myRank == 1)
for (int n = 0; n < 3; n++)
{
List<List<int>> results = new List<List<int>>();
g.OrderedQuery(Group.ALL, LOOKUP, n, new Isis.EOLMarker(), results);
Console.WriteLine("\r\nAnswers for Query rank=" + n);
foreach (List<int> list in results)
foreach (int value in list)
Console.Write(value + " ");
}

Results is a “List of List<int>”
Back to the leader (process B)

Again, look at code in Main
if(myRank == 1)
for (int n = 0; n < 3; n++)
{
List<List<int>> results = new List<List<int>>();
g.OrderedQuery(Group.ALL, LOOKUP, n, new Isis.EOLMarker(), results);
Console.WriteLine("\r\nAnswers for rank=" + n);
foreach (List<int> list in results)
foreach (int value in list)
Console.Write(value + " ");
}


Perhaps results will have {1,3},{},{0,2,4}
So output will be 1 3 0 2 4
What does “consistency” mean?




Every tuple is scanned by one group member
We know that there is a 0, 1, 2, 3, 4 value for each
rank value 0, 1, 2
So a consistent answer requires that we see 0..4 for
each Query, but the program might not print in order
Homework: what we can say about the ordering within
each List<int> reply element?
Which result came first?


In the results list we do not know which part of the result
came from A, which from B and which from C
Homework:
Add a second value to the reply giving the rank of the
member that sent each list
 Modify the output to show this information

Answers for Query rank=0
[Member with myRank=0 sent {1,2}]
[Member with myRank=2 sent {}]
[Member with myRank=1 sent {0,3,4}]
Using the View

Homework: Modify the program so that if the View
contains N members when the Query is done, each does
1/N of the work


Currently code is “hard coded” to always use N=3
What if a failure causes loss of a Reply?
Homework: Modify the replies to include value of N
 Modify the Main program to sense missing reply and “retry”
the Query: Missing a reply… must retry for rank=0
 Homework: Test your fault-tolerance logic (hint: consider
using “IsisSystem.Terminate()” to “crash” a member)

Code for full program
using
using
using
using
using
using
System;
System.Collections.Generic;
System.Linq;
System.Text;
Isis;
System.Threading;
g.Handlers[LOOKUP] += (Action<int>)delegate(int arg)
{
Console.WriteLine("=== Query for arg=" + arg);
List<int> answer = new List<int>();
int index = 0;
foreach (tuple tp in database)
if (index++ % 3 == myRank)
{
Console.WriteLine("Looking at " + tp.rank + "/" + tp.value);
if (tp.rank == arg)
{
Console.WriteLine("Including " + tp.rank + "/" + tp.value);
answer.Add(tp.value);
}
}
g.Reply(answer);
};
g.Join();
while (!go)
Thread.Sleep(10);
for (int n = 0; n < 5; n++)
g.OrderedSend(UPDATE, myRank, n);
while (!dbfull)
Thread.Sleep(10);
if(myRank == 1)
for (int n = 0; n < 3; n++)
{
List<List<int>> results = new List<List<int>>();
g.OrderedQuery(Group.ALL, LOOKUP, n, new Isis.EOLMarker(), results);
Console.WriteLine("\r\nAnswers for Query rank=" + n);
foreach (List<int> list in results)
foreach (int value in list)
Console.Write(value + " ");
}
IsisSystem.WaitForever();
namespace ConsoleApplication3
{
public class tuple
{
public int rank;
public int value;
public tuple(int r, int v)
{
rank = r; value = v;
}
}
class Program
{
static List<tuple> database = new List<tuple>();
public const int UPDATE = 0;
public const int LOOKUP = 1;
static void Main(string[] args)
{
IsisSystem.Start();
Group g = new Group("foo");
int myRank = 0;
bool go = false, dbfull = false; ;
g.ViewHandlers += (ViewHandler)delegate(View v)
{
Console.WriteLine("New View: " + v);
myRank = v.GetMyRank();
if (v.members.Length == 3)
go = true;
};
g.Handlers[UPDATE] += (Action<int,int>)delegate(int rank, int n)
{
database.Add(new tuple(n, rank));
Console.WriteLine("New tuple: " + rank + "/" + n);
if (database.Count() == 15)
dbfull = true;
};
}
}
}