[Loco-dev] Backend

[Janico Greifenberg]

Hi,
I made an important design decision this week: I exchanged the tree as loco
backend with a distributed doubly linked list. This is probably quiet
surprising or even shocking so let me explain what the problems with the tree
were, what I wanted instead and what exactly the new backend is.

The main problems with the tree are that its maintainance is way too complex
and changes may affect the entire network. The complexety is a problem because
there a many, many points of failure (while trying to implement the tree I
noticed in many parts that there are things which could fail easily but might
be fixed somehow though with substancial efford). Even if the tree could be
stabilized the code would be an incompresensible mess somewhere between deep
wizardry and evil hacks and I don't think that this is good for the central
part of the project. The complexity was a problem I always kind of knew about
but I think I wanted to take the challenge and ignored or postponed it. 
The point where I thought something
else is needed was when I wanted to implement messages for split and merge
operations. These can affect the whole tree and it's a bad idea to have two
of those operations running a the same time, so some kind of locking was
needed, which needs to be in one place as locks only make sense when they are
atomic operations. But with one peer handling the locks we would have a
centralized service (with vast power over the network) and that is
contradictory to the goals of Loco. 
Even if there is way to handle the locks in a decentralized way the complexety
is undeniable. B-trees are a great data structure for searching but they are
very fragile. And a fragile structure with complicated maintainace functions is
not really good for being distributed over a network with many people to mess
with it. 

So I wanted a structure machting the following criteria:
- simple (and thourgh this easy to maintain and to fix)
- sorted by fingerprints (this was the most important feature of the tree I
think) 
- all changes affect only a small number of peers

So I came up with (and imlemented) a doubly linked list with buffer and
cache. So what does that mean?
Every peer is a link in the list and so it knows its direct predessor and its
direct successor. The buffer means that each peer looks one link ahead for
safety reasons, so one peer knows also the predessor of its predessor and the
successor of its successor. The cache means that nodes you got to know somehow
are saved, so you can "jump" into other parts of the list to search more
efficiently. The disadvantage of the solution is that searches are less
efficient than in the tree, but because of the cache you can be lucky. 
I tested this backend with a couple of clients and it worked (of
course I cannot say anything about the performance) but more testing needs to
be done. The latest version of implementation of the tree is in the CVS in the
branch tree-backend-branch, the main development branch (which you get with a
simple checkout without options) contains the new backend. 
While I was at it I also removed the Loco socket descriptors (integer
identifiers for sockets) so now sockets are only identified by LocoSocket
structs. The desciptors were introduced because I wanted more similarity with
the regual socket API but they didn't have any advantage and only made things
more complicated internally.

I think this change is a great step ahead for Loco. I will now clean up some
things and that turn toward documentation and more features (search keys in the
list and so on).

So long
   Divo
-- 
Warning! Taking anyone (especially yourself) too serious will be harmful

pgpxhrK3ZPle3.pgp
Description: PGP signature