On Wed, Feb 29, 2012 at 8:55 AM, Thomas Mueller <[email protected]> wrote: > Hi, > > I think we all have more or less the same basic idea. Well, I would call > it "Node" and not "Tree" because the term node more closely matches what > we do. But first about what we seem to agree: > > * A persistent and immutable data structure has many benefits > (for example concurrency). > > * Mutable data strucutures also have benefits: > it avoids creating lots of garbage and a new root node > for each and every modification. > > I think we should use a structure that is immutable when reading, but > mutable when writing. Write methods should return a new object (for > example cloneAndAddChildNode), but only when necessary, that is, if the > revision doesn't match. When the revision matches, the internal state is > changed instead, and the cloneAndAddChildNode method returns 'this'. A > first implementation is org.apache.jackrabbit.mk.simple.NodeImpl. > >> everyone has their own >> MicroKernel implementation.
i won't comment on why we suddenly ended up with 2 independent and supposedly competing implementations of the MicroKernel API within the same sandbox project. that's the subject of a private discussion i am having with thomas. apart from that, some comments/clarifications follow inline... > > The reasons why we have two implementations is, Stefan and I could not > agree on a few implementation details. My view is: > > * Stefan assumes it's important to use the content hash as the node id, > while I think this hurts performance too much (as the randomly distributed > node ids hurt storage performance in Jackrabbit 2). With the copy-on-write > model it is even a bigger performance problem because each time a node is > changed it gets a new node id (I didn't think about this first). That > means even small repositories are problematic if there are many changes. when i started the MicroKernel sandbox project about a year ago i thought (and still think so) that a microkernel should support clustering ootb. furthermore, mvcc seemed to be a promising approach to address the concurrency issues we're suffering from in jackrabbit v1-2.*. there are not that many hierarchical mvcc-based repositories around to learn from. the obvious candidates IMO were svn and git. while svn and git do use a very similar internal versioning model one important difference is the choice of identifiers. svn uses a numeric counter while git is based on a content-addressed (hash) model, the content-hash identifiers are a key aspect of git's architecture. svn is client-server based while git uses a decentralized distributed model. my assumption was that our clustering implementation could leverage the content-addressed model since it should e.g. make it easier to sync remote (sub)trees based on the content hash. so far, WRT a clustering implementation, we're still on square 1. as long as we don't have a clear idea of how to support clustering i am rather reluctant to already give up on the content-addressable model. > > * Stefan implemented a different way to represent large child node lists. > He used a h-tree (the hash code of the child node name), which means child > nodes are pseudo-randomly distributed. I think this hurts performance too > much (same reason as above: a stored index on randomly distributed keys is > required). the h-tree approach was my first take at supporting flat hierarchies. it's intentionally simple and does have a few advantages (e.g. efficient diffing of 2 large child node entries collections) it's probably not the final answer to the problem of flat hierarchies. since we can't assume that child node names do follow a specific pattern (e.g. n1-n99999999) i don't follow your performance-related reasoning. > > > * Stefan believes concurrent write operations are very important while I > believe this will not increase write throughput as much as it complicates > the implementation (Stefan implementations merges changes while my > implementation does not). > > > * Stefans implementation re-constructs the journal by diffing the node > tree. I believe this is troublesome because it is not always possible to > re-construct the journal with regards to re-order and move operations. > Also I believe this adds more complexity that the possible benefit > (because the journal doesn't need to be stored). In my implementation the > journal is stored. i've considered storing the diff of a commit in the revision a while ago. while it would be relatively easy to implement i currently don't see an immediate benefit compared to diffing which OTOH is very efficient thanks to the content-addressable model. i imagine that in a clustering scenario there's a need to compute the changes between 2 non-consecutive revisions, potentially spanning a large number of intermediate revisions. just diffing 2 revsisions is IMO probably more efficient than reconstructing the changes from a large number of revisions. cheers stefan > > There is quite a lot of common code, for example the data store, parsing > and constructing JSON / JSOP. My implementation consists of the classes in > org.apache.jackrabbit.mk.simple. The classes NodeImpl, NodeList, > NodeListSmall are used again in multiple different modules (the index and > the wrapper implementations for example). So what is really unique in my > "storage" implementation is the 3 NodeMap implementations, NodeListTrie to > support large child node lists, the Revision class, and SimpleKernelImpl. > > Regards, > Thomas > >
