<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">I am speaking from the perspective of
the algorithm and less from my opinions of the way the system
should work as a whole. <br>
<br>
On 08/01/2014 03:02 PM, Randall Hauch wrote:<br>
</div>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">I’ve really enjoyed learning about what AeroGear has
been doing with data sync. This is a tough problem, but finding a
solution is really important. Both data sync POCs appear to use
Differential Synchronization, or DS [1]. I was not familiar with
the paper until today, but after reading it I do have a few
questions/comments. Bear with me; this is a long post.
<div><br>
</div>
<div>DS is clearly targeted for use within a collaborative
document editor, where there are multiple clients concurrently
editing the same document, and at any one time there are a
relatively small number of documents being edited; you can get a
feel for this by looking at figures 5 and 7 in the paper [1] —
look at the amount of server memory and CPU required to perform
DS on just one document being edited by a half-dozen clients.
Also, in a collaborative document editor, clients are often
continually making changes even as they attempt to synchronize
with the server. <br>
</div>
</blockquote>
It doesn't actually make any claims about CPU or memory usage. A
shadow document is needed for each connection. For documents which
are infrequently edited, the shadow doc can easily be frozen to disk
until an edit comes in.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div><br>
</div>
<div>(It’s interesting that Google Docs, and Google Wave before
it, appear to use Operational Transformation [2] rather than DS.
OT might also make it easier to implement undo/redo, which works
really well in Google Docs.)</div>
</blockquote>
That is probably because OT, Docs, and Apache Wave are all older
then Diff-sync. OT is also a much more complicated algorithm in my
experience (and from browsing around on wikipedia)<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div><br>
</div>
<div>An MBaaS or any other database-like service is very
different. It has to host multiple applications (i.e.,
databases), each with multiple collections containing
potentially millions of entities (e.g., JSON documents). The
entities themselves are more fine-grained and smaller than
collaborative documents (though probably a bit coarser-grained
and larger than a single record in a RDBMS). Many clients might
be reading and updating lots of documents at once, and the data
service has to coordinate those changes. A single batch update
from one client might request changes to dozens of entities. And
the clients can/will always wait for confirmation that the
server made the requested changes before continuing (unless the
client is offline); or at a minimum can enqueue the requested
changes.</div>
</blockquote>
Two quick things. A document is just a collection of entities and
can be structured to reduce this problem (especially is we are
faking it on a RDBMS with particularly sadistic abuses to an ORM).
Clients don't have to wait for the edits to be merged on the server
and the nature of diff-sync gives us batching for free.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div><br>
</div>
<div>Given these characteristics, using DS within the data service
might be extremely expensive in terms of CPU and memory</div>
</blockquote>
or it might not be. We need data, use cases, etc to test and see
what happens.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div>, and difficult for a DS-based service to implement all of
the features necessary. </div>
</blockquote>
Which features? Features of the algorithm of features of the
application? The algorithm is really REALLY simple for what we get
out of it.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div>First, the data service doesn’t really know which entities
are being“edited”; instead, connected clients read entities,
make changes locally, then request the service make those
changes. </div>
</blockquote>
I disagree. The service knows documents which the client has a
connection to/active session for. It most certainly knows which
entities are being edited.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div>Secondly, every time a change comes in, to compute the diff
the service would have to read the persisted entity; this not
only is inefficient, but this also makes it more difficult to
scale and handle the concurrency, consistency, atomicity, and
serializability guarantees. </div>
</blockquote>
See earlier comment about sadistic abuses of an ORM. Yes we have to
be aware of the RDB underneath the sync server, but I don't think
this is a problem with the algorithm.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div>Thirdly, what would the data service need to do when a client
connects and asks for the changes since it was last connected? </div>
</blockquote>
Send it the diff of the clients serverside shadow and the server's
current document. This diff will get sent to the client, merged
with the clients shadow, and the diff of that will get sent back to
the server. Repeat until the client is in sync.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div>The data service might be able to quickly find out which
entities were modified since then, but computing the diffs
(relative to the time the client last connected) for all of
those changed entities would be very complicated. </div>
</blockquote>
It isn't.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div>It may be easier and better for the data service to record
the individual changes (edits) made by each transaction, and
then to use that information to compute the effective diffs from
some period of time. In fact, these recorded edits might also be
useful to implement other features within the data service; see
CQRS [3] and [4].</div>
</blockquote>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div><br>
</div>
<div>What is really required by the client when trying to
synchronize its data after being disconnected? Assuming the
client can say which subset of entities it’s interested in when
it reconnects (via some criteria in a subscription), does the
client want:</div>
<div>
<ol class="MailOutline">
<li>the new versions of those entities that changed;</li>
</ol>
</div>
</blockquote>
No<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div>
<ol class="MailOutline">
<li>the deltas in the entities; and/or</li>
</ol>
</div>
</blockquote>
Yes<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div>
<ol class="MailOutline">
<li>all of the events describing the individual changes made
to all of those entities? <br>
</li>
</ol>
</div>
</blockquote>
No. <br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div><br>
</div>
<div>It may not matter for clients that don’t allow local offline
changes, but what might the preferred approach be for clients
that do allow offline changes? Option 1 is clearly the easiest
from the perspective of the data service, but options #2 and #3
can certainly be handled. With option #1, can the client do
something like DS and maintain copies of each original
(unmodified) entity so that it can compute the differences? Does
this (perhaps with a journal of edits made while offline)
provide enough info for the client to properly merge the local
changes, or does the client really need the individual events in
#3 so that it can, for example, know that some local changes
were made to now-out-date data?</div>
</blockquote>
Except in the case of a merge error, the algorithm handles long
offline periods with edits just fine. If there is a merge error the
user/application will have to manually merge the documents somehow.<br>
<br>
One of the things to keep in mind is on mobile devices the radio is
the most expensive thing you can control as an application. Any
decision we make should err toward only sending as little data as
possible as few times as possible.<br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div><br>
</div>
<div>Will the same option work for online notifications? After
all, it’d be great if the same mechanism was used for data-sync,
offline (push) notifications, and online notifications (events).</div>
</blockquote>
I don't understand your question. <br>
<blockquote
cite="mid:36AD5F9D-31D4-406C-B8CD-25E639187C0C@redhat.com"
type="cite">
<div><br>
</div>
<div>Finally, the data sync APIs of the data service should
support the use of local client storage, but it should not
require it.</div>
<div><br>
</div>
<div>Best regards,</div>
<div><br>
</div>
<div>Randall</div>
<div><br>
</div>
<div><br>
</div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>[1] <a moz-do-not-send="true"
href="http://research.google.com/pubs/pub35605.html">http://research.google.com/pubs/pub35605.html</a></div>
</div>
</div>
</div>
</div>
</div>
</div>
<div>[2] <a moz-do-not-send="true"
href="http://en.wikipedia.org/wiki/Operational_transformation">http://en.wikipedia.org/wiki/Operational_transformation</a></div>
<div>[3] <a moz-do-not-send="true"
href="http://www.infoq.com/presentations/Events-Are-Not-Just-for-Notifications">http://www.infoq.com/presentations/Events-Are-Not-Just-for-Notifications</a></div>
<div>[4] <a moz-do-not-send="true"
href="http://martinfowler.com/bliki/CQRS.html">http://martinfowler.com/bliki/CQRS.html</a></div>
<div><br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
aerogear-dev mailing list
<a class="moz-txt-link-abbreviated" href="mailto:aerogear-dev@lists.jboss.org">aerogear-dev@lists.jboss.org</a>
<a class="moz-txt-link-freetext" href="https://lists.jboss.org/mailman/listinfo/aerogear-dev">https://lists.jboss.org/mailman/listinfo/aerogear-dev</a></pre>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
Summers Pittman
>>Phone:404 941 4698
>>Java is my crack.
</pre>
</body>
</html>