Делать нечего, пишите LRU локальный кеш

Java

При изучении параллелизма в Java примеры в книге основаны на кешах, поэтому я хочу написать общий локальный кеш

написать впереди

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

инвалидация кеша

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

Активно удалять
  • Удалить регулярно
    При установке времени истечения срока действия пары ключ-значение создайте таймер и позвольте таймеру немедленно удалить ключ, когда наступит время истечения срока действия ключа.
    преимущество: наиболее бережно относится к памяти, убедитесь, что пары ключ-значение с истекшим сроком действия удалены в максимально возможной степени, и освободите память, занимаемую парами ключ-значение с истекшим сроком действия.
    недостаток:правильноCPUНедружелюбно, если просроченных пар ключ-значение слишком много, удаление просроченных пар ключ-значение займет значительную частьCPUвремя исполнения
  • регулярно удалять
    Выполняйте операцию удаления ключа с истекшим сроком действия через равные промежутки времени и уменьшайте эффект операции удаления, ограничивая продолжительность и частоту операции удаления.CPUВлияние времени [сложность, трудно установить время выполнения и частоту]
пассивное удаление
  • ленивое удаление
    Срок действия ключей проверяется только при их извлечении. Плюсы и минусы напротив временного удаления
    преимущество:правильноCPUдружелюбно
    недостаток: не поддерживает память Используя ленивое удаление + периодическое удаление одновременно, вы можете получитьCPUи баланс памяти, поэтому аннулирование кеша локального кеша принимает два вида ленивого удаления + обычное удаление

удаление кеша

Устранение кеша означает, что когда количество кешей достигает определенного значения, определенные данные удаляются в соответствии с определенными правилами, независимо от того, истек ли срок действия данных. Общие алгоритмы удаления кеша:

  • алгоритм "первым пришел - первым вышел"FIFO】
    Первые данные, сохраненные в кеше, будут удалены первыми.
  • Наименее часто используемый алгоритмLFU】
    Удалите данные с наименьшим количеством использований.Общая реализация заключается в подсчете всех данных и расчете их один раз при каждом использовании.Устраните данные с наименьшим количеством подсчетов.
  • Наименее недавно использованный алгоритмLRU】
    Недавние данные без использования первого для устранения, обычно достигаются в списке, самое последнее посещение, вновь вставленный элемент переместился в головку списка, из списка последнего элемента Отбор локального кешаLRUАлгоритм устранения кеша

Определение структуры кэша

После выбора алгоритмов инвалидации и ликвидации кеша можно определить структуру кеша.Первоначально учитывалась безопасность потоков.K-VструктурныйConcurrentHashMapПлюс + структура двусвязного списка, но Хэ Тяньтянь в последнее время пристрастился к запоминанию английских слов, и выучил заодноLinkedHashMapможет быть реализованLRU, используется ленивоLinkedHashMap.LinkedHashMapОн может храниться в соответствии с порядком вставки [по умолчанию] или в соответствии с порядком доступа [сначала будет помещено последнее прочитанное, а в конец — наименее часто прочитанное]. порядок хранения для хранения порядка доступа только должен быть будетaccssOrderУстановить какtrueОК, по умолчаниюfalse. в то же времяLinkedHashMapПредоставляет метод для определения необходимости удаления наименее часто читаемых данных [removeEldestEntry(Map.Entry<K, CacheNode<K, V>> eldest)вернуть по умолчаниюfalseНе удалять], вам нужно удалить и переопределить этот метод.

Определение узла кэша

public class CacheNode<K, V> {
    /**
     * 保存的键
     */
    private K key;

    /**
     * 保存的值
     */
    private V value;

    /**
     * 保存时间
     */
    private long gmtCreate;

    /**
     * 过期时间，单位为毫秒，默认永久有效
     */
    private long expireTime = Long.MAX_VALUE;
}

Инициализация структуры кэша

    /**
     * 底层缓存结构
     */
    private LinkedHashMap<K, CacheNode<K, V>> localCache;

    /**
     * 负载因子
     */
    private final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 缓存过期清理策略
     */
    private ExpireStrategy<K, V> lazyExpireStrategy = new LazyExpireStrategy<>();

    private ExpireStrategy<K, V> regularExpireStrategy;

    private int maxCacheSie;

    /**
     * 构造函数
     *
     * @param expireStrategy 缓存失效策略实现类，针对的是定期失效缓存，传入null，定期失效缓存类为默认配置值
     * @param maxCacheSie    缓存最大允许存放的数量，缓存失效策略根据这个值触发
     */
    public LocalCache(int maxCacheSize, ExpireStrategy<K, V> expireStrategy) {
        //缓存最大容量为初始化的大小
        this.maxCacheSize = maxCacheSize;
        //缓存最大容量 => initialCapacity * DEFAULT_LOAD_FACTOR，避免扩容操作
        int initialCapacity = (int) Math.ceil(maxCacheSie / DEFAULT_LOAD_FACTOR) + 1;
        //accessOrder设置为true，根据访问顺序而不是插入顺序
        this.localCache = new LinkedHashMap<K, CacheNode<K, V>>(initialCapacity, DEFAULT_LOAD_FACTOR, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, CacheNode<K, V>> eldest) {
                return size() > maxCacheSie;
            }
        };
        this.regularExpireStrategy = (expireStrategy == null ? new RegularExpireStrategy<>() : expireStrategy);
        //启动定时清除过期键任务
        regularExpireStrategy.removeExpireKey(localCache, null);
    }

инструкция:

  • переписанныйremoveEldestEntryметод, когда размер кеша превышает установленныйmaxCacheSizeудаляйте только те элементы, которые редко используются
  • установить в конструктореaccessOrderзаtrue, Абсолютный доступ к последовательному хранилищу
  • Размер кеша определяется(int) Math.ceil(maxCacheSie / DEFAULT_LOAD_FACTOR) + 1рассчитано так, что даже если множествоmaxCacheSizeне будет запускать операцию расширения
  • regularExpireStrategy.removeExpireKey(localCache, null);Инициировать задачу периодического удаления

Периодически удалять реализации политики:

public class RegularExpireStrategy<K, V> implements ExpireStrategy<K, V> {
    Logger logger = LoggerFactory.getLogger(getClass());
    /**
     * 定期任务每次执行删除操作的次数
     */
    private long executeCount = 100;

    /**
     * 定期任务执行时常 【1分钟】
     */
    private long executeDuration = 1000 * 60;

    /**
     * 定期任务执行的频率
     */
    private long executeRate = 60;

    //get and set
    public long getExecuteCount() {
        return executeCount;
    }

    public void setExecuteCount(long executeCount) {
        this.executeCount = executeCount;
    }

    public long getExecuteDuration() {
        return executeDuration;
    }

    public void setExecuteDuration(long executeDuration) {
        this.executeDuration = executeDuration;
    }

    public long getExecuteRate() {
        return executeRate;
    }

    public void setExecuteRate(long executeRate) {
        this.executeRate = executeRate;
    }

    /**
     * 清空过期Key-Value
     *
     * @param localCache 本地缓存底层使用的存储结构
     * @param key 缓存的键
     * @return 过期的值
     */
    @Override
    public V removeExpireKey(LinkedHashMap<K, CacheNode<K, V>> localCache, K key) {
        logger.info("开启定期清除过期key任务");
        ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);
        //定时周期任务，executeRate分钟之后执行，默认1小时执行一次
        executor.scheduleAtFixedRate(new MyTask(localCache), 0, executeRate, TimeUnit.MINUTES);
        return null;
    }

    /**
     * 自定义任务
     */
    private class MyTask<K, V> implements Runnable {
        private LinkedHashMap<K, CacheNode<K, V>> localCache;

        public MyTask(LinkedHashMap<K, CacheNode<K, V>> localCache) {
            this.localCache = localCache;
        }

        @Override
        public void run() {
            long start = System.currentTimeMillis();
            List<K> keyList = localCache.keySet().stream().collect(Collectors.toList());
            int size = keyList.size();
            Random random = new Random();

            for (int i = 0; i < executeCount; i++) {
                K randomKey = keyList.get(random.nextInt(size));
                if (localCache.get(randomKey).getExpireTime() - System.currentTimeMillis() < 0) {
                    logger.info("key:{}已过期，进行定期删除key操作", randomKey);
                    localCache.remove(randomKey);
                }

                //超时执行退出
                if (System.currentTimeMillis() - start > executeDuration) {
                    break;
                }
            }
        }
    }
}

инструкция:

  • использоватьScheduledExecutorServiceизscheduleAtFixedRateРеализуйте запланированные периодические задачи
  • По умолчанию выполняется один раз в час, а время каждого выполнения 1 минута, и каждой случайной попытки удалить 100 элементов [если позволяет время, срок действия ключа истекает]

Реализация стратегии удаления с ленивой загрузкой: LazyExpireStrategy.java

public class LazyExpireStrategy<K, V> implements ExpireStrategy<K, V> {
    private final Logger logger = LoggerFactory.getLogger(getClass());

    /**
     * 清空过期Key-Value
     *
     * @param localCache 本地缓存底层使用的存储结构
     * @param key 缓存的键
     * @return 过期的值
     */
    @Override
    public V removeExpireKey(LinkedHashMap<K, CacheNode<K, V>> localCache, K key) {
        CacheNode<K, V> baseCacheValue = localCache.get(key);
        //值不存在
        if (baseCacheValue == null) {
            logger.info("key:{}对应的value不存在", key);
            return null;
        } else {
            //值存在并且未过期
            if (baseCacheValue.getExpireTime() - System.currentTimeMillis() > 0) {
                return baseCacheValue.getValue();
            }
        }

        logger.info("key:{}已过期，进行懒删除key操作", key);
        localCache.remove(key);
        return null;
    }
}

инструкция:

  • Определить, существует ли ключ, если нет, вернутьnullценность
  • Если ключ существует, оцените, истек ли срок его действия, верните без истечения срока действия, удалите его после истечения срока действия и вернитеnullценность

Реализация метода работы с кэшем

  • Удалить
    public synchronized V removeKey(K key) {
  CacheNode<K, V> cacheNode = localCache.remove(key);
  return cacheNode != null ? cacheNode.getValue() : null;
}
  • найти
    public synchronized V getValue(K key) {
  return lazyExpireStrategy.removeExpireKey(localCache, key);
}
    При поиске лениво будет удалять стратегию
  • депозит
    Сохраненное значение не имеет срока действия:
    public synchronized V putValue(K key, V value) {
    CacheNode<K, V> cacheNode = new CacheNode<>();
    cacheNode.setKey(key);
    cacheNode.setValue(value);
    localCache.put(key, cacheNode);
    // 返回添加的值
    return value;
}
    Сохраненное значение неверно:
    public synchronized V putValue(K key, V value, long expireTime) {
  CacheNode<K, V> cacheNode = new CacheNode<>();
  cacheNode.setKey(key);
  cacheNode.setValue(value);
  cacheNode.setGmtCreate(System.currentTimeMillis() + expireTime);
  localCache.put(key, cacheNode);
  // 返回添加的值
  return value;
}
  • Установить время истечения кэша
    public synchronized void setExpireKey(K key, long expireTime) {
  if (localCache.get(key) != null) {
    localCache.get(key).setExpireTime(System.currentTimeMillis() + expireTime);
  }
}
  • получить размер кеша
    public synchronized int getLocalCacheSize() {
        return localCache.size();
}

Все методы используются для обеспечения безопасности потоковsynchronizeКлючевое слово [Безопасность потока, He Tiantian будет толькоsynchronize, я не думал о других лучших методах блокировки, рассматривал блокировки чтения-записи, но это не сработало,]

Поза

  • Создать объект localcace
    • поза один
      LocalCache<Integer, Integer> localCache = new LocalCache<>(4, null);
      Первый параметр — это размер кеша, который позволяет хранить количество кешей. Второй параметр периодически удаляет объект, если онnull, используйте периодическое удаление объектов по умолчанию [цикл выполнения, время выполнения и время выполнения — все значения по умолчанию]
    • поза два
      RegularExpireStrategy<Integer, Integer> expireStrategy = new RegularExpireStrategy<>();
expireStrategy.setExecuteRate(1); //每隔1分钟执行一次
LocalCache<Integer, Integer> localCache = new LocalCache<>(4, expireStrategy);
      Передать настраиваемый объект периодического удаления
  • хранить в кэше
    for (int i = 0; i < 16; i++) {
  localCache.putValue(i, i);
}
  • Сохранить в кеше и установить срок действия
     localCache.putValue(i, i,1000);
  • прочитать значение из кеша
    localCache.getValue(i)
  • Установите время истечения срока действия данных в существующем кеше
    localCache.setExpireKey(i, 1000)
  • Получить размер кеша
    localCache.getLocalCacheSize()
  • удалить кеш
    localCache.removeKey(i)

Локальный кеш пишется с целью обучения, что рекомендуется в практических приложениях.GoogleизGuava Cache, если вы достаточно уверены в моем коде, вы, конечно же, можете использоватьBug

точка оптимизации

  • использоватьConcurrentHashMapплюс + двусвязный список
  • Инвалидация кеша и выбор времени для запланированных задач разнообразны. В настоящее время единицей аннулирования кеша по умолчанию являются миллисекунды, а единицей запланированных задач по умолчанию — минуты. Путем добавления в методTimeUnitБольше разнообразных вариантов времени параметра
  • Поддержка параллелизма плохая, а реализация — это синхронизация [He Tiantian слишком плох! ! ! 】

TODO

  • Загрузите частные серверы, предоставьте зависимости для использования в других проектах и ​​узнайте, как загружать частные серверы.


Наконец прикрепил:Полный код проекта,Добро пожаловатьfork,star
如有错误，欢迎指正交流【何甜甜真的太菜了！ ! ! 】

Категории