Масштабируемый многопоточный объект String в Java

Question

Я провожу небольшое исследование для серверного приложения, которое планирую создать.Основная функция будет состоять в том, что многие пользователи смогут выполнять редактирование в реальном времени.

Итак, изучим все параметры масштабируемой строки, которая в основном представляет собой некий вид строкового буфера, но может обрабатывать много (сотни?) потоков, работающих над ним одновременно с довольно большим количеством текста.

Вместо того, чтобы заново изобретать колесо, я надеюсь увидеть общие библиотеки, которые имеют такие функции :) Я действительно не мог найти много сGoogle.

Answer 1

Возможно, вы захотите взглянуть на исходный код Etherpad - это веб-приложение для совместного редактирования текста на Java, поэтому оно должно иметь своего рода реализацию строк, позволяющую одновременный доступ к записи для разделенияобласти строки, предположительно, без потери данных.Конечно, отвечает ли он вашим требованиям к производительности, это другой вопрос ...

Answer 2

В этом выступлении (требуется бесплатная регистрация) описываются виды алгоритмов, которые используются в Google Docs и т. Д. Для многопользовательского редактирования, и демонстрируется простая реализация.В Scala, но применимо к любому языку.

Редактировать: упс, немного поздно!В любом случае, кому-то может быть полезно ...

Answer 3

Сама строка является поточно-ориентированной (поскольку она неизменна) и довольно высокопроизводительна для большинства случаев использования.

Основная проблема производительности со строкой заключается в том, что в O (n)в длину строки для мутаций (в связи с необходимостью взять полную копию).

Если вам нужно работать с очень длинными строками, вы, вероятно, захотите использовать Структура данных Rope .В Java доступно несколько реализаций:

• Канаты для Java - кажется очень хорошей реализацией
• Моя собственная реализация - котораяменее общий, но может быть быстрее для реализованных операций, так как он рассчитан на очень низкие издержки.

Обе реализации Rope выше соответствуют интерфейсу CharSequence (который String также реализует), поэтому если вы разрабатываете свое приложение для работы с CharSequence вместо Strings, вы можете начать со Strings и переключиться на Ropes позже, если решите, что они вам нужны.

Answer 4

Основной проблемой было отслеживание изменений, так как вы больше не полагаетесь на индекс, это усложняло ситуацию.

Так что я сейчас смотрю на хранение строк в чем-то вроде LinkHashMap или ListOrderedMap.Но все еще продолжаю исследовать правильную структуру данных ...

Редактировать: На этом этапе я пойду с ListOrderedMap, чтобы сохранить мои строки и посмотреть, как это происходит ...

Answer 5

Мне кажется, что это будет вызовом.Вы должны позволить отдельным пользователям «блокировать» части строки, над которой они работают, в то время как другие могут блокировать и работать с другими частями.Итак, в основном вы говорите о форме базы данных.

Возможно, вы могли бы сделать это с помощью SQL, но вам нужно было бы придумать протокол.

Answer 6

Ну, StringBuffer является потокобезопасным.Вы можете основать свою систему на этом.