javascript - 如何将数据(可能是 JSON)的差异推送到服务器？

Question

我将定期将一组基于文本的数据从网页推送到服务器，可能是 JSON。

对于每次推送，数据可能没有改变、部分或全部发生改变。为了减少必须通过网络发送的数据量，我只想发送每次推送中更改的差异。

您是否知道任何预制解决方案/工具/库可以:

• 在发生更改时动态构建 JSON 的差异(以避免存储 oldJson 和 newJson 并在每次推送时进行完整的差异)用 JavaScript 编写(即针对客户端)
• 在服务器端使用 JSON diff 修补现有的 JSON block ，在非 Java 或 .NET^ 的任何平台上编写(需要在 Linux 上运行，Java 不是一个选项)我所在的环境，Mono 也不是)。

此外，这是否是解决这个特定问题的最佳方法？ 是否有更好的方法来推送文本数据 block ？

编辑:一些说明:

• 可能的数据结构基本上是一个相当平坦的节点集合(从某种意义上说，它是高度连接的，因此任何链接都将是基于 ID 的引用，而不是实际的嵌套数据)。节点包含树的集合，这些树的叶子包含实际的“原始”数据，例如数字、字符串和 Id。大多数数据更改将发生在叶子中。
  • 大多数叶数据都非常小(基元或小于文本段落)，但有些会非常长(“丰富”文本的页面)。
• 目前我们可以考虑严格的一对一，即只有一个客户端连接(读/写)到任何特定的数据结构。
• 就复杂性而言，将服务器保持在尽可能低的水平是很好的——这个想法是尽可能远离服务器。虽然 HTML5 仍然基本上不受支持，但我仍然需要一个来存储数据......

^ 这就是您在随机共享主机上所期望的。我说的是你的好 friend PHP、Python、PERL、Ruby，这些 fullas。 或者，可以轻松安装在随机共享主机上的东西。

Answer 1

这也是我一直在努力解决的问题。如果其他人提供比我更好的答案，我会非常感兴趣，但目前......

首先，有 http://www.xn--schler-dya.net/blog/2008/01/15/diffing_json_objects/

我个人还无法让这个库正常工作，但您的情况可能会有所不同。

另一种选择是不尝试使用 DIFF 算法来解决问题。这是非常低效的，并且根据问题的不同，即使您最终重复自己，您也可能仅发送整个数据 block 就可以获得更好的性能指标。这主要适用于非常小的数据 block 。显然，随着需要传输的数据变大，将会出现一个转折点，但如果没有某种测量，转折点在哪里并不明显。这里的技巧是，数据越大，差异计算所需的时间也就越长。转折点仅由每种方法的增长率形成的两条线的交点决定，这两条线都将是线性的或更糟，具体取决于您的 diff 的实现方式。在最坏的情况下，您可能会看到中间有一个孤岛，其中 diff 获得了更好的性能，但随后再次交叉回来以获得更大的数据集，并且只需通过网络发送它就会再次变得更好。

在尝试 diff 之前，下一站是将数据访问包装在“get”、“set”和“delete”方法中，以跟踪所做的更改。您通过线路发送的数据本质上是这些方法使用情况的顺序日志，您可以在每次成功传输时从客户端刷新该日志。在服务器端，您可以将此日志应用于服务器端数据，并使用服务器端类似的数据访问方法。这是比 diff 更轻的解决方案，不需要太多的处理能力。

最后，如果您要进行比较，我能想到的最有效的方法是您可以将数据集分解为离散的“ block ”，每个 block 都有一个唯一的 ID。然后，当您运行差异时，差异的过程正好处于“ block ”级别。也就是说，您唯一要做的比较就是 ID 与 ID 之间的比较。如果你改变了一个 block ，给它一个新的 id。您能够负担得起的 diff 算法越多，运行所需的时间就越少。

或者，您可以简单地运行 diff 来检查特定对象是否已“更改”，而不是在更改时分配新的 ID，一旦检测到更改就停止，然后简单地将该 block 标记为要重新更改完整发送，以更新服务器端具有相同 ID 的 block 。如果您有某种可以用于快速建立相等性的 block 的快速哈希算法，那么这可能会变得更加有效。

如果 block 的顺序并不重要，或者如果您可以将序列存储为 block 本身的属性，而不是根据 block 的物理序列进行建模，那么您甚至可以通过 ID 为 block 设置关键字。然后发现差异只需列出对象 A 的键，然后在对象 B 上查找它们，然后反之亦然。这比“真正的” diff 算法更容易实现，它具有 O(a+b) 性能，(我认为)比真正的 diff 算法的最坏情况更好，如果你正在尝试自己实现它，或者得到一个糟糕的实现。