¿Cómo presionar diffs de datos (posiblemente JSON) a un servidor?

Question

Voy a presionar periódicamente un conjunto de datos basados ​​en texto de una página web a un servidor, probablemente como JSON.

Por cada inserción, ninguno, algunos o todos los datos pueden haber cambiado. Para reducir la cantidad de datos que tengo que enviar por el cable, me gustaría enviar solo una diferencia de los cambios en cada inserción.

¿Conoce alguna soluciones/herramientas/librerías pre-hechos que:

• construir dinámicamente un diff de JSON como los cambios se hacen a él (para evitar el almacenamiento de oldJson y newJson y haciendo una completa diff every push) escrito en JavaScript (es decir, para el lado del cliente)
• Parche un fragmento existente de JSON con un diff de JSON en el lado del servidor, escrito en cualquier plataforma que no sea Java o .NET^(necesita para ejecutar en Linux, Java no es una opción para el entorno en el que estoy, tampoco lo es Mono).

Además, ¿es esta la mejor manera de resolver este problema en particular? ¿Hay alguna forma mejor de enviar fragmentos de datos de texto?

Editar: Algunas aclaraciones:

• El stucture datos probable sería básicamente una bastante plana (en el sentido de que está conectado hightly por lo que cualquier enlaces serán referencias a base de identificación no los datos anidados reales) colección de nodos. Los nodos contienen una colección de árboles, las hojas de estos árboles contienen datos reales "primitivos", como números, cadenas e Id. La mayoría de los cambios de datos estarán en las hojas.
  • La mayoría de los datos de hoja serán muy pequeños (primativos o menos que un párrafo de texto) pero algunos serán muy largos (páginas de texto "enriquecido").
• Por el momento podemos considerar esto estrictamente uno-a-uno, es decir, solo hay un cliente conectado (en lectura/escritura) a cualquier estructura de datos en particular.
• Sería bueno mantener el servidor lo más bajo posible en términos de complejidad, la idea es alejarse de tener un servidor tanto como sea posible. Mientras que HTML5 está todavía en su mayoría no soportado todavía necesito uno para almacenar datos con aunque ...

^ Eso que se puede esperar en alojamiento compartido al azar. Estoy hablando de tus buenos amigos PHP, Python, PERL, Ruby, esos fullas. O, algo que podría instalarse fácilmente en el alojamiento compartido aleatorio.

Answer 1

Esto también ha sido algo con lo que he estado luchando. Voy a estar muy interesado si alguien ofrece una respuesta mejor que la mía, pero por el momento ...

En primer lugar, hay http://www.xn--schler-dya.net/blog/2008/01/15/diffing_json_objects/

Yo personalmente no he sido capaz de obtener esta biblioteca para trabajar , pero tu kilometraje puede variar.

La otra alternativa es no intentar resolver el problema utilizando el algoritmo DIFF.Es bastante ineficaz y, dependiendo del problema, puede obtener mejores métricas de rendimiento simplemente enviando toda la masa de datos, incluso si termina repitiendo usted mismo. Esto es cierto principalmente en fragmentos muy pequeños de datos. Obviamente, habrá un punto de inflexión a medida que aumenten los datos que necesita transmitir, pero no va a ser obvio dónde está el punto de inflexión, sin algún tipo de medición. El truco aquí es que cuanto más grandes sean tus datos, más tiempo tomará tu cálculo de diferencia. El punto de inflexión solo está determinado por la intersección de las dos líneas formadas por la tasa de crecimiento de cada método, las cuales serán lineales o peores, dependiendo de cómo se implemente su diferencia. En el peor de los casos, es posible que vea una isla en el medio donde diff obtiene un mejor rendimiento, pero luego vuelve a cruzar para obtener conjuntos de datos aún mayores, y simplemente enviarlo por la red es mejor otra vez.

La siguiente parada antes de probar diff, es envolviendo su acceso a los datos en los métodos "get", "set" y "delete" que rastrean los cambios que se están realizando. Los datos que envía a través del cable serían esencialmente un registro secuencial del uso de este método, que descarga desde el lado del cliente en cada transmisión exitosa. En el lado del servidor, aplica este registro a los datos de su servidor con análogos de servidor a sus métodos de acceso a datos. Esta es una solución algo más ligera que una diferencia que no requiere tanto poder de procesamiento.

Finalmente, si vas a hacer diff, la forma más eficiente que puedo pensar es si puedes dividir tu conjunto de datos en "trozos" discretos, cada uno con una ID única. Luego, cuando ejecuta el diff, el curso de la diferencia está exactamente en el nivel de "fragmento". es decir, las únicas comparaciones que harías es ID a ID. Si cambias un trozo, dale una nueva identificación. El corredor que puede permitirse hacer el algoritmo diff, menos tiempo le tomará correr.

Como alternativa, en lugar de asignar una nueva ID al cambio, simplemente puede ejecutar el diff para verificar si un objeto específico ha "cambiado", detenerse brevemente tan pronto como detecta un cambio, y simplemente marcar ese fragmento para volver a - en su totalidad, para actualizar el fragmento en el lado del servidor con la misma ID. Esto podría ser incluso más eficiente si tiene algún tipo de algoritmo de hashing rápido para sus fragmentos que puede utilizar para establecer rápidamente la igualdad.

Si la secuencia de tus fragmentos no importa, o si puedes almacenar la secuencia como una propiedad de los fragmentos, en lugar de modelarla por la secuencia física de los fragmentos, puedes incluso clavear tus fragmentos por ID . Entonces, descubrir las diferencias es simplemente una cuestión de enumerar las claves del objeto A y buscarlas en el objeto B y luego en Vice Versa. Esto es mucho más fácil de implementar que un algoritmo de diferencia "real", tiene un rendimiento O (a + b) que (creo) es mejor que el peor de los escenarios para un algoritmo de diferencia real, que es probable que obtenga si Está tratando de implementarlo usted mismo, o tiene una mala implementación.

Answer 2

¿Por qué crear un diff en primer lugar, no sería más eficiente conectarse a los eventos que cambian sus datos y generar un conjunto de datos modificado en función de los cambios? Como su código se integrará en un navegador, estará limitado a JavaScript, por lo que generar un diff podría matar el rendimiento de su aplicación.

Answer 3

en algún lado hay una tesis de licenciatura aquí, para encontrar una solución que sea una transmisión eficiente de "novedades" y que funcione bien con arquitecturas web (almacenamiento en caché y ahorro de una cantidad mínima de estado en el servidor).

Tengo curiosidad por lo que hay; He estado lidiando con esta misma pregunta, la idea de "fragmento" en la respuesta de @Breton es un poco hacia dónde voy, pero no estoy seguro de cómo.

corregir: esperar - Lo hice al revés, pensé que hablabas sobre el servidor calculando diffs para enviar al cliente.

Quizás podría describir con vagos detalles la estructura de los datos en el cliente que se envía al servidor.No lo haría basado en el texto JSON si fuera posible; hacer las diferencias desde dentro de Javascript. Si se trata de una lista de elementos con estructura conocida, realice un seguimiento de los que ha enviado al servidor y envíe el resto. Si se trata de un conjunto de datos más complicado, no estoy seguro de cómo ayudarlo allí.

Answer 4

EtherPad resolvió algo como esto convirtiendo cada cambio de fuente en una operación matemática que podría ser conmutativa, asociativa, etc. Sin embargo, consideraría esto un problema no trivial, y EtherPad pudo formar un negocio en torno a la solución a este problema

editar: curiosamente, este es exactamente el problema que aborda un buen DVCS como Git, pero no en el navegador.

Answer 5

Publico hoy un pequeño plugin jQuery haciendo una diferencia entre dos objetos JS. http://plugins.jquery.com/project/jquery-diff

Lo utilizo en una aplicación para enviar al servidor solamente los datos modificados.

Answer 6

No es consciente de JSON, pero existe el método que Google parece utilizar para los documentos (su versión del problema antes mencionado de Etherpad).

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

No sería JSON conscientes, pero sería permitirá generar un lado del cliente diff eficiente en JavaScript, y tener el servidor de aplicarlo usando una implementación apropiada (Java, JavaScript, C++, C#, Objetivo C, Lua o Python).

Esta respuesta a otra pregunta podría ser útil, especialmente la parte sobre una versión modificada de Google-diff-match-parche: Textually diffing JSON

Answer 7

"Ahora he creado un método para el retorno de las diferencias estructurales entre dos objetos JSON. "

http://www.xn--schler-dya.net/blog/2008/01/15/diffing_json_objects/