I mentioned that this management function that this initiator
is doing, you don't want it to be statically
assigned to one node, because that would be a
huge burden, and besides this node will suddenly become very
active, and if that happens, then you must time
in the computations that are going to happen here to
do this management function. Now intuitively if you think
about it, if a particular node, let's say node N2.
Has a read of .8, what does that mean? What that means is that in the upcoming
Epoch, 80% of the end pages are going to be replaced from the
node N2, in other words, N2 is hosting a whole bunch of serious citizens, so
it's a node that's not very active. Right?
If an inactive node, then the replacement's candidates
are probably not going to come from that guy
and in predicting the future the initiator is saying that
well, most of the replacements are going to come from
here, so it's rated very high. So this information. The
weight information for all the nodes is coming to
every one of these guys. So intuitively if we think
about it, the guy that has the highest weight is
probably the least active. Why not make him the manager?
So the initiator for the next Epoch is going
to be the node with the maximum weight. Now how
do you determine that? Well, every one of these
nodes is receiving not only the min age of the
candidate pages that are going to be replaced in
the next epoch but also the weight distribution that says
what is the percentage of these replacements that are going
to happen in each one of these nodes. So locally
each one of these guys. Can look at the
Wi vector that it got back from the initiator and
say, I know, given that node N3 has the
maximum rate, that's going to be the initiative of the next
epoch. So locally you can make the determination so
that for the next epoch, in order to send the
age information, you know, locally who to send it
to. Now let's look at how this minimum age information
is going to be used by each node.
Remember that min age represents the minimum age of
the m oldest pages. The smaller the age, the
more recent that page is. And so those are
the active pages. So if you, if you look at this as the age distribution, of all
the pages, then if you draw a line here,
then the pages to the left of this line,
the minimum age line, are the active pages. And the
pages to the right of this, with is the m
oldest pages are the candidate pages that are going to
be replaced in the next epoch. This is the information that
we're going to use In the way we manage page
replacements at every node. So let's see what the action is
at a node when there is a page fault. If
upon a page fault I have to evict a page y,
then what I'm going to do is I'm going to look at the age of this page y. If the
age of this page y is more than the minimum
wage. Then I know it's going to be replaced. Even if
I sent it to a peer node, it's going to be
replaced because that is part of the candidate m pages
that are going to be replaced in the upcoming epoch. And
therefore locally I'll make a decision that page y has
an age older than minimum age, and therefore, I'm
going to discard it. Simply discard it. Don't worry about sending
it to a peer. Remember that, in the description of
how a page fault is handled, I said that, when
you have a page fault in the node, I pick
one of the replacement candidates, and I send it to
a peer node. To store it in the global cache
of the peer node. Well, we don't want to do that.
If that page is going to be eventually replaced
during this upcoming epoch, meaning it has to be
thrown out onto the disk. In that case, you
might as well discard it right now. So if
the age of the page that you're evicting. From
your node happens to be greater than MinAge, simply
discard it. On the other hand, if the page
happens to be less than the MinAge, then you
know that it is part of the Active set
of pages for the entire cluster, you cannot throw
it away. You send it to Peer Node Ni. How do you pick Ni? This is where the
weight distribution comes in. I know the weight of
the nodes. At the end of this computation, the
manager sent me the weight distribution for the upcoming
epoch of all the nodes. So I can pick a
node to send this page to based on the
weight distribution. Of course I could say, well, send it
to the guy that has the highest weight because that's
the guy that is likely to replace, but remember that
there's only an estimate of what is going to happen in
the future. So, you don't want to hard code that.
Instead, we're going to use some information drawn from these weights.
We're going to factor that weight information Into making a choice
as to which peer we want to send this
eviction page to. Chances are that the node, that
has a higher weight is a likely candidate that'll
pick. But it will not always be the node
with the highest weight. Because if that decision is
made by everybody then we going to have a situation
where. If the prediction was not exactly accurate, we
would be making wrong choices. Basically you can see
that this age management, geriatric management, is
approximating a global LRU. Not exactly a
global LRU, because global LRU. Computing that
on every page fault is too expensive,
so we don't want to do that. Instead, we are doing an approximation to global
LRU by computing this information at the beginning of an epoch, and using that
information locally in order to make decisions. So we
think globally in order to get all the age
information, and compute the minimum age and compute the
weight for all the nodes as to how much of
the fraction of the replacements are going to come from
each one of these nodes. But once that computation
has been done, for the duration of the epoch,
all the decisions that are taken at a particular node
Is local decisions in terms of, what we want to do, with respect to a page that
we are choosing as an eviction candidate. Do we discard it, or do we store it in
a peer, global cache? This might sound like a political slogan but, the
important thing, in any distributed system, is as much as
possible. Use local information in decision making. So think globally but
act locally. So that's the key and that's
what is ingrained in this description of the algorithm.