Имплементация кеша при доступе к базе данных с ограниченным числом коннектов

Question

Здраствуйте, Подскажите, пожалуйста, кто сталкивался. На недавнем собеседовании мне задали вопрос. Есть база данных к которой одновременно может быть открыто только 500 коннекшенов. Если 501-й юзер стучится в базу то получается он должен ждать чтобы какой-то коннекшн закрылся. Тоесть необходима реализация кеша, где по какой-то логике (например, принимается во внимание время последнего запроса к базе) хранятся и удаляются объекты. Вопрос: надо описать с помощью какой структуры данных можно имплементировать данный кеш? Собственно ответ мне уже озвучили и сказали что это типичный кейс и любой кто работал с базами с таким сталкивался и должен знать решение. А я джуниор и разумеется такие вопросы в моих пет-проэктах не поднимались вообще. Правильный ответ: нужны две структуры данных - мапа и линкедлист, в мапе ключ это какая-то логика хранения объектов (например, время последнего запроса) а значением выступает ссылка на объект, сами объекты хранятся в линкедлисте. Но проблема в том что я не до конца понимаю это решение, к чему примеру тут линкедлист?)) Я сразу сказал вариант с одной лишь мапой но говорят неверно, тут мол нужны две структуры данных. Тоесть я хотел бы проконсультироваться, может у кого-то была подобная ситуация в практике и понимаете что хотел услышать от меня интервьюер, какое в таком случае верное решение.

Answer 1

Основная идея заключается в том что есть map, где находится ключ - значение связи и очередь, для отслеживания последнего использования ключа. Один из вариантов реализации очереди и есть linkedlist.

Конечно, это не единственный способ сделать кеш, но довольно простой в реализации.

UPDATE:

// Сильно упрощённый пример для наглядности.

 public class Cache {

    private final capacity = 100;

    // хранилище закешированных значений
    private Map<String, Object> store = new HashMap<>(capacity);

    // очередь добавления ключей  
    private LinkedList<String> leastAddedKeys = new LinkedList<>();

    // метод загрузки из базы
    private Object loadFromDb(String key) {                

        return ...;
    }

    public Object get(String key) {

        Object o = store.get(key);
        if (o == null) {
            o = loadFromDb(key);
            store.put(key, o);
            leastAddedKeys.add(key);
            if (store.size() > capacity) {
                String keyToEvict = leastAddedKeys.removeFirst();
                store.remove(keyToEvict)
            }
        }

        return o;
    }
}

В рабочем проекте надо использовать готовые решения и никогда не писать кеш самому.

БЛОГ НА HUSL

Имплементация кеша при доступе к базе данных с ограниченным числом коннектов

Ответы (1 шт):