Add support for delta JSON, to squeeze the request size down further.
authorSteinar H. Gunderson <sgunderson@bigfoot.com>
Tue, 25 Nov 2014 16:43:44 +0000 (17:43 +0100)
committerSteinar H. Gunderson <sgunderson@bigfoot.com>
Tue, 25 Nov 2014 16:43:44 +0000 (17:43 +0100)
build.sh
www/index.html
www/js/json_delta.js [new file with mode: 0644]
www/js/remoteglot.js
www/serve-analysis.js

index a03d72b..61b1376 100755 (executable)
--- a/build.sh
+++ b/build.sh
@@ -11,5 +11,6 @@ java -jar closure/compiler.jar \
        --externs externs/webstorage.js \
        www/js/chessboard-0.3.0.js \
        www/js/chess.js \
+       www/js/json_delta.js \
        www/js/remoteglot.js
 
index 5bf6d14..5ee3c1b 100644 (file)
 <!-- For faster development -->
 <script type="text/javascript" src="js/chessboard-0.3.0.min.js"></script>
 <script type="text/javascript" src="js/chess.min.js"></script>
+<script type="text/javascript" src="js/json_delta.js"></script>
 <script type="text/javascript" src="js/remoteglot.js"></script>
 
-<!-- Minified version of the previous three, compiled together -->
+<!-- Minified version of the previous four, compiled together -->
 <!--
 <script type="text/javascript" src="js/remoteglot.min.js"></script>
 -->
diff --git a/www/js/json_delta.js b/www/js/json_delta.js
new file mode 100644 (file)
index 0000000..dad457b
--- /dev/null
@@ -0,0 +1,293 @@
+/* JSON-delta v0.2 - A diff/patch pair for JSON-serialized data structures.
+
+Copyright 2013-2014 Philip J. Roberts <himself@phil-roberts.name>.
+All rights reserved
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+1. Redistributions of source code must retain the above copyright
+notice, this list of conditions and the following disclaimer.
+
+2. Redistributions in binary form must reproduce the above copyright
+notice, this list of conditions and the following disclaimer in the
+documentation and/or other materials provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+This implementation is based heavily on the original python2 version:
+see http://www.phil-roberts.name/json-delta/ for further
+documentation.  */
+JSON_delta = {
+    isStrictlyEqual: function (left, right) {
+       if (this.isTerminal(left) && this.isTerminal(right)) {
+           return (left === right);
+       }
+       if (this.isTerminal(left) || this.isTerminal(right)) {
+           return false;
+       }
+       if (left instanceof Array && right instanceof Array) {
+           if (left.length != right.length) {
+               return false;
+           }
+           for (idx in left) {
+               if ( ! this.isStrictlyEqual(left[idx], right[idx])) {
+                   return false;
+               }
+           }
+           return true;
+       }
+       if (left instanceof Array || right instanceof Array) {
+           return false;
+       }
+       var ks = this.computeKeysets(left, right);
+       if (ks[1].length != 0 || ks[2].length != 0) {
+           return false;
+       }
+       for (key in ks[0]) {
+           key = ks[0][key];
+           if ( ! this.isStrictlyEqual(left[key], right[key])) {
+               return false
+           }
+       }
+       return true;
+    },
+
+    isTerminal: function (obj) {
+       if (typeof obj == "string" || typeof obj == "number"
+           || typeof obj == "boolean" || obj == null) {
+           return true;
+       }
+       return false;
+    },
+
+    splitDeletions: function (diff) {
+       if (diff.length == 0) {return [[], diff]}
+       diff.sort(function (a,b) {return b.length-a.length});
+       for (idx in diff) {
+           if (diff[idx] > 1) {break}
+       }
+       return [diff.slice(0,idx), diff.slice(idx)]
+    },
+
+    sortStanzas: function (diff) {
+       // Sorts the stanzas in a diff: node changes can occur in any
+       // order, but deletions from sequences have to happen last node
+       // first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] -> ['foo'] ->
+       // [] and additions to sequences have to happen
+       // leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
+       // ['foo', 'bar', 'baz'].
+
+
+       // First we divide the stanzas using splitDeletions():
+       var split_thing = this.splitDeletions(diff);
+       // Then we sort modifications in ascending order of last key:
+       split_thing[0].sort(function (a,b) {return a[0].slice(-1)[0]-b[0].slice(-1)[0]});
+       // And deletions in descending order of last key:
+       split_thing[1].sort(function (a,b) {return b[0].slice(-1)[0]-a[0].slice(-1)[0]});
+       // And recombine:
+       return split_thing[0].concat(split_thing[1])
+    },
+
+    computeKeysets: function (left, right) {
+       /* Returns an array of three arrays (overlap, left_only,
+        * right_only), representing the properties common to left and
+        * right, only defined for left, and only defined for right,
+        * respectively. */
+       var overlap = [], left_only = [], right_only = [];
+       var target = overlap;
+       var targ_num = (left instanceof Array);
+
+       for (key in left) {
+           if (targ_num) {
+               key = Number(key)
+           }
+           if (key in right) {
+               target = overlap;
+           }
+           else {
+               target = left_only;
+           }
+           target.push(key);
+       }
+       for (key in right) {
+           if (targ_num) {
+               key = Number(key)
+           }
+           if (! (key in left)) {
+               right_only.push(key);
+           }
+       }
+       return [overlap, left_only, right_only]
+    },
+
+    commonality: function (left, right) {
+       var com = 0;
+       var tot = 0;
+       if (this.isTerminal(left) || this.isTerminal(right)) {
+           return 0;
+       }
+
+       if ((left instanceof Array) && (right instanceof Array)) {
+           for (idx in left) {
+               elem = left[idx];
+               if (right.indexOf(elem) != -1) {
+                   com += 1;
+               }
+           }
+           tot = Math.max(left.length, right.length);
+       }
+       else if ((left instanceof Array) || (right instanceof Array)) {
+           return 0;
+       }
+       else {
+            var ks = this.computeKeysets(left, right);
+            o = ks[0]; l = ks[1]; r = ks[2];
+           com = o.length;
+           tot = o.length + l.length + r.length;
+           for (idx in r) {
+               elem = r[idx];
+               if (l.indexOf(elem) == -1) {
+                   tot += 1
+               }
+           }
+       }
+       if (tot == 0) {return 0}
+       return com / tot;
+    },
+
+    thisLevelDiff: function (left, right, key, common) {
+       // Returns a sequence of diff stanzas between the objects left and
+       // right, assuming that they are each at the position key within
+       // the overall structure.
+       var out = [];
+       key = typeof key !== 'undefined' ? key: [];
+
+       if (typeof common == 'undefined') {
+           common = this.commonality(left, right);
+       }
+
+       if (common) {
+           var ks = this.computeKeysets(left, right);
+           for (idx in ks[0]) {
+               okey = ks[0][idx];
+               if (left[okey] != right[okey]) {
+                   out.push([key.concat([okey]), right[okey]]);
+               }
+           }
+           for (idx in ks[1]) {
+               okey = ks[1][idx];
+               out.push([key.concat([okey])]);
+           }
+           for (idx in ks[2]) {
+               okey = ks[2][idx];
+               out.push([key.concat([okey]), right[okey]]);
+           }
+           return out
+       }
+       else if ( ! this.isStrictlyEqual(left,right)) {
+           return [[key, right]]
+       }
+       else {
+           return []
+       }
+    },
+
+    keysetDiff: function (left, right, key) {
+       var out = [];
+       var ks = this.computeKeysets(left, right);
+       for (k in ks[1]) {
+           out.push([key.concat(ks[1][k])]);
+       }
+       for (k in ks[2]) {
+           out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
+       }
+       for (k in ks[0]) {
+           out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
+                                      key.concat([ks[0][k]])))
+       }
+       return out;
+    },
+
+    patchStanza: function (struc, diff) {
+       // Applies the diff stanza diff to the structure struc.  Returns
+       // the modified structure.
+       key = diff[0];
+       switch (key.length) {
+       case 0:
+           struc = diff[1];
+           break;
+       case 1:
+           if (diff.length == 1) {
+               if (typeof struc.splice == 'undefined') {
+                   delete struc[key[0]];
+               }
+               else {
+                   struc.splice(key[0], 1);
+               }
+           }
+           else {
+               struc[key[0]] = diff[1];
+           }
+           break;
+       default:
+           pass_key = key.slice(1);
+           pass_struc = struc[key[0]];
+           pass_diff = [pass_key].concat(diff.slice(1));
+           struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
+       }
+       return struc;
+    },
+
+    patch: function (struc, diff) {
+       // Applies the sequence of diff stanzas diff to the structure
+       // struc, and returns the patched structure.
+       for (stan_key in diff) {
+           struc = this.patchStanza(struc, diff[stan_key]);
+       }
+       return struc
+    },
+
+    diff: function (left, right, key, minimal) {
+       key = typeof key !== 'undefined' ? key : [];
+       minimal = typeof minimal !== 'undefined' ? minimal: true;
+       var dumbdiff = [[key, right]]
+       var my_diff = [];
+
+       common = this.commonality(left, right);
+       if (common < 0.5) {
+           my_diff = this.thisLevelDiff(left, right, key, common);
+       }
+       else {
+           my_diff = this.keysetDiff(left, right, key);
+       }
+
+       if (minimal) {
+           if (JSON.stringify(dumbdiff).length <
+               JSON.stringify(my_diff).length) {
+               my_diff = dumbdiff
+           }
+       }
+
+       if (key.length == 0) {
+           if (my_diff.length > 1) {
+               my_diff = this.sortStanzas(my_diff);
+           }
+       }
+       return my_diff;
+    }
+}
+
+// node.js
+if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;
index b7a4fea..3c85e67 100644 (file)
@@ -138,7 +138,11 @@ var request_update = function() {
                ims = xhr.getResponseHeader('X-Remoteglot-Last-Modified');
                var num_viewers = xhr.getResponseHeader('X-Remoteglot-Num-Viewers');
                possibly_play_sound(current_analysis_data, data);
-               current_analysis_data = data;
+               if (Array.isArray(data)) {
+                       current_analysis_data = JSON_delta.patch(current_analysis_data, data);
+               } else {
+                       current_analysis_data = data;
+               }
                update_board(current_analysis_data, displayed_analysis_data);
                update_num_viewers(num_viewers);
 
index c970c00..cc1d2dd 100644 (file)
@@ -8,6 +8,7 @@ var url = require('url');
 var querystring = require('querystring');
 var path = require('path');
 var zlib = require('zlib');
+var delta = require('./js/json_delta.js');
 
 // Constants.
 var json_filename = '/srv/analysis.sesse.net/www/analysis.json';
@@ -15,6 +16,11 @@ var json_filename = '/srv/analysis.sesse.net/www/analysis.json';
 // The current contents of the file to hand out, and its last modified time.
 var json = undefined;
 
+// The last five timestamps, and diffs from them to the latest version.
+var history_to_keep = 5;
+var historic_json = [];
+var diff_json = {};
+
 // The list of clients that are waiting for new data to show up.
 // Uniquely keyed by request_id so that we can take them out of
 // the queue if they close the socket.
@@ -35,21 +41,59 @@ var touch_timer = undefined;
 var viewer_count_override = undefined;
 
 var replace_json = function(new_json_contents, mtime) {
+       // Generate the list of diffs from the last five versions.
+       if (json !== undefined) {
+               // If two versions have the same mtime, clients could have either.
+               // Note the fact, so that we never insert it.
+               if (json.last_modified == mtime) {
+                       json.invalid_base = true;
+               }
+               if (!json.invalid_base) {
+                       historic_json.push(json);
+                       if (historic_json.length > history_to_keep) {
+                               historic_json.shift();
+                       }
+               }
+       }
+
        var new_json = {
                parsed: JSON.parse(new_json_contents),
                plain: new_json_contents,
                last_modified: mtime
        };
+       create_json_historic_diff(new_json, historic_json.slice(0), {}, function(new_diff_json) {
+               // gzip the new version (non-delta), and put it into place.
+               zlib.gzip(new_json_contents, function(err, buffer) {
+                       if (err) throw err;
 
-       // gzip the new version, and put it into place.
-       zlib.gzip(new_json_contents, function(err, buffer) {
-               if (err) throw err;
+                       new_json.gzip = buffer;
+                       json = new_json;
+                       diff_json = new_diff_json;
 
-               new_json.gzip = buffer;
-               json = new_json;
+                       // Finally, wake up any sleeping clients.
+                       possibly_wakeup_clients();
+               });
+       });
+}
 
-               // Finally, wake up any sleeping clients.
-               possibly_wakeup_clients();
+var create_json_historic_diff = function(new_json, history_left, new_diff_json, cb) {
+       if (history_left.length == 0) {
+               cb(new_diff_json);
+               return;
+       }
+
+       var histobj = history_left.shift();
+       var diff = delta.JSON_delta.diff(histobj.parsed, new_json.parsed);
+       var diff_text = JSON.stringify(diff);
+       zlib.gzip(diff_text, function(err, buffer) {
+               if (err) throw err;
+               new_diff_json[histobj.last_modified] = {
+                       plain: diff,
+                       text: diff_text,
+                       gzip: buffer,
+                       last_modified: new_json.last_modified,
+               };
+               create_json_historic_diff(new_json, history_left, new_diff_json, cb);
        });
 }
 
@@ -87,6 +131,7 @@ var possibly_wakeup_clients = function() {
        for (var i in sleeping_clients) {
                mark_recently_seen(sleeping_clients[i].unique);
                send_json(sleeping_clients[i].response,
+                         sleeping_clients[i].ims,
                          sleeping_clients[i].accept_gzip,
                          num_viewers);
        }
@@ -114,10 +159,12 @@ var handle_viewer_override = function(request, u, response) {
                response.end();
        }
 }
-var send_json = function(response, accept_gzip, num_viewers) {
+var send_json = function(response, ims, accept_gzip, num_viewers) {
+       var this_json = diff_json[ims] || json;
+
        var headers = {
                'Content-Type': 'text/json',
-               'X-Remoteglot-Last-Modified': json.last_modified,
+               'X-Remoteglot-Last-Modified': this_json.last_modified,
                'X-Remoteglot-Num-Viewers': num_viewers,
                'Access-Control-Expose-Headers': 'X-Remoteglot-Last-Modified, X-Remoteglot-Num-Viewers',
                'Expires': 'Mon, 01 Jan 1970 00:00:00 UTC',
@@ -127,10 +174,10 @@ var send_json = function(response, accept_gzip, num_viewers) {
        if (accept_gzip) {
                headers['Content-Encoding'] = 'gzip';
                response.writeHead(200, headers);
-               response.write(json.gzip);
+               response.write(this_json.gzip);
        } else {
                response.writeHead(200, headers);
-               response.write(json.text);
+               response.write(this_json.text);
        }
        response.end();
 }
@@ -203,7 +250,7 @@ server.on('request', function(request, response) {
        // If we already have something newer than what the user has,
        // just send it out and be done with it.
        if (json !== undefined && (!ims || json.last_modified > ims)) {
-               send_json(response, accept_gzip, count_viewers());
+               send_json(response, ims, accept_gzip, count_viewers());
                return;
        }
 
@@ -214,6 +261,7 @@ server.on('request', function(request, response) {
        client.request_id = request_id;
        client.accept_gzip = accept_gzip;
        client.unique = unique;
+       client.ims = ims;
        sleeping_clients[request_id++] = client;
 
        request.socket.client = client;