From 70bc196b94f2959ea9726f62019e5f0caa696eab Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Tue, 25 Nov 2014 17:43:44 +0100 Subject: [PATCH 1/1] Add support for delta JSON, to squeeze the request size down further. --- build.sh | 1 + www/index.html | 3 +- www/js/json_delta.js | 293 ++++++++++++++++++++++++++++++++++++++++++ www/js/remoteglot.js | 6 +- www/serve-analysis.js | 72 +++++++++-- 5 files changed, 361 insertions(+), 14 deletions(-) create mode 100644 www/js/json_delta.js diff --git a/build.sh b/build.sh index a03d72b..61b1376 100755 --- 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 diff --git a/www/index.html b/www/index.html index 5bf6d14..5ee3c1b 100644 --- a/www/index.html +++ b/www/index.html @@ -77,9 +77,10 @@ + - + diff --git a/www/js/json_delta.js b/www/js/json_delta.js new file mode 100644 index 0000000..dad457b --- /dev/null +++ b/www/js/json_delta.js @@ -0,0 +1,293 @@ +/* JSON-delta v0.2 - A diff/patch pair for JSON-serialized data structures. + +Copyright 2013-2014 Philip J. Roberts . +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; diff --git a/www/js/remoteglot.js b/www/js/remoteglot.js index b7a4fea..3c85e67 100644 --- a/www/js/remoteglot.js +++ b/www/js/remoteglot.js @@ -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); diff --git a/www/serve-analysis.js b/www/serve-analysis.js index c970c00..cc1d2dd 100644 --- a/www/serve-analysis.js +++ b/www/serve-analysis.js @@ -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; -- 2.39.2