Tuesday, January 10, 2012

Entities and values

As so often in programming, one big question arose when I worked on my Undo/Replication framework: What is an entity, and what is a value?

I use the word entity to make clear that I mean something different from objects. An object is something identified by an address pointer, whereas for a primitive value, its bytes in memory directly represent the value instead of an address. What I mean with entity/value is best explained by an example from databases:

Suppose you have a database table storing the data of a company's employees. There is a surname, a prename, a birth date, and so on. Besides others, there's an address. The simplest approach is to handle each of these items as a table column: Surname and prename are strings, the birthdate uses a special date column type. The address can also be simply taken as a string, but there are other ways:

An address is composed of a street name, a number, probably also an appartment number, country, state etc. It could be beneficial to store all these data in a table on its own, give it an ID (the database way of saying address), and only reference this ID in the employee table.

Don't forget the third way! You could use all those columns, but put them directly into the employee table, so there would be prename, surname, birth date, street, stree no., appartment no., etc.

What's the best? Of course, it depends! Variant one is easy to use, but lacks intrinsic validity checks: When the database doesn't know that something should be an (appartment) number, how should it check it's even a number? Variant two can handle a very specific case "better": two workers have the same address. In this case, the same ID can be referenced multiple times, so that both employees not only have equal addresses but also have the same one. In this particular case, the benefit is not too big, but there are use cases where it's important that something can be referenced. About the third, it really combines the downsides of the both above... I personally see no benefit in using it. It there are, I'm sorry I didn't see them.

Now, what should have triggered your attention was the word "ID". As soon as something has an identity, it's an entity. Note how the prename is a String, which is an Object type in Java, but only a value. On the other hand, the address in case 2 has an identifier and is an entity.

And now we're back: What I do is to assign IDs to the objects I want to replicate. The objects have values which can be changed, and I transmit changes like "property XY of object 01 changed from 'ab' to 'cd'."

And now the big question: what about collections? Should it be "element 'ab' was added to list 01" (i.e. they are entities) or "element 'ab' was added to list XY of object 01?"

Saturday, January 7, 2012

Replicating Game States - JGroups

So now I've got it. My goals in implementing Replication was to keep it out of the core functionality while still making it easy to use without worrying about replication yourself. How do you do that? By providing a general interface to other software (in my case, that's a listener) and implementing a specific one for the task at hand.

So my History class, which stores all changes to the managed objects, has a listener for two possible events: A new modification is executed; and the "current" state is moved somewhere else (e.g. undoing something.) My replication listener does not support undo right now, because I haven't figured out how to best identify a state (which is where the program is going) yet, but that should be easy. The other thing, executing modifications, does work. That means, whenever a modification is executed locally, it is sent over the network so that the partner(s) can execute it too.

The only downside is that the partners also "execute it locally", so I had to use a trick to suppress resending these received modifications. And it works pretty well:

//initialization code
final History h = createHistory(createKey("test-history"));
final JChannel channel = new JGroupsReplicationListener(h) {
    @Override
    public void receive(Message msg) {
        Modification m = (Modification) deserialize(msg.getBuffer());
        if(m instanceof Creation) id = ((Creation) m).getId();
        super.receive(msg);
    }
}.getChannel();


//executing the actions (creating an object)
h.pushHistoryForThread();
try {
    TestBean t = (TestBean) h.getObjectStore().get(Creation.create(new TestBean()));
    t.setA(1);
    t.setB(1);
} finally {
    h.popHistoryForThread();
}


//printing the results
System.out.printf("current state: %s%n", h.getObjectStore().get(id));



I made this test a GUI application so that I can control the timing on multiple virtual machines. The public void receive(Message msg)seen above is only needed for this Test, again. It's not necessary to do something like that to get the replication. The code in the middle looks exactly the same as the example last time, except I haven't hidden some of the details in a setTest() method.

Now what's probably the most interesting is how the networking works; let me tell you, I didn't write any! As hinted by me before, and in the title of course, is that I have tried JGroups to do this. In JGroups, you create Channels and let them join into a cluster; all channels in the cluster can receive and send messages, either to only only one recipient, or to all at the same time. JGroups provides a configurable protocol stack that takes care of reliability, synchronity and such things. For my tests, I have used a UDP-based protocol stack. For wide-area connections, a TCP-based approach is probably easier.

Thursday, January 5, 2012

Replicating Game States - Working code!

Before you get too excited - no, there's no multiplayer yet (well, who would have guessed that...). There is, however, working code for undoing and redoing actions (even with multiple, branching histories), and even for replicating the state on multiple virtual machines.

The key to make such a library is that it looks like ordinary Java code from the outside, so that others can use your code without wondering why it looks so weird. Let's take a look:

//Test t = new Test(); is an attribute

//replaced angle with square brackets because of HTML markup
List[StateStamp] states = new ArrayList[StateStamp]();
History h = createHistory(createKey("test"));
h.pushHistoryForThread();
try {

    states.add(h.getCurrentState()); // 0
    print();

    setTest(t);
    states.add(h.getCurrentState()); // 1
    print();

    getTest().setA(1);
    states.add(h.getCurrentState()); // 2
    print();

    getTest().setB(1);
    states.add(h.getCurrentState()); // 3
    print();

    Deletion.delete(getTest());
    states.add(h.getCurrentState()); // 4
    print();

    h.goToState(states.get(3));
    print();
    h.goToState(states.get(2));
    print();
    h.goToState(states.get(1));
    print();
    h.goToState(states.get(0));
    print();
} finally {
    h.popHistoryForThread();
}



It's probably easy to to guess that print(); prints the current state of the test object. Besides that, the only code that looks different from normal operations is marked in bold. Most of it is only necessary for this test case: storing the previous states so that you can go back. Really mandatory is only the colored code (and the actual functional code of course, but that doesn't count.)

Of course, a history for the modifications must be created. Then, the history is set for the thread: Code running in the thread (that is, everything in this method, and nothing more) can access the history without passing it as a parameter (which would make using the library awkward) or declaring it as a static variable somewhere (which is ugly from an architecture standpoint.) Everything after this is wrapped in try/finally, so that the last method is not skipped in case of an exception: this removes the association of the history with the current Thread.

Of course, implementing setTest(), setA() etc. is different from a usual simple setter. But the point here is that using the code is as simple as shown here. The result is this:

Test@732A54F9[a=0, b=0] not in store
Test@7A6D084B[a=0, b=0] in store
Test@7A6D084B[a=1, b=0] in store
Test@7A6D084B[a=1, b=1] in store
Test@7A6D084B[a=1, b=1] not in store
Test@15301ED8[a=1, b=1] in store
Test@15301ED8[a=1, b=0] in store
Test@15301ED8[a=0, b=0] in store
Test@15301ED8[a=0, b=0] not in store


You see here how the test object runs through different states up to its deletion, then goes back to its initial state. What's not shown here, but is working, is adding another branch to this history. Of course, the actual objects have only one state at a time, but the history can be switched arbitrarily between multiple histories:


This is the actual test case I ran: I went back to the state after creating the test object, changed its a value, and then switched over to the state before, and then after, deleting the test again.

I have code for replication of states going, but it's not yet as clean as for undo: a lot of handling is necessary for the network, which should be transparent to the user. I'll show it once I'm finished, but in the meantime you can look here.