Создание «изолированных» и «автоматически обновляемых» кэшей (java.util.List) в Java - PullRequest
Новая
       21

Создание «изолированных» и «автоматически обновляемых» кэшей (java.util.List) в Java

1 голос
/ 10 апреля 2010

ДЛЯ ЛЮБОГО ЗАИНТЕРЕСОВАННОГО: Я реализовал код для поведения, которое я ищу, и открыл его на Google-коде. Получи это здесь! POJO-MVCC

-

Привет, ребята,

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

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

Я сделаю все возможное, чтобы попытаться объяснить:

мастер-кеш содержит: [A, B, C, D, E, F] временный кэш, созданный с состоянием [A, B, C, D, E, F]

1) временный кеш добавляет элемент G: [A, B, C, D, E, F] 2) временный кеш удаляет элемент B: [A, C, D, E, F]

мастер-кеш содержит: [A, B, C, D, E, F]

3) мастер-кеш добавляет элементы [X, Y, Z]: [A, B, C, D, E, F, X, Y, Z]

Временный кэш содержит: [A, C, D, E, F]

Ситуация становится еще сложнее, когда значения в элементах могут изменяться и не всегда должны обновляться (поэтому я даже не могу поделиться экземплярами базового объекта, мне нужно использовать клоны).

Я реализовал простой подход - просто создать новый экземпляр List с помощью стандартного конструктора Collection в ArrayList, однако, когда вы получаете около 200 000 элементов, системе просто не хватает памяти. Я знаю, что значение 200 000 слишком много для итерации, но я пытаюсь немного подчеркнуть свой код.

Я думал, что он мог бы каким-то образом "прокси" список, так что временный кеш использует главный кеш и хранит все его изменения (фактически Memento для изменения), однако это быстро становится кошмар, когда вы хотите выполнить итерацию временного кэша или получить элемент по определенному индексу. Кроме того, учитывая, что я хочу внести некоторые изменения в содержимое списка (в зависимости от типа временного кэша, независимо от того, является ли он «автообновлением» или нет), я полностью выхожу из своей глубины.

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

Приветствия

Айдос

1 Ответ

2 голосов
/ 10 апреля 2010

Вот что вы хотите сделать. Нечто похожее на то, что называется MVCC, Multi Version Currency Control.

Проще говоря, вам нужно связать идентификатор транзакции с элементами вашего кэша.

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

public class CacheEntry {
    long transactionId;
    boolean deleted;
    Object value;
}

Ваши записи в кэше хранятся в списке в обратном порядке транзакций.

Когда вы идете, чтобы получить элемент кэша, вы просматриваете список (в вашей хэш-карте). Затем выполняется поиск значения с наивысшим идентификатором транзакции, которое меньше или равно идентификатору транзакции ВАШЕЙ транзакции.

Итак, давайте рассмотрим проблему УДАЛИТЬ.

У вас есть транзакция 10, вы ищете "ABC". Предположим, что ABC уже находится в кэше, и он был добавлен в транзакции 5.

Итак, T10 получает список записей для ABC, выполняет поиск по списку и обнаруживает, что в T5 есть значение «123». T5 - самая высокая транзакция, меньшая или равная T10. T10 изменяет значение для ABC с 123 на 456.

Теперь T12 приходит и ищет ABC. Он найдет значение 456 от T10. T12 решает удалить ABC, и поэтому «удаленная» запись кэша для T12 помещается в список записей кэша. Если T10 попытается снова найти ABC, он найдет 456, потому что 12> 10, а самая высокая транзакция <= 10 - T10, поэтому он не видит удаления. </p>

Появляется T14, ищет ABC, НЕ МОЖЕТ найти его (потому что он «удален») и вставляет новое значение 789. Если посмотреть T12, он все равно будет удален, а если T10, он все равно 456 .

Итак, в итоге ваш кеш-список выглядит так: 

{tid: 14 deleted: false value: 789}
{tid: 12 deleted: true  value: nul}
{tid: 10 deleted: false value: 456}
{tid:  5 deleted: false value: 123}

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

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

Например, если у вас есть данные от T5 и T10, если они оба зафиксированы, никто никогда не сможет снова «увидеть» данные T5, поскольку T10 теперь является «текущим» состоянием. Таким образом, строка T5 может быть удалена.

Это, вероятно, лучше всего сделать, просто перебирая кеш и удаляя устаревшие записи транзакций.

В этом суть, очевидно, дьявол кроется в деталях.

...