Mobile & Synchronisation - part 2 / 3

Last blog post I talked about the different approaches to mobile synchronisation. In this article, I will focus on synchronisation without prior context. With two data sets, let's say my local data set (data on my offline mobile) and a remote data set (data from the remote server, changed by other users of my mobile app), that are out of sync after an offline period. I want to be able to get a difference from those two. In this approach, we don't have any prior context. Information like when was the last synchronisation, what happened during offline (logs etc...) is not available.

Bloom Filter

A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. You basically compare 2 hashed codes, because of the nature of hash function you can tell an element is either definitely not in the set or may be in the set.

Invertible Bloom Filter (IBF): Let Magic Happen

For the purpose of synchronisation, we want to know which elements were added and which ones were removed. Replacing a set of hashed values by a more complete data structure we can achieve a clever filter. Instead of storing hashed values, we can use Bucket structure adding information like number of items, key of the item, and hashed value of the item. Using the magic XOR operator with its reversibility nature. We can xor a sum of element together.

xor 2 elements together, xor again and you get our initial element!

Hashing into buckets

In a bucket, the number of items is increased by one, each time we add an item in the bucket. The key is xored with the other keys. A hash function is used to hash the key into an hashed value, itself xored to the hashed sum.

With this same technique, you can spread hashed items into different buckets increasing odds to compare them. The bucket distribution should be uniform and reproducible on both sides (local client and remote server in our exemple).

Using recursive approach, incrementing bucket numbers each time, we build buckets set locally and remotely. With 2 sets, we compute the difference subtracting number of items. In the difference, if the count of elements is 1, we know one element was added (similarly if the count is -1, one element was removed). From the key element, we can hash it, xor it to the hash sum bucket field and get the hashed sum without it (because of the xor reversibility).

Compute difference

The whole purpose of the algorithm is to get a difference with number of item -/+1. You can iterate until you get to that point increasing by 2^level.

How to treat difference

Let's say, I have an item "green circle" that was hashed and spread into 3 different buckets (3 being the default number of hashed functions used for distributing items into buckets). With this difference set, I'm looking for item number equal to 1. I know the green circle was added, so I can removed it from the buckets index 1, 4 and 6 and add it to the set of added items. In index 2, the number of items is 2, so we carry on to index 3. I can remove blue circles from index 3, 4 and 5. etc... At the end of iteration, if I get an empty difference set, I've retrieved of differences. If the set is not empty, I don't have enough information so I need to increase numbers of buckets.

Implementation

Using "What’s the Difference? Efficient Set Reconciliation without Prior Context" paper, 3musket33rs libraires implements the IBF algorithm in Java, JavaScript and iOS.

The different players: Resolver is responsible of computing difference, increasing number of bucket (level) as needed. Set of buckets are called Summary. Summary comparaison produces Difference which hold removed and added set. BucketSelector produces a set of hash functions to uniformly distribute items with buckets. Bucket is the data structure to hold number of items, xored key and xored hashed value.

Want to see it in action? See my next blog post for an example involving JavaScript backend and iOS client.

Tweet

Mobile & Synchronisation - part 1 / 3

Last meet-up @JSSophia, we talked about synchronisation. It's an awesome subject that I like to chat, in more details, about it. My blog posts are related to some work done with my 3musket33rs friends, but also discussions ongoing in the AeroGear project mailing list.

When developing your cloud connected mobile app, you can't take for granted that user will be connected all the time. Supporting offline mode is crucial. Obviously, you need to consider what happen when back online. Let's talk about synchronisation.

Back online: Mobile Sync

User stores data locally on device for offline support. User pushes its data when back online. Potentially, there are conflicts to be resolved. Conflict resolution is really business focus. Depending on your app, you may choose deal with conflict very basically: reject them, deal with then automatically(providing patch), propose fine grained merge popup etc...

Once user's own conflicts are resolved, data reconciliation (synchronisation with other people data) can happen. But depending on your use case (how big is your changes, how much data), you have several options...

Different options for Synchronisation

Whole sale transfer: the simplest one. Client ask for reconciliation. The whole data structure is sent over the network. "Just send everything", this is great to build a prototype before moving on more complex algorithm or if there is only a short list of items/data.

Time based approach: log based. Client side and Server side, you need to track all changes. An audit log module is needed to record logs. An increasing timestamp or numeric log (be cautious with clock difference always use the same referencial to create check point) is added to each data items when changed. Client asks for reconciliation since its last reconciliation (last checkpoint).

Math Algorithm: without prior context. No prior assumption, you don't log changes. You send grouped/hashed table of your items and you compute the difference between client and server set. One algorithm can be Efficient set Reconciliation without prior context.

To be continued... Next part, I will blog in more details about the mathsync algo and its 3musket33rs implementation.



Tweet

JSSophia making the show!

Last Thursday, JSSophia, we had fun. Lots of new faces, packed room (audience record, yes man) and last but not least I wasn't the only female dev in the room (Hoorray!!).

Our evening started with a short introduction on the e-learning products by CrossKnowledge (special thanks for hosting our event). Cool demos and even some glance at source code because at JSSophia, it's geeks talking to geeks ;) Interesting to know that CrossKnowledge is recruiting at fast pace of one person a month. Hey networking is also one of the mission of user groups.

And during this introduction lots of idea for new future presentation like HTML5 and accessibility, unit test running on phantom, TypeScript... I've posted those brainstormed ideas in our JSSophia presentation proposal, feel free to add more description to them and even new ideas.

Mathieu made the show presenting "World in conflict!" with a roman costume. Small break, and Maxime gives us in less than 1024 words an entertaining presentation of JS golfing. Last but not least, Yacine (who came from London just for JSSophia ;0 ) carried on the show with a very interactive presentation of Back end as a service. Evening finished around a beer at Green King. Perfect day!

Next not-to-be-missed JSSophia event will be hosted by Amadeus the thursday 27th March. Patrick Brosset, from Mozilla, will tell all about browsers dev tools. See you there!

Tweet

Back from MarsJUG hackengarten#2

Last Saturday in Marseille, I participated in MarsJUG hackengarten#2. A bunch of known faces from my previous visit of the first edition of MArsJUG hackengarten (Hey, it looks like I'm part of the usual participants). Thanks to Julien and Benjamin for organizing the event and making such a nice place to be.

The day started with a short introduction of the proposed open source projects. Very different subjects: CRaSH, DataFari, CodevTT, RHQ, Audela and AeroGear. Having presented AeroGear last Wednesday with my fellow Sebastien Blanc (you can find slides here), I gave a very short introduction and presented the list of possible contributions from hackengarten wiki page.

Quick lunch (with Quick food) and back to work. Several teams formed: Nico and Thomas want to use AeroGear Push for RHQ Alert mobile app, trying out Cordova Push plugin. And making a double contribution to AeroGear and RHQ projects. Sylvain is brave enough to upgrade to XCode 5 and delve in iOS code with OAuth2 and Facebook. There's even a JIRA code for this one. Xavier tried simple push quickstart and even submitted his first PR. Time is always too short, but we can carry on those ideas. Mailing list is our friend.

I'm always impressed with all the ideas that come up during a hack-together day, but the best is the enthusiasm that you can feel. The reward of course is the Pull Request being accepted. Keep in touch and let's work for the holy graal: the Pull Request.



Tweet

Secure your runtime #Groovy #Hackengarten

Hackengarten is over, we had such a great time!

Thank you all for coming and making this event so special (after a long week of work). Special thanks to Nicolas Berge (@LesSatellites) for giving us a roof (useful by this rainy day). And for @CedricChampeau (who left Bretagne to see the sun) and @fabricematrat for organising and driving the event.

Wanna see in how it went? Here the twitter story:
Early start with french croissants. Sebi didn't forget them:

9hours to go before Groovy hackengarten. Getting closer! See you all @LesSatellites @sebi2706 don't forget croissants. @fabricematrat coffee

— corinne (@corinnekrych) 17 Janvier 2014

Meeting time, Cedric talk about AST, giving tricks how to work with the beast. How to read the GroovyConsole and some very useful debug tips.

@cedricchampeau talking about AST transform. #groovy hackengarten @rivieragug @lessatellites pic.twitter.com/T9DVGoEhc9

— corinne (@corinnekrych) 18 Janvier 2014

(Cedric talking with hands like a real South of France guy). Fabrice took over delving in SecureRuntimeASTCustomizer. Code is showing up!

#Groovy hackengarten ça commence ! pic.twitter.com/pLE1GhtQbw

— corinne (@corinnekrych) 18 Janvier 2014

We warm up with some coding using GroovyConsole and making test passed. One by one, step by step.
Geek lunch with ...

Pizza and beers, of course! (Greasy hands couldn't tweet that one)
Back to work in the afternoon, people working in pair, talking, coding, designing, talking again, merging... Hard work, man.

Ca bosse dur au @rivieragug #groovy hackengarten ! pic.twitter.com/HoPWJzvqAI

— corinne (@corinnekrych) 18 Janvier 2014

And to finish, what did we produce:

Just came back from a very producitve #groovylang hackengarten ! Check out all our commits https://t.co/Dd0Judd6Ne

— Sébastien Blanc (@sebi2706) 18 Janvier 2014

What our French Riviera community said about it:

The @RivieraGUG Groovy hackengaten day was a success! Thanks to @CedricChampeau @corinnekrych @fabricematrat @sebi2706

— Bertrand Goetzmann (@bgoetzmann) 18 Janvier 2014

What's next?
Still some failing tests to go over before sending the Pull Request. The core design is here, you're welcome to hack more tests making them passed. Same approach as we did. Pick an item in wiki page, fix it commit on secureruntime branch. Once all use cases are treated will come the time to refactor (lots of ideas showed up).
Other related blog:
Fabrice talks about it too

Tweet

RivieraGUG - Groovy hackengarten

Remember the RivieraGUG coding WE back in the old days?
That was fun. A whole WE of live coding and snoring;)
Just browse our etherpad log to get the idea.

We decided to get back together for some hacking. The event will be hosted at Les Satellites, Saturday 18th January (note that les Satellites has moved - still in Nice). And this time we have Cedric Champeau (core committer on Groovy) with us!

What are we going to do?
Nothing less than contributing to Groovy language! We'd like to work on SecureASTCustomizer to secure your Groovy scripts not only at compile time but at runtime too. Be prepared to code some AST transform... Get all the details in our announcement page.

Brainstorming is ongoing, check out the forked repo groovy-core with secureruntime branch. This is a proposal, nothing written in marble. Feel free to add new ideas on Groovy-Secure hackengarten wiki page, try the code snippets, comment on it or simply add your contribution. The more we have, the more we can discuss and make progress during our hackengarten. Come and join us, this is an wonderful opportunity to contribute to an open source project.

OSS needs you!!
And remember we have a goal: make a pull request by the end of Saturday!



Tweet

OAuth2 discussion - part2

We talked about OAuth2 protocol in part 1, let's see it in action in this second part. We'll take a demo app from aerogear-ios-cookbook and I'm going to drive you through it step by step.

GroogleDrive app displays the list of documents in your Google Drive using OAuth2 to authorize with aerogear-ios library.

Let's do Google setup

Before we start you will need to register your app, follow the steps below:
1. Have a Google account
2. Go to Google cloud console, create a new project
3. Go to APIs & auth menu, then select APIs and turn on Drive API
4. Always in APIs & auth menu, select Credentials and hit create new client id button Select iOS client and enter your bundle id. Enter a correct bundle id as it will be use in URL schema (if you don't know about URL Schemas I suggest you read about it) to specify the callback URL.

Once completed you will have your information displayed as below:



You'll get a Client Id, a Client Secret and a callback URL, open Xcode (or AppCode whathever you like best), go to GoogleDrive-Info.plist and add an new URL schema entry as shown below:

Show me the code

In AGViewController.m:

- (IBAction)authorize:(UIButton *)sender {
    AGAuthorizer* authorizer = [AGAuthorizer authorizer];

    _restAuthzModule = [authorizer authz:^(id config) {              [1]
        config.name = @"restAuthMod";
        config.baseURL = [[NSURL alloc] initWithString:@"https://accounts.google.com"];
        config.authzEndpoint = @"/o/oauth2/auth";
        config.accessTokenEndpoint = @"/o/oauth2/token";
        config.clientId = @"XXXXX";
        config.redirectURL = @"org.aerogear.GoogleDrive:/oauth2Callback";
        config.scopes = @[@"https://www.googleapis.com/auth/drive"];
    }];

    [_restAuthzModule requestAccessSuccess:^(id object) {                           [2]
        [self fetchGoogleDriveDocuments:_restAuthzModule];                          [4]
    } failure:^(NSError *error) {
    }];
}

[1]: configuration with all required URLs and endpoints.
[2]: requestAccessSuccess:failure: is the method dealing with all the steps needed to authorize. Within this method, we're going to bring the UI grant web page, once authorization is granted, we go back to the mobile app and then we exchange code for access token. this is the heart of OAuth2 dance ;)

In AGAppDelegate.m:

- (BOOL)application:(UIApplication *)application
            openURL:(NSURL *)url
  sourceApplication:(NSString *)sourceApplication
         annotation:(id)annotation
{                                                                                   [3]
    NSNotification *notification = [NSNotification notificationWithName:@"AGAppLaunchedWithURLNotification" 
    object:nil userInfo:[NSDictionary dictionaryWithObject:url forKey:@"UIApplicationLaunchOptionsURLKey"]];
    [[NSNotificationCenter defaultCenter] postNotification:notification];

    return YES;
}

[3]: once popup has been answered, go back to GoogleDrive app and notified AeroGear framework. If this method is not well implemented, the browser won't be able to callback the application. Back to the app, access code is excahnge with access token (step 2).
[4]: the success callback takes the access token as parameter. The access token is stored in memory with AGAuthzModule. It's up to the developer to store permanently the access token for next app launch. Note that access token has an expiration date (1h for Google).

In AGViewController.m:

-(void)fetchGoogleDriveDocuments:(id) authzModule {
    NSString* readGoogleDriveURL = @"https://www.googleapis.com/drive/v2";
    NSURL* serverURL = [NSURL URLWithString:readGoogleDriveURL];
    AGPipeline* googleDocuments = [AGPipeline pipelineWithBaseURL:serverURL];

    id documents = [googleDocuments pipe:^(id config) {       [5]
        [config setName:@"files"];
        [config setAuthzModule:authzModule];                                        [6]
    }];

    [documents read:^(id responseObject) {                                          [7]
        _documents = [[self buildDocumentList:responseObject[0]] copy];
        [self.tableView reloadData];
    } failure:^(NSError *error) {
        // when an error occurs... at least log it to the console..
        NSLog(@"Read: An error occured! \n%@", error);
    }];
}

[5]: create your Pipeline and Pipe objects as usual.
[6]: setting authz module in your pipe configuration will pass the access token for each pipe operations transparently.
[7]: read the pipe as usual.

As a conclusion

No need to learn and use different providers SDK, Aerogear-iOS library allows you to use OAuth2 with any providers. Once you're authorized, you can use the pipes transparently (no need for you to pass the access token, the framework does it for you).
OAuth2 will be shipped in 1.4.0. Give it a trial, give us your feedback and enjoy!

Tweet