Differential Synchronization: Shadow/Backup Revision Control and its Garbage Collection
by Lukáš Fryč
Hey guys,
TL;DR: there are ways how to make the memory footprint of Differential
Synchronization (DS) very low; if we assume that JSON patches are
reversible and we create cumulative patches from series of individual
patches, we can use (smart, garbage-collactable) revision control for
storage of documents that server need to maintain.
----
I had an idea in my head that for couple of days as I was becoming familiar
with how Differential Synchronization (DS) works and studying Dan's and
Luke's impl.
I share the concern that Randall expressed in earlier thread - the DS in
its pure version doesn't scale for huge amount of users when connected to
one server.
Sure, the algorithm can be scaled trivially by adding new nodes that uses
very same algorithm as is used for client<->server. But that doesn't mean
it is something that we should do regularly to get more memory available.
Instead, I was thinking about limiting a memory that server needs to
maintain in any point in time.
In pure DS, server have to maintain all copies of documents that clients
ever requested. Even worse, it has to maintain two copies - "shadow" and
"backup",
So, in worst case, 2 x N copies of document will be maintained by the
server for N clients.
-----
The DS algorithm doesn't tell us how the "shadow" and "backup" documents
should be stored.
We can transparently plug in a storage that will be clever about how to use
"backups" and "shadow".
-----
CONCEPTS:
1) REVISION CONTROL
In order to limit a number of documents we need to maintain in server's
memory, we can come with a system where just last known state is remembered
in full version. Together with last known version, we remember also history
of the document for each revision as it was patched by clients.
But server doesn't have to maintain full history of the document, it
maintains just revisions that are known to its clients (that revision is
known by DS for each client out of the box).
2) GARBAGE COLLECTION
Server trivially knows what versions are mantained by client, so it can get
rid of those revisions that are no longer needed.
First, it can cut all the history that is older than the oldest version of
document throughout all its clients.
Secondly, it can accumulate the serious of patches between states so that
it doesn't have to maintain full history, but just revisions that is known
to any of those clients.
----
DIAGRAM:
I've attached a picture for illustration of the revision control / garbage
collection, it does not illustrate algorithm itself (Dan did awesome job
describing DS here [3]).
In the attached diagram, you can see four clients with different revisions:
Client 1: revision X
Client 2: revision X+3
Client 3: revision X+3
Client 4: revision X+4
If any of the clients reaches server, server can reconstruct the document
(shadow and backup) for given client revision and the DS algorithm then can
operate as normally (that's why it is transparent from algorithmic point of
view).
If server comes to garbage collection, it can scan through available client
revisions. As it identifies, that the oldest known revision is X, it can
remove patch for X-1 and less as they are no longer needed.
Later, it can even more optimize, and accumulate patches so that the only
information he knows is how to get to the revision for each participating
client. In the picture, he can compute cumulative patch for getting from
state X to state X+3, as X+1 and X+2 themselves are not needed.
(Patch accumulation is actually something that Google Wave does in its
Operational Transformation implementation, just there it is called
cumulative Operations).
----
Then it comes to caching strategies, you can maintain caches of things like
last recently used revisions (they don't need to be computed each time).
You can store some documents and their revision history to the disk (fully
or partially), etc.
----
THE USE CASE:
1000 employees maintain one document - Contact List - on their smartphones
400 of those employees has mobile data plan, so they want to synchronize
almost immediately as they are notified about changes. The rest of the
devices is connected rather sparely.
If one employee changes data, 600 devices are notified about the change
immediately (some on data plan, some through Wifi, etc.) Those clients all
have version say X+3, because they are synchronized proactively.
These clients reach the server in say <10 seconds after that employee did
the change.
First client reaches server and ask for version X+3 (it probably is still
in the memory, but if it isn't, it is deconstructed and placed into MRU
cache). All of the others reaches the server and re-synchronize themselves
against the one copy of backup/shadow that is in the memory already.
The other clients will reach the server later, as they are connecting to
Wifi, say in 5 minutes to 24 hours. They will have even older versions,
such as X. Those clients will require more computation, but at the end the
server can resolve them and through their revisions out of the window.
At the end, there are clients that didn't connected for days, maybe months
- I suggest we don't actually use DS here and fallback to e.g. slow
synchronization (show me what you have, I will show you mine), because
maintaining full history for longer period of days may be too resource
demanding (configurable?).
Obviously, 1000 is not much, but this can scale to pretty decent numbers if
we use hybrid approach (fallback to other sync strategies if revision is
already forgotten by a server).
----
WORST CASE:
we still have to maintain all the document revisions, but practically it
won't happen :-)
----
ASSUMPTIONS:
1. patches are reversible (we are able to compute reverse patch for each
patch sent by client)
2. patches are cumulative (we are able to compute aggregated patch from
series of patches)
For 1, it seems many of JSON-patch libraries actually implement it (Java,
JavaScript) [1, 2]
For 2, it again seems some libraries implement it and if not, we can
implement it or even use brute-force - compute a patch between two documents
----
It's not the only way how to make it scale, but it does solve the problem
pretty independently of the DS algorithm and still leaves the algorithm
clean and simple.
Cheers,
~ Lukas
[1] https://github.com/fge/json-patch
[2] https://github.com/benjamine/jsondiffpatch
12 years, 1 month
Data Sync: use of IETFs formats
by Lukáš Fryč
Hey guys,
I've recently encountered two standard formats that standardizes the HTTP
PATCH, that could be important for formats we use for Data Sync features:
*json-patch*
http://tools.ietf.org/html/rfc6902
Defines set of operations that you can do with JSON object such as: add,
remove, replace, move, copy, replace, test.
[
{ "op": "test", "path": "/a/b/c", "value": "foo" },
{ "op": "remove", "path": "/a/b/c" },
{ "op": "add", "path": "/a/b/c", "value": [ "foo", "bar" ] },
{ "op": "replace", "path": "/a/b/c", "value": 42 },
{ "op": "move", "from": "/a/b/c", "path": "/a/b/d" },
{ "op": "copy", "from": "/a/b/d", "path": "/a/b/e" }
]
The structure of the patch is list of operations, not the document itself.
We could actually rewrite DiffSync Server to use it (since it is very close
to that format).
*json-merge-patch* (draft)
http://tools.ietf.org/html/draft-ietf-appsawg-json-merge-patch-0
Defines a format where you send updated parts of the JSON Object itself in
same structure as original object:
e.g.: object:
{
"a": "b",
"c": {
"d": "e",
"f": "g"
}
}
patch:
{
"a":"z",
"c": {
"f": null
}
}
Cheers,
~ Lukas
12 years, 1 month
Should Cordova push plugin dependencies be shrinkwrapped?
by Gorkem Ercan
Hi All,
I have been working cordova push quickstarts and noticed that on Android
installation through JBoss tools started to fail.
After a bit of investigation I figured that the failure occurs because
push plugin defines cordova plugin "com.google.playservices" as a
dependency through a git URL[1] that points to the master of the plugin's
repo. Unfortunately this repo received a change [2] which started to use a
new feature that was not implemented for JBoss tools. In this particular
case, I am already implementing the missing feature so it should be all
good soon. However I have doubts that referencing a dependency through
master is a good idea. I think it may not only make it really difficult for
us to reproduce cases but also unexpected behaviour may just appear.
[1] https://github.com/MobileChromeApps/google-play-services
[2]
https://github.com/MobileChromeApps/google-play-services/commit/41c19152c...
12 years, 1 month
errors in cordova / android app
by hagai.sela
Hi,
I am trying to use aerogear to send push notifications to cordova
application which runs on my android device.
I followed this tutorial:
http://aerogear.org/docs/guides/aerogear-push-cordova-android/cordova-and...
When my app loads in the device I am getting this error:
Could not find method
com.google.android.gms.gcm.GoogleCloudMessaging.getInstance, referenced from
method
org.jboss.aerogear.android.impl.unifiedpush.AeroGearGCMPushRegistrar$2.get
Help, please. This is the complete log file:
09-04 12:45:09.724: I/dalvikvm(14690): Debugger is active
09-04 12:45:09.884: I/System.out(14690): Debugger has connected
09-04 12:45:09.884: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:10.084: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:10.284: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:10.484: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:10.684: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:10.884: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:11.084: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:11.284: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:11.484: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:11.684: I/System.out(14690): waiting for debugger to settle...
09-04 12:45:11.884: I/System.out(14690): debugger has settled (1310)
09-04 12:45:11.914: I/CordovaLog(14690): Changing log level to DEBUG(3)
09-04 12:45:11.914: I/CordovaLog(14690): Found start page location:
index.html
09-04 12:45:11.914: D/Whitelist(14690): Unlimited access to network
resources
09-04 12:45:11.914: D/CordovaActivity(14690): CordovaActivity.onCreate()
09-04 12:45:11.924: V/WebViewChromium(14690): Binding Chromium to the
background looper Looper (main, tid 1) {42832650}
09-04 12:45:11.934: I/chromium(14690): [INFO:library_loader_hooks.cc(112)]
Chromium logging enabled: level = 0, default verbosity = 0
09-04 12:45:11.934: I/BrowserProcessMain(14690): Initializing chromium
process, renderers=0
09-04 12:45:11.944: W/chromium(14690): [WARNING:proxy_service.cc(888)] PAC
support disabled because there is no system implementation
09-04 12:45:11.954: I/Adreno-EGL(14690): <qeglDrvAPI_eglInitialize:385>: EGL
1.4 QUALCOMM build: ()
09-04 12:45:11.954: I/Adreno-EGL(14690): OpenGL ES Shader Compiler Version:
E031.24.00.02
09-04 12:45:11.954: I/Adreno-EGL(14690): Build Date: 01/20/14 Mon
09-04 12:45:11.954: I/Adreno-EGL(14690): Local Branch:
PMH2-KK_3.5-RB1-AU61-554722-586267-set2
09-04 12:45:11.954: I/Adreno-EGL(14690): Remote Branch:
09-04 12:45:11.954: I/Adreno-EGL(14690): Local Patches:
09-04 12:45:11.954: I/Adreno-EGL(14690): Reconstruct Branch:
09-04 12:45:12.024: D/CordovaWebView(14690): CordovaWebView is running on
device made by: LGE
09-04 12:45:12.034: D/JsMessageQueue(14690): Set native->JS mode to 2
09-04 12:45:12.034: D/CordovaActivity(14690): CordovaActivity.init()
09-04 12:45:12.054: D/CordovaWebView(14690): >>>
loadUrl(file:///android_asset/www/index.html)
09-04 12:45:12.054: D/PluginManager(14690): init()
09-04 12:45:12.064: D/CordovaWebView(14690): >>> loadUrlNow()
09-04 12:45:12.064: D/dalvikvm(14690): Note: class
Lcom/lge/mdm/manager/ILGMDMDevicePolicyManager$Stub; has 319 unimplemented
(abstract) methods
09-04 12:45:12.094: I/CordovaLog(14690): Changing log level to DEBUG(3)
09-04 12:45:12.104: I/CordovaLog(14690): Found start page location:
index.html
09-04 12:45:12.104: D/Whitelist(14690): Unlimited access to network
resources
09-04 12:45:12.104: D/CordovaActivity(14690): Resuming the App
09-04 12:45:12.104: D/CordovaActivity(14690): CB-3064: The errorUrl is null
09-04 12:45:12.104: W/BaseRuntimeLoader(14690): don't
searchcom.lge.telephony.msim.QcomMSimTelephonyManagerAdaptor class
09-04 12:45:12.124: W/BaseRuntimeLoader(14690): don't
searchcom.lge.telephony.msim.MtkMSimTelephonyManagerAdaptor class
09-04 12:45:12.124: W/BaseRuntimeLoader(14690): don't
searchcom.lge.telephony.msim.QcomMSimTelephonyManagerAdaptor class
09-04 12:45:12.124: W/BaseRuntimeLoader(14690): don't
searchcom.lge.telephony.msim.MtkMSimTelephonyManagerAdaptor class
09-04 12:45:12.134: D/CordovaActivity(14690): Paused the application!
09-04 12:45:12.134: D/CordovaWebView(14690): Handle the pause
09-04 12:45:12.194: D/OpenGLRenderer(14690): Enabling debug mode 0
09-04 12:45:12.214: D/OpenGLRenderer(14690): GL error from OpenGLRenderer:
0x502
09-04 12:45:12.214: E/OpenGLRenderer(14690): GL_INVALID_OPERATION
09-04 12:45:12.234: I/ActivityManager(14690): Timeline: Activity_idle id:
android.os.BinderProxy@42834218 time:6453809
09-04 12:45:12.244: D/CordovaWebViewClient(14690):
onPageStarted(file:///android_asset/www/index.html)
09-04 12:45:12.244: D/CordovaActivity(14690):
onMessage(onPageStarted,file:///android_asset/www/index.html)
09-04 12:45:12.294: D/CordovaLog(14690): : Line 1 : exception firing pause
event from native
09-04 12:45:12.294: I/chromium(14690): [INFO:CONSOLE(1)] "exception firing
pause event from native", source: (1)
09-04 12:45:12.314: D/CordovaLog(14690):
file:///android_asset/www/index.html: Line 25 : Viewport target-densitydpi
is not supported.
09-04 12:45:12.314: I/chromium(14690): [INFO:CONSOLE(25)] "Viewport
target-densitydpi is not supported.", source:
file:///android_asset/www/index.html (25)
09-04 12:45:12.424: D/CordovaWebViewClient(14690):
onPageFinished(file:///android_asset/www/index.html)
09-04 12:45:12.424: D/CordovaActivity(14690):
onMessage(onPageFinished,file:///android_asset/www/index.html)
09-04 12:45:12.464: D/CordovaActivity(14690): onMessage(spinner,stop)
09-04 12:45:12.484: D/CordovaLog(14690):
file:///android_asset/www/js/index.js: Line 71 : Received Event: deviceready
09-04 12:45:12.484: I/chromium(14690): [INFO:CONSOLE(71)] "Received Event:
deviceready", source: file:///android_asset/www/js/index.js (71)
09-04 12:45:12.484: V/PushPlugin(14690): execute: action=register
09-04 12:45:12.494: V/PushPlugin(14690): execute:
data=[{"android":{"variantSecret":"e69404ed-e23b-4cff-9476-63f3ce242e35","senderID":"406666539484","variantID":"6d3153b7-f64f-47ad-b7fb-d0310532d57f"},"pushServerURL":"http:\/\/192.168.10.27:8080\/ag-push\/"}]
09-04 12:45:12.534: I/dalvikvm(14690): Could not find method
com.google.android.gms.gcm.GoogleCloudMessaging.getInstance, referenced from
method
org.jboss.aerogear.android.impl.unifiedpush.AeroGearGCMPushRegistrar$2.get
09-04 12:45:12.534: W/dalvikvm(14690): VFY: unable to resolve static method
5245: Lcom/google/android/gms/gcm/GoogleCloudMessaging;.getInstance
(Landroid/content/Context;)Lcom/google/android/gms/gcm/GoogleCloudMessaging;
09-04 12:45:12.534: D/dalvikvm(14690): VFY: replacing opcode 0x71 at 0x0005
09-04 12:45:12.534: W/dalvikvm(14690): VFY: unable to find class referenced
in signature (Lcom/google/android/gms/gcm/GoogleCloudMessaging;)
09-04 12:45:12.544: W/dalvikvm(14690): VFY: unable to find class referenced
in signature (Lcom/google/android/gms/gcm/GoogleCloudMessaging;)
09-04 12:45:12.544: E/dalvikvm(14690): Could not find class
'com.google.android.gms.gcm.GoogleCloudMessaging', referenced from method
org.jboss.aerogear.android.impl.unifiedpush.AeroGearGCMPushRegistrar$3.doInBackground
09-04 12:45:12.544: W/dalvikvm(14690): VFY: unable to resolve check-cast 766
(Lcom/google/android/gms/gcm/GoogleCloudMessaging;) in
Lorg/jboss/aerogear/android/impl/unifiedpush/AeroGearGCMPushRegistrar$3;
09-04 12:45:12.544: D/dalvikvm(14690): VFY: replacing opcode 0x1f at 0x001c
09-04 12:45:12.554: W/dalvikvm(14690): VFY: unable to find class referenced
in signature (Lcom/google/android/gms/gcm/GoogleCloudMessaging;)
09-04 12:45:12.554: I/dalvikvm(14690): Could not find method
com.google.android.gms.gcm.GoogleCloudMessaging.register, referenced from
method
org.jboss.aerogear.android.impl.unifiedpush.AeroGearGCMPushRegistrar$3.doInBackground
09-04 12:45:12.554: W/dalvikvm(14690): VFY: unable to resolve virtual method
5247: Lcom/google/android/gms/gcm/GoogleCloudMessaging;.register
([Ljava/lang/String;)Ljava/lang/String;
09-04 12:45:12.554: D/dalvikvm(14690): VFY: replacing opcode 0x6e at 0x0046
09-04 12:45:14.424: D/CordovaActivity(14690): onMessage(spinner,stop)
09-04 12:45:29.854: W/dalvikvm(14690): threadid=23: thread exiting with
uncaught exception (group=0x417f0e48)
09-04 12:45:29.884: E/AndroidRuntime(14690): FATAL EXCEPTION: AsyncTask #1
09-04 12:45:29.884: E/AndroidRuntime(14690): Process: com.speakez.userapp,
PID: 14690
09-04 12:45:29.884: E/AndroidRuntime(14690): java.lang.RuntimeException: An
error occured while executing doInBackground()
09-04 12:45:29.884: E/AndroidRuntime(14690): at
android.os.AsyncTask$3.done(AsyncTask.java:300)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
java.util.concurrent.FutureTask.finishCompletion(FutureTask.java:355)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
java.util.concurrent.FutureTask.setException(FutureTask.java:222)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
java.util.concurrent.FutureTask.run(FutureTask.java:242)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
android.os.AsyncTask$SerialExecutor$1.run(AsyncTask.java:231)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1112)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:587)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
java.lang.Thread.run(Thread.java:841)
09-04 12:45:29.884: E/AndroidRuntime(14690): Caused by:
java.lang.NoClassDefFoundError:
com.google.android.gms.gcm.GoogleCloudMessaging
09-04 12:45:29.884: E/AndroidRuntime(14690): at
org.jboss.aerogear.android.impl.unifiedpush.AeroGearGCMPushRegistrar$2.get(AeroGearGCMPushRegistrar.java:76)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
org.jboss.aerogear.android.impl.unifiedpush.AeroGearGCMPushRegistrar$2.get(AeroGearGCMPushRegistrar.java:72)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
org.jboss.aerogear.android.impl.unifiedpush.AeroGearGCMPushRegistrar$3.doInBackground(AeroGearGCMPushRegistrar.java:95)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
org.jboss.aerogear.android.impl.unifiedpush.AeroGearGCMPushRegistrar$3.doInBackground(AeroGearGCMPushRegistrar.java:87)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
android.os.AsyncTask$2.call(AsyncTask.java:288)
09-04 12:45:29.884: E/AndroidRuntime(14690): at
java.util.concurrent.FutureTask.run(FutureTask.java:237)
09-04 12:45:29.884: E/AndroidRuntime(14690): ... 4 more
09-04 12:45:29.924: I/Process(14690): Sending signal. PID: 14690 SIG: 9
--
View this message in context: http://aerogear-dev.1069024.n5.nabble.com/errors-in-cordova-android-app-t...
Sent from the aerogear-dev mailing list archive at Nabble.com.
12 years, 1 month
JMS example
by Ronald van Aken
Hi all,
Apologies if this is not the appropriate area for posting this question.
But I see in the HornetQ an example integrating with the UnifiedPush
server. However when i install the server i do not see any registration for
JMS consumers. Should I install a different package?
Thanks in advance.
Kind regards,
Ronald
12 years, 1 month
Maven repo config in pom.xml
by John Manko
I added the repo and plugin config to my pom, but I still can't find the
aerogear artifacts.
For org.jboss.aerogear:aerogear-android-push, only v0.2 and v0.1 are found,
not v1.0.
Also, getting Failed to execute goal on project blah: Could not resolve
dependencies for project .... Failed to collect dependencies for
[org.jboss.aerogear:aerogear-android:jar:1.4.0 (compile),
org.jboss.aerogear:aerogear-security:jar:1.3.1 (compile),
org.jboss.aerogear:aerogear-security-picketlink:jar:1.3.1 (compile),
com.google.android:support-v4:jar:r7 (compile),
javax:javaee-web-api:jar:6.0 (provided)]: No versions available for
android.support:compatibility-v4:jar:[18,) within specified range -> [Help
1]
I'm running in Netbeans 8, btw. Is Eclipse a requirement due to IDE plugin
support?
<repositories>
<repository>
<id>jboss-public-repository-group</id>
<name>JBoss Public Maven Repository Group</name>
<url>
https://repository.jboss.org/nexus/content/groups/public-jboss/</url>
<layout>default</layout>
<releases>
<enabled>true</enabled>
<updatePolicy>never</updatePolicy>
</releases>
<snapshots>
<enabled>true</enabled>
<updatePolicy>never</updatePolicy>
</snapshots>
</repository>
</repositories>
<pluginRepositories>
<pluginRepository>
<id>jboss-public-repository-group</id>
<name>JBoss Public Maven Repository Group</name>
<url>
https://repository.jboss.org/nexus/content/groups/public-jboss/</url>
<layout>default</layout>
<releases>
<enabled>true</enabled>
<updatePolicy>never</updatePolicy>
</releases>
<snapshots>
<enabled>true</enabled>
<updatePolicy>never</updatePolicy>
</snapshots>
</pluginRepository>
</pluginRepositories>
12 years, 1 month
