如何将数据差异(可能是JSON格式)推送到服务器?

23

我将定期从网页上推送一组基于文本的数据到服务器,可能以JSON格式发送。

每次推送时,可能有部分或全部数据发生了更改。为了减少要通过网络发送的数据量,我只想发送每个推送中更改的差异。

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

  • 动态构建JSON的差异,随着对其进行更改(避免存储oldJson和newJson并在每次推送时执行完整差异)使用JavaScript编写(即客户端)
  • 在服务器端使用JSON差异修补现有JSON块,在Java或.NET之外的任何平台上编写(需要在Linux上运行,因为Java不适用于我的环境,Mono也不适合)

此外,这是解决此特定问题的最佳方法吗?有没有更好的方法来推送文本数据块?

编辑:一些澄清:

  • 可能的数据结构基本上是一个相当扁平的(在连接紧密的意义上,因此任何链接都将基于ID引用而不是实际嵌套数据)节点集合。节点包含树的集合,这些树的叶子包含实际的“基元”数据,例如数字,字符串和ID。大多数数据更改都将在叶子中发生。
    • 大多数叶数据非常小(原语或少于一段文字)但有些非常长(页面的“富”文本)
  • 目前我们可以严格考虑这是一对一的,即只有一个客户端与任何特定数据结构连接(读/写)。
  • 希望服务器尽可能地保持最小复杂性--想法是尽可能远离拥有服务器。虽然HTML5仍然大多不支持,但我仍然需要一个用于存储数据的...

^ 这就是你会在随机共享托管上预期的内容。我指的是你喜爱的 PHP、Python、PERL、Ruby 等语言。或者,一些可以轻松安装在随机共享托管上的东西。


除了Java或.NET之外,还有其他平台吗?REBOL呢? - BobbyShaftoe
@Bobby,好吧,也许只是我听说过的语言。帖子已更新... - SCdF
@Bobby,实际上,在了解了REBOL之后,我不确定你是否在开玩笑。如果您愿意以JS的差异为开端提供使用REBOL的答案,请随意。 - SCdF
等一下:你是指从客户端向服务器端发起对话吗?这似乎不是一件简单的事情。 - Jason S
11年过去了,显然对于这个微不足道的问题,我们仍然没有一个被广泛使用/可接受的解决方案。 - sigmaxf
9个回答

5

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

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

个人而言,我无法使该库正常工作,但你的情况可能不同。

另一种选择是不使用DIFF算法来解决问题。这种方法效率低下,而且根据问题的不同,即使您重复发送整个数据块,也可能获得更好的性能指标。这通常适用于非常小的数据块。显然,随着需要传输的数据变得越来越大,会出现一个转折点,但是如果没有某种测量方式,这个转折点将不会明显。关键在于,您的数据越大,diff计算所需的时间就越长。转折点仅由两种方法的增长速度形成的两条线的交点确定,两种方法的增长速度都将是线性或更差,具体取决于您如何实现diff。在最坏的情况下,您可能会看到中间有一个岛屿,diff获得更好的性能,但是对于更大的数据集,它会再次穿过,直接将其发送到网络上会再次变得更好。
在尝试diff之前的下一步是用“get”、“set”和“delete”方法包装您的数据访问,以跟踪所做的更改。您发送到网络的数据实际上将是这些方法使用的顺序日志,每次成功传输时都会从客户端清除。在服务器端,您可以使用服务器端模拟数据访问方法将此日志应用于服务器端数据。这比不需要太多处理能力的diff要轻松一些。
最后,如果你要进行diff,我能想到的最有效的方法是将数据集拆分为离散的“块”,每个块都有一个唯一的ID。然后,当您运行diff时,差异的粗糙度正好在“块”级别。也就是说,您只需进行ID与ID的比较。如果更改了一个块,请给它一个新的id。您能够承受的差异算法越粗略,运行所需的时间就越少。

或者,与其在更改时分配新的ID,您可以简单地运行差异以检查特定对象是否已“更改”,一旦检测到更改就停止,然后仅标记该块以完全重新发送,以使用相同的ID在服务器端更新该块。如果您有某种快速哈希算法可用于块,则可以使其更加高效。

如果您的块序列不重要,或者如果您可以将序列存储为块本身的属性,而不是由块的物理序列建模,则甚至可以按ID对块进行键入。然后,发现差异只是列出对象A的键,并在对象B上查找它们,然后反过来。这比实现“真正”的差异算法要简单得多,它具有O(a + b)性能,这比您自己尝试实现它或获得糟糕的实现时可能会得到的最坏情况更好的性能。


将您的数据访问封装在“get”、“set”和“delete”方法中。是的,我的另一个想法是在修改JSON时存储一堆“修改”对象,就像审计日志一样,然后发送它。 - SCdF
发送数据方面:不行,它会变得非常庞大。可能是兆字节级别的。还有一个问题就是如何将这些数据传输到客户端,这可能与从服务器获取数据块并根据需要构建整个对象的过程相反,但这是另一个问题。;-) - SCdF
我个人会选择使用更改日志记录的方法,具体取决于数据的更改情况,你可能需要合并条目。 - Simon Buchan
哇,你真的想得很周到 :P - SCdF
1
我最终编写了自己的diff/patch库 https://github.com/algesten/jsondiff - Martin Algesten
不好意思打广告:https://github.com/benjamine/JsonDiffPatch 这是我自己的JSON差异和补丁库,请查看演示页面。 - Benja

5

EtherPad通过将每个源更改转换为可交换、可结合等数学操作来解决了类似的问题。我认为这是一个非常重要的问题,而EtherPad能够围绕这个问题形成业务。

编辑:有趣的是,这正是像Git这样出色的DVCS所解决的问题,只不过不是在浏览器上。


你是在建议我将Git移植到JavaScript吗... :P - SCdF
1
是的,立即开始。;-) 但说真的,我想要一个基于浏览器的解决方案来解决这类问题。 - m104
这是论文链接: https://github.com/Pita/etherpad-lite/tree/master/doc/easysync 请查看完整描述和备注。 - prafulfillment

2

2

1
为什么要首先创建一个差异呢?通过挂接到更改数据的事件并基于更改生成更改后的数据集不是更有效吗?由于您的代码将嵌入到浏览器中,因此生成差异可能会影响应用程序性能,因为您只能使用JavaScript。

1

它不支持JSON,但似乎有一种方法是谷歌在Docs中使用的(他们的版本解决了上述Etherpad问题)。

http://code.google.com/p/google-diff-match-patch/

它可能不会意识到JSON,但它可以让你在JavaScript客户端生成高效的差异,并使用适当的实现(Java、JavaScript、C++、C#、Objective C、Lua或Python)让服务器应用它。

这个回答对另一个问题可能有用,特别是关于修改版的google-diff-match-patch的部分:Textually diffing JSON


1
这个项目很不错,但是它并没有被谷歌使用。它是由谷歌赞助的项目。 - ABCD
谢谢你提到这个。我非常感激。 - snehanshu.js

0

在某个地方,有一个研究生论文,旨在找到一种既能有效传输“新内容”,又能与Web架构(缓存和在服务器上保存最少量状态)相容的解决方案。

我很好奇现在有什么方法;我一直在思考这个问题,@Breton的答案中的“块”概念是我的方向,但不确定如何实现。

编辑:等等——我搞错了,我以为你在谈论服务器计算差异并发送给客户端。

也许您可以模糊地描述一下发送到服务器的客户端数据的结构。如果可能的话,不要基于JSON文本进行差异比较;在Javascript内部进行差异比较。如果它是具有已知结构的项目列表,请跟踪您已经发送到服务器的项目并发送其余项目。如果它是更复杂的数据集,则不确定如何帮助您。


0

看一下JSON Patch

JSON Patch是一种描述更改JSON文档的格式。 它可用于在仅部分更改时避免发送整个文档。 当与HTTP PATCH方法结合使用时,它以符合标准的方式允许HTTP API进行部分更新。

补丁文档本身就是JSON文档。

JSON Patch在IETF的RFC 6902中指定。


-2

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接