[jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Thomas Müller <th...@day.com>]

The current Jackrabbit clustering doesn't scale well for writes
because all cluster nodes use the same persistent storage. Even if
persistence storage is clustered, the cluster journal relies on
changes being immediately visible in all nodes. That means Jackrabbit
clustering can scale well for reads, however it can't scale well for
writes. This is a property Jackrabbit clustering shares with most
clustering solutions for relational databases. Still, it would make
sense to solve this problem for Jackrabbit 3.

== Current Jackrabbit Clustering ==

[Cluster Node 1]  <--> | Shared
[Cluster Node 2]  <--> | Storage

I propose a different architecture in Jackrabbit 3:

== Jackrabbit 3 Clustering ==

[Cluster Node 1]  <-->  [ Local Storage ]
[Cluster Node 2]  <-->  [ Local Storage ]

Please note that shared node storage is still supported for things
like the data store, but no longer required or supported for the
persistent storage (currently called PersistenceManager).

Instead, the cluster nodes should merge each others changes
asynchronously (except operations like JCR locking, plus potentially
other operations that are not that common; maybe even node move). With
"asynchronously" I mean usually within a second or so, but potentially
minutes later depending on configuration, latency between cluster
nodes, and possibly load. Similar to NoSQL systems.

== Unique Change Set Ids ==

For my idea to work, we need globally unique change set ids. Each
change set is stored in the event journal, and can be retrieved later
and sent to other cluster nodes. I suggest that events are grouped
into change sets so that all events within the same session.save()
operation have the same change set id. We could also call it
transaction id (I don't mind). Change set ids need to be unique across
all cluster nodes. That means, the change set id could be:

changeSetId = nanosecondsSince1970 * totalClusterNodes + clusterNodeId

Let's say if you have 2 cluster nodes currently and expect to add a
few more later (up to 10), you could use the formula:

changeSetId = nanosecondsSince1970 * 10 + clusterNodeId

To support more than 10 cluster nodes the formula would need to be
changed (that could be done at runtime). It doesn't necessarily need
to be this formula, but the change set id should represent the time
when the change occurred, and it should be unique.

== How to Merge Changes ==

Changes need to be merged so that all cluster nodes end up with the
same data (you could call this "eventually consistent").

New changes are not problematic can be applied directly. This includes
local changes of course, because the change set id of local changes is
always newer than the last change.

Changes with change set ids in the future are delayed. Cluster nodes
should have reasonably synchronized clocks (it doesn't need to be
completely exact, but it should be reasonably accurate, so that such
delayed events are not that common).

So the only tricky thing are changes that happened in the past, in
another cluster node, if the same data was changed in this cluster
node (or another cluster node) afterwards (afterwards mean with a
higher change set id). To find out that a change happened in the past,
each node needs to at least know the change set id of the last change.
There are multiple solutions:

== Solution A: Node Granularity, Ignore Old Changes ==

Here, each node only need to know when it was changed the last time.
If the change set id is older than that, changes to its properties and
child node list are ignored. That means, if two cluster nodes
concurrently change data in a node, the newer change wins, and the
older change is lost. This is a bit problematic for example when
concurrently adding child nodes: Only the added child node of the
newer change survives, which is probably unexpected.

== Solution B: Merge Old Changes ==

Here, we need an efficient way to load the list of changes (events) to
a node since a certain time. Now, when merging a change, the old
versions of the node need to be loaded or re-constructed, and then the
old change needs to be applied as if it already happened before the
newer change. Let's say we know about the two versions:

v1: node a; child nodes b, c, d; properties x=1, y=2
event t9: add child node e, set property x=2, remove property y
v9: node a; child nodes b, c, d, e; properties x=2

The change to merge happend in the past:

event t3: add child node f, remove child node b, set property y=3,
remove property x, set property z=1

Now the result would be:

v9(new): node a, child nodes c, d, e, f; properties x=2, z=1

There are other ways to merge the changes of course (for example, only
merge added child / removed child nodes). I think there are some
tricky problems, however I think it's relatively easy to ensure the
algorithm is correct using a few randomized test cases. No matter what
the merge rules are, they would need to be constructed so that at the
end of the day, each cluster node would end up with the exact same
data, for all possible combination and order of changes.

Regards,
Thomas

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Raffaele Sena <ra...@gmail.com>]

Thomas, I am not sure if you are proposing to add a more "asynchronous"
PersistenceManager or completely change the behaviour of the current one.

While I would love a system that can scale well for reads and writes, and
while I understand that there is a class of applications that are well
served by "eventual consistency" I think a system like Jackrabbit, mainly
used for content publishing and delivery over the web will suffer from such
implementation (but I may be wrong).

Here are a few cases where I think eventual consistency doesn't work (and I
am assuming there is a web application like Sling or CMIS that exposes the
JCR APIs via REST, and that each webserver is connected to a different JCR
instance) :

1) A pure REST system where a client uploads a file via POST/PUT (write),
receives a new URL in return and fetches the new node information via GET
(read).

2) A blog system where the publisher upload an image and the content page
refreshes to show the image

3) A real-time collaboration system (like a chat room) where a user uploads
a file and broadcasts the file URL and all other participants try to
view/download the file.

#1 and #2 could potentially be non-problems assuming the cluster is behind a
load balancer configured for session affinity (so two requests from the same
client will go to the same server) and/or by making sure client and server
supports keep-alive (again the same client is hitting the same server), but
actually I would say these are more "hidden" problems than non-problems. One
day the request will go through a proxy that doesn't support keep-alive, or
a browser that is misconfigured, or the load balancer will try to better
"balance" requests and these will become problems.

#3 I would think is always a problem, because multiple clients will always
hit different webservers, and so different JCR instances.

I agree that keeping the interval between "merges" very short will mitigate
the problem, but again, there will always be the chance that one server
slows down and doesn't synchronize in time and the problem will appear (and
it will be very difficult to diagnose).

Some of the NoSQL implementations address this problem by making the client
deal with inconsistencies and this means most of the times having the client
read from multiple servers and then compare the results. This works, but
again if I want a system that is always consistent isn't it easier to keep
consistency at the write level ?

Also, I think that both the current system and this new system work well
with a reasonably small cluster (i.e. <= 10 machines) but may degrade
quickly if the cluster gets much larger (and this is just guts feeling, I
really don't have any data to corroborate this :)

If the goal is to enable much larger clusters probably the system should be
designed to support some kind of sharding/partitioning (i.e. if I have a
cluster with 100 machines do I really want to have each machine replicate
the full repository or should nodes be replicated only on a small number of
machines ?). Of course this open a new can of worms because there is a set
of operations that don't work well on a partitioned system. Search is
probably fine, because it should be easy to do multiple searches on the
different partitions and merge the results. Transactions may be tricky
because you may be dealing with nodes in different partitions and you'll
need to synchronize operations between them.

Note that pure NoSQL systems solve this problem by saying "well you can't do
that" or "do it in the client" and they expose a very limited set of
operations, i.e. only put or get, so that they can scale. But I suspect that
trying to apply some of the NoSQL scalabilty tricks to a system with a rich
set of operations like JCR is going to be hard.

But again, as long as there is the option to configure the system to work
"synchronously" or "asynchronously" depending on the use cases (and as long
as the "synchronous" version is not penalized by the new design) it's worth
pursuing.

-- Raffaele


On Tue, Oct 19, 2010 at 3:24 AM, Thomas Müller <th...@day.com>wrote:

> The current Jackrabbit clustering doesn't scale well for writes
> because all cluster nodes use the same persistent storage. Even if
> persistence storage is clustered, the cluster journal relies on
> changes being immediately visible in all nodes. That means Jackrabbit
> clustering can scale well for reads, however it can't scale well for
> writes. This is a property Jackrabbit clustering shares with most
> clustering solutions for relational databases. Still, it would make
> sense to solve this problem for Jackrabbit 3.
>
> == Current Jackrabbit Clustering ==
>
> [Cluster Node 1]  <--> | Shared
> [Cluster Node 2]  <--> | Storage
>
> I propose a different architecture in Jackrabbit 3:
>
> == Jackrabbit 3 Clustering ==
>
> [Cluster Node 1]  <-->  [ Local Storage ]
> [Cluster Node 2]  <-->  [ Local Storage ]
>
> Please note that shared node storage is still supported for things
> like the data store, but no longer required or supported for the
> persistent storage (currently called PersistenceManager).
>
> Instead, the cluster nodes should merge each others changes
> asynchronously (except operations like JCR locking, plus potentially
> other operations that are not that common; maybe even node move). With
> "asynchronously" I mean usually within a second or so, but potentially
> minutes later depending on configuration, latency between cluster
> nodes, and possibly load. Similar to NoSQL systems.
>
> == Unique Change Set Ids ==
>
> For my idea to work, we need globally unique change set ids. Each
> change set is stored in the event journal, and can be retrieved later
> and sent to other cluster nodes. I suggest that events are grouped
> into change sets so that all events within the same session.save()
> operation have the same change set id. We could also call it
> transaction id (I don't mind). Change set ids need to be unique across
> all cluster nodes. That means, the change set id could be:
>
> changeSetId = nanosecondsSince1970 * totalClusterNodes + clusterNodeId
>
> Let's say if you have 2 cluster nodes currently and expect to add a
> few more later (up to 10), you could use the formula:
>
> changeSetId = nanosecondsSince1970 * 10 + clusterNodeId
>
> To support more than 10 cluster nodes the formula would need to be
> changed (that could be done at runtime). It doesn't necessarily need
> to be this formula, but the change set id should represent the time
> when the change occurred, and it should be unique.
>
> == How to Merge Changes ==
>
> Changes need to be merged so that all cluster nodes end up with the
> same data (you could call this "eventually consistent").
>
> New changes are not problematic can be applied directly. This includes
> local changes of course, because the change set id of local changes is
> always newer than the last change.
>
> Changes with change set ids in the future are delayed. Cluster nodes
> should have reasonably synchronized clocks (it doesn't need to be
> completely exact, but it should be reasonably accurate, so that such
> delayed events are not that common).
>
> So the only tricky thing are changes that happened in the past, in
> another cluster node, if the same data was changed in this cluster
> node (or another cluster node) afterwards (afterwards mean with a
> higher change set id). To find out that a change happened in the past,
> each node needs to at least know the change set id of the last change.
> There are multiple solutions:
>
> == Solution A: Node Granularity, Ignore Old Changes ==
>
> Here, each node only need to know when it was changed the last time.
> If the change set id is older than that, changes to its properties and
> child node list are ignored. That means, if two cluster nodes
> concurrently change data in a node, the newer change wins, and the
> older change is lost. This is a bit problematic for example when
> concurrently adding child nodes: Only the added child node of the
> newer change survives, which is probably unexpected.
>
> == Solution B: Merge Old Changes ==
>
> Here, we need an efficient way to load the list of changes (events) to
> a node since a certain time. Now, when merging a change, the old
> versions of the node need to be loaded or re-constructed, and then the
> old change needs to be applied as if it already happened before the
> newer change. Let's say we know about the two versions:
>
> v1: node a; child nodes b, c, d; properties x=1, y=2
> event t9: add child node e, set property x=2, remove property y
> v9: node a; child nodes b, c, d, e; properties x=2
>
> The change to merge happend in the past:
>
> event t3: add child node f, remove child node b, set property y=3,
> remove property x, set property z=1
>
> Now the result would be:
>
> v9(new): node a, child nodes c, d, e, f; properties x=2, z=1
>
> There are other ways to merge the changes of course (for example, only
> merge added child / removed child nodes). I think there are some
> tricky problems, however I think it's relatively easy to ensure the
> algorithm is correct using a few randomized test cases. No matter what
> the merge rules are, they would need to be constructed so that at the
> end of the day, each cluster node would end up with the exact same
> data, for all possible combination and order of changes.
>
> Regards,
> Thomas
>

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Ian Boston <ie...@tfd.co.uk>]

On 19 Oct 2010, at 11:24, Thomas Müller wrote:

> changeSetId = nanosecondsSince1970 * totalClusterNodes + clusterNodeId

I have spent some time doing experiments on this, here are some observations based on those experiments. (could be totally irrelevant to this discussion, sorry for the noise if it is)

A sequential number helps since you know the order and can maintain lookahead and lookback buffers to ensure you replay in sequence.
Performing master election and then working mean time between all nodes in the cluster and offset of time averaging a request response travel time gives offset of all nodes relative to one another allowing real time clock sync with diffs, you do need to do more than one message in the master election to generate a good measurement of time offset. ( ideally measure until mean is stable)

Once you have that, I would recommend BigInt storage and reserve 4 digits for the cluster ID.
I would also not use nano seconds but make the ID generator in each JVM synchronised and start a rapid counter reserving 10K ticks per ms. Server offsets are never going to be ns accurate and who knows which conflicting change is right in the ns range. so the structure of the change set ID is:

((((serverOffset+msSince1970)*1000)+perMSCounter)*1000)+cluserNodeId

This generates a cluster wide sequence where each counter runs independently on each server only blocked by  very small sync block. The sequence has holes in it. Interestingly if you can accept that the sequence is reliable (ie after a certain time delay all events have arrived and none were lost), it can be used as the basis for the sequence in the current (2x) ClusterNode implementation as the replay of a Journal does not require a hole free sequence. (AFAICT)  The sequence can be checked for lost events if each subsequent event contains the previous ID.

The clusterNodeID is taken from a position in a List of clusterNodeNames that is shared on master election, the only thing the master does is co-ordinate that list and determine clock offsets. That also removes any management of the range, unlike Cassandra which shards the ID range over the cluster from the start.

The other thing I have found is necessary is to propagate version information of changes so when a remote node receives an event it knows, that if it doesn't have the current version locally, it knows which node within the cluster does, giving just-in-time-constent rather than eventially-consistent.

I am sorry if this is old information, I havent been following the JR3 discussions too closely, but I hope it helps. Once other thing you might want to have a quick look at is the Quorum implementation in Cassandra which might be relevant to making certain areas more acid than basic.


What you do with the data once you have the sequence and event distribution is another matter, I guess you are thinking of distributing the content over the entire cluster rather than making it local to each node.

HTH
Ian
 

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Thomas Müller <th...@day.com>]

Hi,

> See section 7 "Vector Time". Also see [1] from slide 14 onwards for a more
> approachable reference.
> [1] http://www.cambridge.org/resources/0521876346/6334_Chapter3.pdf

Thanks! From what I read so far it sounds like my idea is called "Time
Warp" / "Virtual Time".

On page 10 and 11 there is the notion of "Total Ordering": "The main
problem in totally ordering events is that two or more events at
different processes may have identical timestamp." - "A tie-breaking
mechanism is needed to order such events." - "Process identifiers are
linearly ordered and tie among events with identical scalar timestamp
is broken on the basis of their process identifiers." This is what I
meant with "+ clusterNodeId"

Vector time and Matrix time: I think it would need too much memory -
if the dimension of vector clocks is the number of cluster nodes, then
the number of dimensions would change whenever you add a cluster node.

Time Warp matches my suggestion: Page 33 says "Time Warp relies on the
general lookahead-rollback mechanism where each process executes
without regard to other processes having synchronization conflicts." -
it sounds like my proposal (I specially like the term "Time Warp").
"If a conflict is discovered, the offending processes are rolled back
to the time just before the conflict and executed forward along the
revised path." "Virtual time is implemented a collection of several
loosely synchronized local virtual clocks."

Regards,
Thomas

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Michael Dürig <mi...@day.com>]

>> we could leverage a virtual time algorithm
>
> I read the paper, but I don't actually understand how to implement it.

See section 7 "Vector Time". Also see [1] from slide 14 onwards for a 
more approachable reference.

Michael

[1] http://www.cambridge.org/resources/0521876346/6334_Chapter3.pdf

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Thomas Müller <th...@day.com>]

Hi,

> You wrote: "I think the persistence API should be synchronous as it is
> now." Which I understand as the persistence layer returning a save()
> call only when the entire cluster has been "written to".

It seems I was unclear. This is exactly what I *don't* want for
Jackrabbit 3. In the current Jackrabbit implementation, the
storage.save() call indeed returns only when the change is available
on all cluster nodes. And that is exactly what doesn't scale. What I
want for Jackrabbit 3 is: the storage.save() call on a cluster node
returns as soon as the data was written on *this* cluster node
(locally). But not on *other* cluster nodes. As I already wrote,
"cluster nodes should merge each others changes asynchronously".

> the observation listeners will be called out of order

Not necessarily. The spec doesn't say when observation listeners are
called (I don't talk about synchronous observation listeners here,
because they are not part of the spec). Regular observation listeners
might be called 1 second or 1 minute after the event. Now if
Jackrabbit 3 would guarantee to asynchronously merge changes within 2
seconds, and delay delivering local events, then Jackrabbit 3 could
deliver the events in the right order.

> with clustering you tend to ignore external events in observation listeners anyway

Yes, many application ignore such events. However Jackrabbit must
still deliver them.

Regards,
Thomas

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Alexander Klimetschek <ak...@day.com>]

On Thu, Oct 21, 2010 at 21:03, Thomas Müller <th...@day.com> wrote:
>> importance of leveraging in-memory storage
>
> In-memory storage *alone* is fast. But if used in combination with the
> current clustering architecture, then writes will not scale. They will
> be just be a bit faster (until you reach the network delay wall).

Agreed.

>> What is then the reason for asynchronous change merging, if not for
>> performance?
>
> Where did I say it's not about performance? As I already wrote: "it's
> about how to manage cluster nodes that are relatively far apart."

You wrote: "I think the persistence API should be synchronous as it is
now." Which I understand as the persistence layer returning a save()
call only when the entire cluster has been "written to". This is how
it is implemented/expected from persistence managers currently, right?
And this is slow...

>> observation listeners would not always get notified in the same order
>
> Regular observation listeners are not necessarily the problem, we
> could just delay them until the pre-defined sync delay (until things
> are in sync). The problem are *synchronous* event listeners (as I
> already wrote). The JCR API doesn't actually define them as far as I
> know.

Ah, I didn't see "synchronous".

But still, if you get changes out of order, because a local change is
handled first, while a remote change, that in a total ordering sense
happened before, arrives later at this node, the observation listeners
will be called out of order as well. However, with clustering you tend
to ignore external events in observation listeners anyway, so probably
not a big issue.

Regards,
Alex

-- 
Alexander Klimetschek
alexander.klimetschek@day.com

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Thomas Müller <th...@day.com>]

Hi,

> Network delay .. is faster than the delay of a disk

I wrote ""the network is the new disk" (in terms of bottleneck, in
terms of performance problem)". Network delay may be a bit faster now
than disk access. But it's *still* a huge bottleneck (compared to
in-memory operations), specially if cluster nodes are far apart. If
you have the complete repository in-memory, but for each operation you
need network access, then the network is the bottleneck. And I don't
want that to be the bottleneck. I know I repeat myself, but it looks
like this was not clear.

> importance of leveraging in-memory storage

In-memory storage *alone* is fast. But if used in combination with the
current clustering architecture, then writes will not scale. They will
be just be a bit faster (until you reach the network delay wall).

> What is then the reason for asynchronous change merging, if not for
> performance?

Where did I say it's not about performance? As I already wrote: "it's
about how to manage cluster nodes that are relatively far apart."

> observation listeners would not always get notified in the same order

Regular observation listeners are not necessarily the problem, we
could just delay them until the pre-defined sync delay (until things
are in sync). The problem are *synchronous* event listeners (as I
already wrote). The JCR API doesn't actually define them as far as I
know.

Regards,
Thomas

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Alexander Klimetschek <ak...@day.com>]

On Wed, Oct 20, 2010 at 11:22, Thomas Müller <th...@day.com> wrote:
> Let's discuss partitioning / sharding in another thread. Asynchronous
> change merging is not about how to manage huge repositories (for that
> you need partitioning / sharding),

Having different consistency expectations for certain parts in order
to make certain writes faster is not necessarily about huge
repositories.

> But I don't want that "the network is the new disk" (in terms of
> bottleneck, in terms of performance problem). Networking delay may be
> the bottleneck even if cluster nodes are in the same room, specially
> when you keep the whole repository in memory, or use SSDs.

Network delay in a proper setup is faster than the delay of a disk
drive nowadays (leaving out the other end of the network that has to
store the data it receives).

For some numbers, see
http://www.tele-task.de/archive/video/flash/11097/ slide starting at
about 3:21 (until ~7:00).

This underlies the importance of leveraging in-memory storage, btw, as
Jukka also pointed out.

> Asynchronous operation is bad for reservation systems, banking
> applications, or if you can't guarantee sticky sessions. Here you need
> synchronous operations or at least locking. If you want to support
> both cases in the same repository, you could use virtual repositories
> (which are also good for partitioning / sharding).

We could use virtual repositories for that, but that should be more
easily configurable then and make sure it is performant. Still, it
would need to be configurable.

> I think the persistence API should be synchronous
> as it is now.

What is then the reason for asynchronous change merging, if not for
performance? AFAIU, the synchronous operation of the (cloud)
persistence layer makes it quite slow compared to a pure local storage
(especially if that one is in-memory).

Regards,
Alex

-- 
Alexander Klimetschek
alexander.klimetschek@day.com

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Thomas Müller <th...@day.com>]

Hi,

Let's discuss partitioning / sharding in another thread. Asynchronous
change merging is not about how to manage huge repositories (for that
you need partitioning / sharding), it's about how to manage cluster
nodes that are relatively far apart. I'm not sure if this is the
default use case for Jackrabbit. Traditionally, asynchronous change
merging (synchronizing) is only used if the subsystems are offline for
some time, or if there is a noticeable networking delay between them,
for example if cluster nodes are in different countries.

But I don't want that "the network is the new disk" (in terms of
bottleneck, in terms of performance problem). Networking delay may be
the bottleneck even if cluster nodes are in the same room, specially
when you keep the whole repository in memory, or use SSDs. Also,
computers get more and more cores, and at some point message passing
is more efficient than locking.

Asynchronous operation is bad for reservation systems, banking
applications, or if you can't guarantee sticky sessions. Here you need
synchronous operations or at least locking. If you want to support
both cases in the same repository, you could use virtual repositories
(which are also good for partitioning / sharding).

My proposal is for Jackrabbit 3 only. In the extreme case, the
"asynchronous change merger" might very well be a separate thread and
use little more than the JCR API. Therefore asynchronous change
merging should have very little or no effect on performance if it is
not used. On the other hand, replication should likely be in the
persistence layer. I think the persistence API should be synchronous
as it is now.

> We could also use normal UUIDs or SHA1 hashes of the serialized change sets

That's an option, but lookup by node id and time must be efficient.
UUIDs / secure hashes are not that space efficient (that might not be
the problem). We see from Jackrabbit that indexing random data (UUIDs)
is extremely bad for cache locality and index efficiency, but if
indexing is done by time then that's also not a problem. The algorithm
I propose is sensitive to configuration changes, but you only need to
change the formula when going from "max 256 cluster nodes" to "more
than 256 cluster nodes" (for example). And you need a unique cluster
id. But I don't think that's the problem.

> we could leverage a virtual time algorithm

I read the paper, but I don't actually understand how to implement it.

> We'll probably need some mechanism for making the content
> of conflicting changes available for clients to review event if the
> merge algorithm chooses to discard them.

If we leave it up to the client to decide what to do, then things
might more easily run out of sync. But in any case there might be
problems, for example synchronous event listeners might get a
different order of events in different cluster nodes (possibly even
different events). Probably it would make sense to add some kind of
offline comparison / sync feature, similar to rsync. Actually that
could be useful even for Jackrabbit 2.

Regards,
Thomas

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Jukka Zitting <ju...@gmail.com>]

Hi,

On Tue, Oct 19, 2010 at 12:24 PM, Thomas Müller <th...@day.com> wrote:
> The current Jackrabbit clustering doesn't scale well for writes
> because all cluster nodes use the same persistent storage. Even if
> persistence storage is clustered, the cluster journal relies on
> changes being immediately visible in all nodes. That means Jackrabbit
> clustering can scale well for reads, however it can't scale well for
> writes. This is a property Jackrabbit clustering shares with most
> clustering solutions for relational databases. Still, it would make
> sense to solve this problem for Jackrabbit 3.

Agreed. The advent of the read/write web has notably increased the
importance of scalable write functionality in web backends. We aren't
seeing the full impact of this yet, but I know that many of our users
are rolling out new sites and other applications with all sorts of
commenting, tracking and social features, and that such deployments
will sooner or later start hitting our current write bottleneck.

> == Jackrabbit 3 Clustering ==
>
> [Cluster Node 1]  <-->  [ Local Storage ]
> [Cluster Node 2]  <-->  [ Local Storage ]

I'd even like to float the idea of the local storage of each cluster
node being RAM instead of a database or the file system. Instead of
persisting changes to a disk, durability could be achieved by syncing
the changes to at least one or two other cluster nodes. But that's
probably best discussed in another thread...

> == Unique Change Set Ids ==
> [...]
> changeSetId = nanosecondsSince1970 * totalClusterNodes + clusterNodeId

We could also use normal UUIDs or SHA1 hashes of the serialized change
sets as these identifiers as long as we include timestamp information
(and perhaps the identity of the originating cluster node) with the
changes. That way you wouldn't have to make assumptions about the
cluster configuration in advance.

> == How to Merge Changes ==
> [...]
> Changes with change set ids in the future are delayed. Cluster nodes
> should have reasonably synchronized clocks (it doesn't need to be
> completely exact, but it should be reasonably accurate, so that such
> delayed events are not that common).

Instead of relying on clock synchronization (many virtual servers
suffer from serious clock drift), we could leverage a virtual time
algorithm like the one described in [1].

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.2620

> == Solution A: Node Granularity, Ignore Old Changes ==

As you mentioned, this is problematic.

> == Solution B: Merge Old Changes ==

This sounds promising, but needs to be reviewed for all the potential
conflicts. We'll probably need some mechanism for making the content
of conflicting changes available for clients to review event if the
merge algorithm chooses to discard them.

BR,

Jukka Zitting

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Alexander Klimetschek <ak...@day.com>]

On Tue, Oct 19, 2010 at 23:17, Justin Edelson <ju...@justinedelson.com> wrote:
> You'd also need to ensure that a single session.save() which touched
> both "immediately" and "eventually" consistent nodes forces a queue
> flush (or at least a queue flush of changesets which touched the same
> set of eventually consistent nodes). This is possibly the trickiest
> part of the implementation.

Right, didn't think about that. Also, as Thomas pointed out,
observation listeners would not always get notified in the same order,
if conflicting merges happen, but maybe that is ok for extreme cases
(and the application expects that).

Regards,
Alex

-- 
Alexander Klimetschek
alexander.klimetschek@day.com

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Justin Edelson <ju...@justinedelson.com>]

On Tue, Oct 19, 2010 at 4:14 PM, Alexander Klimetschek <ak...@day.com> wrote:
> On Tue, Oct 19, 2010 at 12:24, Thomas Müller <th...@day.com> wrote:
>> Instead, the cluster nodes should merge each others changes
>> asynchronously (except operations like JCR locking, plus potentially
>> other operations that are not that common; maybe even node move). With
>> "asynchronously" I mean usually within a second or so, but potentially
>> minutes later depending on configuration, latency between cluster
>> nodes, and possibly load. Similar to NoSQL systems.
>
> It would be really cool if this configuration could by by path.
This would be quite cool.

> For example:
>
> /banking/accounts => immediately consistent
> /website/comments => eventually consistent
>
> AFAIK all/most NoSQL systems don't allow that, or can't, because they
> miss a content structure to base the configuration on (everything is a
> document with some generic ID string). Configuring this for the entire
> repository or workspace OTOH would break the benefit of JCR to
> integrate different applications in one system.
>
> I think implementation is fairly simple, as it only has to be handled
> at the sender: a session.save() that includes changes with "immediate
> consistency" would be synced over the cluster as it is now (using some
> fsync()-like protocol command), "eventual consistent" changes would go
> into the asynchronous cluster queue and make the save() call return as
> fast as a pure local one.
You'd also need to ensure that a single session.save() which touched
both "immediately" and "eventually" consistent nodes forces a queue
flush (or at least a queue flush of changesets which touched the same
set of eventually consistent nodes). This is possibly the trickiest
part of the implementation.

Justin

>
> Regards,
> Alex
>
> --
> Alexander Klimetschek
> alexander.klimetschek@day.com
>

Re: [jr3] Clustering: Scalable Writes / Asynchronous Change Merging

[Alexander Klimetschek <ak...@day.com>]

On Tue, Oct 19, 2010 at 12:24, Thomas Müller <th...@day.com> wrote:
> Instead, the cluster nodes should merge each others changes
> asynchronously (except operations like JCR locking, plus potentially
> other operations that are not that common; maybe even node move). With
> "asynchronously" I mean usually within a second or so, but potentially
> minutes later depending on configuration, latency between cluster
> nodes, and possibly load. Similar to NoSQL systems.

It would be really cool if this configuration could by by path. For example:

/banking/accounts => immediately consistent
/website/comments => eventually consistent

AFAIK all/most NoSQL systems don't allow that, or can't, because they
miss a content structure to base the configuration on (everything is a
document with some generic ID string). Configuring this for the entire
repository or workspace OTOH would break the benefit of JCR to
integrate different applications in one system.

I think implementation is fairly simple, as it only has to be handled
at the sender: a session.save() that includes changes with "immediate
consistency" would be synced over the cluster as it is now (using some
fsync()-like protocol command), "eventual consistent" changes would go
into the asynchronous cluster queue and make the save() call return as
fast as a pure local one.

Regards,
Alex

-- 
Alexander Klimetschek
alexander.klimetschek@day.com