Как реализовать инкрементное (дифференциальное) хранение строк?
Есть web-приложение. Данные, которые редактирует пользователь, в фоновом режиме (по ajax) сохраняются на сервере в БД в виде большой (на несколько килобайт) строки JSON. Сохранение происходит при любом сколько угодно малом редактировании (onkeypress).
Меня смущают 2 вещи:
1. Качка на сервер полного набора данных при сохранении, а оно происходит при каждом "чихе" пользователя. Я конечно понимаю, что в век быстрого интернета это не проблема, тормоза в работе не наблюдаются, но моё программистское "я" сильно недовольно.
2. Но главное, хочется реализовать undo для пользователя, чтобы можно было откатывать редактирование данных в web-приложении. Хранить историю изменений в виде полного набора данных для каждого нажатия клавиши, очевидно не вариант.
Поэтому я задумался об инкрементном сохранении (и передаче) данных. Т.е. есть JSON-строка str1, есть строка str2 мало отличающаяся от str2. Требуется
а). находить разность строк diff, которую можно кратко записать;
б). восстанавливать str1 по str2 и diff, и наоборот.
Нужно что-то типа XOR для строк. Однако если переводить строки в битовое представление и делать XOR, то будет плохо, т.к. вставка символа в середину строки приводит к очень большой битовой разнице.
Кто может подсказать какие-то полезные идеи, ссылки или готовые реализации?
diff/xdiff - это решение так себе. Скорее, хак.
Пока появилась такая мысль: представил бы действия в виде массива элементов наподобие такой структуры:
UserAction
ts - UNIX timestamp
key - параметр
value - его значение
Каждое такое действие - это патч над структурой, полученной предыдущими действиями. Можно отправлять на сервер и при записи сверять по времени записи в БД.
Нет, это плохо. Дело в том, что пользователь редактирует самые разные данные, имеющие сложную структуру. Он меняет как скалярные поля, так может, например, переупорядочить целые структуры. И такие действия не удастся так просто кодировать (key, value) без каких=либо изобретений и наворотов. Именно поэтому я хочу всё сложить в "мешок" JSON, и уже анализировать изменения его как строку, не вдаваясь, что там внутри в его структуре поменялось.
Чтобы этого избежать используют метод скользящего окна.
Только вот на малых объемах данных это бессмысленная трата ресурсов.
А сделать можно. Но это будет иметь смысл на когда данные имеют размер десятки мегабайт и более. В противном случае накладные расходы превышают полезный эффект.
Тем более если речь идет о БД - там процессорное время стоит в разы дороже чем лишняя пара килобайт.
