Лучший подход для использования в Java 6 для одновременного доступа к списку

Question

У меня есть объект List, к которому обращаются несколько потоков.Обычно список обновляется одним потоком, а в некоторых случаях и двумя потоками.Из этого списка могут читать от одного до пяти потоков, в зависимости от количества обрабатываемых пользовательских запросов.Список — это не очередь задач, которые необходимо выполнить, это список объектов домена, которые извлекаются и обновляются одновременно.

Теперь есть несколько способов сделать доступ к этому списку потокобезопасным:
-использовать синхронизированный блок
-используйте обычный Замок (т.е.операции чтения и записи используют один и тот же замок)
-использовать ЧтениеЗаписьБлокировка
-используйте один из новых ПараллельноBLABLBA классы коллекций

Мой вопрос:
Какой подход лучше всего использовать, учитывая, что критические разделы обычно не содержат большого количества операций (в основном просто добавление/удаление/вставка или получение элементов из списка)?
Можете ли вы порекомендовать другой подход, не указанный выше?

Некоторые ограничения
-оптимальная производительность имеет решающее значение, использование памяти не так уж велико
-это должен быть упорядоченный список (в настоящее время синхронизируется на ArrayList), хотя и не отсортированный список (т.е.сортируется не с помощью Comparable или Comparator, а в соответствии с порядком вставки)
- список будет большим и будет содержать до 100 000 объектов домена, поэтому использование чего-то вроде CopyOnWriteArrayList невозможно.
- критические разделы записи/обновления обычно выполняются очень быстро, выполняя простое добавление/удаление/вставку или замену (установку)
- операции чтения большую часть времени будут выполнять в основном вызов elementAt(index), хотя некоторые операции чтения могут выполнять двоичный поиск или indexOf(element)
-прямая итерация по списку не выполняется, хотя операция типа indexOf(..) будет проходить по списку

Answer 1

Обязательно ли использовать последовательный список?Если структура типа карты более уместна, вы можете использовать ConcurrentHashMap.Со списком, ReadWriteLock это, пожалуй, самый эффективный способ.

Отредактируйте, чтобы отразить редактирование ОП:Бинарный поиск в заказе на размещение?Сохраняете ли вы временную метку и используете ее для сравнения в двоичном поиске?Если это так, вы можете использовать временную метку в качестве ключа и ConcurrentSkipListMap как контейнер (который поддерживает порядок ключей).

Answer 2

Что делают читающие темы?Если они перебирают список, вам действительно нужно убедиться, что никто не трогает список в течение всего процесса итерации, иначе вы можете получить очень странные результаты.

Если вы сможете точно определить, какая семантика вам нужна, проблему можно будет решить, но вы вполне можете обнаружить, что вам нужно написать свой собственный тип коллекции, чтобы сделать это правильно и эффективно.Альтернативно, КопироватьонзаписьArrayList вполне может быть достаточно хорошим, хотя и потенциально дорогим.По сути, чем больше вы можете связать свои требования, тем эффективнее это может быть.

Answer 3

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

Answer 4

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

Вы говорите, что данные находятся в базе данных на сервере, а локальный список на клиентах - ради пользовательского интерфейса.Вам не нужно хранить на клиенте все 100 000 элементов одновременно или выполнять в нем такие сложные изменения.Мне кажется, что на клиенте вам нужен облегченный кеш в базе данных.

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

Да, это довольно сложное решение.Его компонентами являются:

• Протокол для загрузки диапазона данных, скажем, элементов с 478712 по 478901, а не всего этого.
• Протокол получения обновлений об измененных данных
• Класс кэша, который хранит элементы по их известному индексу на сервере.
• Поток, принадлежащий этому кэшу, который взаимодействовал с сервером.Это единственный поток, который пишет в саму коллекцию
• Поток, принадлежащий этому кешу, который обрабатывает обратные вызовы при получении данных.
• Интерфейс, который реализуют компоненты пользовательского интерфейса, позволяющий им получать данные после их загрузки.

На первый взгляд кости этого кэша могут выглядеть примерно так:

class ServerCacheViewThingy {
    private static final int ACCEPTABLE_SIZE = 500;
    private int viewStart, viewLength;
    final Map<Integer, Record> items
            = new HashMap<Integer, Record>(1000);
    final ConcurrentLinkedQueue<Callback> callbackQueue
            = new ConcurrentLinkedQueue<Callback>();

    public void getRecords (int start, int length, ViewReciever reciever) {
        // remember the current view, to prevent records within
        // this view from being accidentally pruned.
        viewStart = start;
        viewLenght = length;

        // if the selected area is not already loaded, send a request
        // to load that area
        if (!rangeLoaded(start, length))
            addLoadRequest(start, length);

        // add the reciever to the queue, so it will be processed
        // when the data has arrived
        if (reciever != null)
            callbackQueue.add(new Callback(start, length, reciever));
    }

    class Callback {
        int start;
        int length;
        ViewReciever reciever;
        ...
    }

    class EditorThread extends Thread {

        private void prune () {
            if (items.size() <= ACCEPTABLE_SIZE)
                return;
            for (Map.Entry<Integer, Record> entry : items.entrySet()) {
                int position = entry.key();
                // if the position is outside the current view,
                // remove that item from the cache
                ...
            }
        }

        private void markDirty (int from) { ... }

        ....
    }

    class CallbackThread extends Thread {
        public void notifyCallback (Callback callback);
        private void processCallback (Callback) {
            readRecords
        }
    }
}

interface ViewReciever {
    void recieveData (int viewStart, Record[] records);
    void recieveTimeout ();
}

Очевидно, вам придется заполнить много деталей самостоятельно.

Answer 5

Вы можете использовать обертку, реализующую синхронизацию:

import java.util.Collections;
import java.util.ArrayList;

ArrayList list = new ArrayList();
List syncList = Collections.synchronizedList(list);

// make sure you only use syncList for your future calls... 

Это простое решение.Я бы попробовал это, прежде чем прибегать к более сложным решениям.