Master election improvements

Master election algorithm

[marcus.falgert, 2015-11-28 17:07:44]

So, me and Robert had a look at some time series prediction libraries for java
which could possibly be used to predict the best possible master. After looking
into some libraries however, we found out that they were very complicated to use
and required a lot of research to use properly. So we scratched the idea of
using those libraries for now. Instead, we improved upon the existing algorithm
that we have.

First of all, we now collect write and latency data in linked lists, for all
nodes. Data put into these linked lists will be pushed back every X secs/msecs.
This is accomplished by always putting new data in the front/head of the lists.
So writes/latencies are bundled together in different time intervals (every X
secs/msecs). The maximum size of the lists can also be set, and when the number
of list elements exceeds this limit, they will be thrown out/deleted. So the
lists are basically sliding windows.

When we want to calculate who should be the new master, we take the write and
latency data of each node and weight them depending on how fresh the data is.
Fresher data becomes more valued, and the weight is easily configurable. For
example:

t0: 10 writes, t1: 15 writes. Weighted writes = 10*1 + 15*0.9.

We then calculate the master election points as normal, using these weighted
values instead. The algorithm likely needs more work, but i think this change is
in the right direction at least.

The files you should look at are:
- "ScheduledTasks.java", where the master election task is modified, and the
sliding windows are implemented as tasks performed every X secs/msecs.
- "MasterElectionData.java", which contains the linked lists of writes and
latencies of a node, and how to add data to them as well as "sliding" the data.
-"WeightFunctions.java", how the data is weighted.
-"MasterElectionFunctions.java", used in the master election task in
"ScheduledTasks.java" to perform the different steps of the master election.
Putting all the different steps in one seperate file helps make everything more
clear for everyone.

Let me know what you think.

//Marcus

[marcus.falgert, 2015-11-29 01:25:29]

I made a new commit to git as well, where i commented the code more.

[teowey, 2015-11-29 22:10:22]

https://codereview.appspot.com/277110043/diff/1/src/main/java/se/kth/crypt/se...
File src/main/java/se/kth/crypt/server/core/WeightFunctions.java (right):

https://codereview.appspot.com/277110043/diff/1/src/main/java/se/kth/crypt/se...
src/main/java/se/kth/crypt/server/core/WeightFunctions.java:20: * @param m 0 if
you don't care
@Robert here's a typo on k and m, both say don't care. Can you explain the logic
on these variables? The m is just an independent coefficient right?

[bruce.yinhe, 2015-11-30 19:24:32]

This seems to duplicate this one:
https://gits-15.sys.kth.se/Crypt/crypt-node/pull/7/files

@Marcus what do you think?



Bruce

On Sun, Nov 29, 2015 at 10:10 PM, <teowey@gmail.com> wrote:

>
>
>
https://codereview.appspot.com/277110043/diff/1/src/main/java/se/kth/crypt/se...
> File src/main/java/se/kth/crypt/server/core/WeightFunctions.java
> (right):
>
>
>
https://codereview.appspot.com/277110043/diff/1/src/main/java/se/kth/crypt/se...
> src/main/java/se/kth/crypt/server/core/WeightFunctions.java:20: * @param
> m 0 if you don't care
> @Robert here's a typo on k and m, both say don't care. Can you explain
> the logic on these variables? The m is just an independent coefficient
> right?
>
> https://codereview.appspot.com/277110043/
>

[marcus.falgert, 2015-11-30 22:09:03]

On 2015/11/30 19:24:32, bruce.yinhe wrote:
> This seems to duplicate this one:
> https://gits-15.sys.kth.se/Crypt/crypt-node/pull/7/files
> 
> @Marcus what do you think?
> 
> 
> 
> Bruce
> 
> On Sun, Nov 29, 2015 at 10:10 PM, <mailto:teowey@gmail.com> wrote:
> 
> >
> >
> >
>
https://codereview.appspot.com/277110043/diff/1/src/main/java/se/kth/crypt/se...
> > File src/main/java/se/kth/crypt/server/core/WeightFunctions.java
> > (right):
> >
> >
> >
>
https://codereview.appspot.com/277110043/diff/1/src/main/java/se/kth/crypt/se...
> > src/main/java/se/kth/crypt/server/core/WeightFunctions.java:20: * @param
> > m 0 if you don't care
> > @Robert here's a typo on k and m, both say don't care. Can you explain
> > the logic on these variables? The m is just an independent coefficient
> > right?
> >
> > https://codereview.appspot.com/277110043/
> >

It is definately not a duplicate. I saw your pull request, but an important task
we discussed previously was how to store data over time. Therefore, I had to
completely rewrite the master election code to use the new data structure (a new
class was created for this, where you could add/remove as well as "slide" the
data as time passed). I also segmented the master election in smaller,
individual steps in the process (you did something similar, but I tried to split
up the election code even more in different methods. Have a look in the code and
see if you agree or not).

The problem was, I didn't really know how I was supposed to use your code. Your
code does not really implement anything new, you just moved stuff from some
places in the code to a new separate class. I agree that this is a step in the
right direction in order to make the code more modular and understandable, but
as i had to rewrite the majority of the election code for the new data
structure, I could not really use your code. We can discuss more about this
tomorrow(tuesday) if you want.

//Marcus

[bruce.yinhe, 2015-12-01 05:37:40]

In this case we can close pull request #7.

Le lun. 30 nov. 2015 à 23:09, <marcus.falgert@gmail.com> a écrit :

> On 2015/11/30 19:24:32, bruce.yinhe wrote:
> > This seems to duplicate this one:
> > https://gits-15.sys.kth.se/Crypt/crypt-node/pull/7/files
>
> > @Marcus what do you think?
>
>
>
> > Bruce
>
> > On Sun, Nov 29, 2015 at 10:10 PM, <mailto:teowey@gmail.com> wrote:
>
> > >
> > >
> > >
>
>
>
https://codereview.appspot.com/277110043/diff/1/src/main/java/se/kth/crypt/se...
> > > File src/main/java/se/kth/crypt/server/core/WeightFunctions.java
> > > (right):
> > >
> > >
> > >
>
>
>
https://codereview.appspot.com/277110043/diff/1/src/main/java/se/kth/crypt/se...
> > > src/main/java/se/kth/crypt/server/core/WeightFunctions.java:20: *
> @param
> > > m 0 if you don't care
> > > @Robert here's a typo on k and m, both say don't care. Can you
> explain
> > > the logic on these variables? The m is just an independent
> coefficient
> > > right?
> > >
> > > https://codereview.appspot.com/277110043/
> > >
>
> It is definately not a duplicate. I saw your pull request, but an
> important task we discussed previously was how to store data over time.
> Therefore, I had to completely rewrite the master election code to use
> the new data structure (a new class was created for this, where you
> could add/remove as well as "slide" the data as time passed). I also
> segmented the master election in smaller, individual steps in the
> process (you did something similar, but I tried to split up the election
> code even more in different methods. Have a look in the code and see if
> you agree or not).
>
> The problem was, I didn't really know how I was supposed to use your
> code. Your code does not really implement anything new, you just moved
> stuff from some places in the code to a new separate class. I agree that
> this is a step in the right direction in order to make the code more
> modular and understandable, but as i had to rewrite the majority of the
> election code for the new data structure, I could not really use your
> code. We can discuss more about this tomorrow(tuesday) if you want.
>
> //Marcus
>
> https://codereview.appspot.com/277110043/
>