Как реализовать фиксированный размер кеша с нуля

Redis

Три вершины программиста

Некоторое время назад у коллеги был медосмотр, и врач медкомиссии сказал, что у него тройка.

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

Каждый разработчик, стремящийся к производительности, неустанно стремится к высокой производительности, и кэширование — единственный способ встать на этот путь высокой производительности.

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

Способ разработки кеша

Древнее общество — HashMap

Когда наше приложение имеет определенный объем трафика или база данных запрашивается очень часто, мы можем использовать HashMap или ConcurrentHashMap, которые поставляются с нашим java.

Мы можем написать это в коде:

public class CustomerService {
    private HashMap<String,String> hashMap = new HashMap<>();
    private CustomerMapper customerMapper;
    public String getCustomer(String name){
        String customer = hashMap.get(name);
        if ( customer == null){
            customer = customerMapper.get(name);
            hashMap.put(name,customer);
        }
        return customer;
    }
}

Однако при этом возникает проблема: HashMap не может выполнять удаление данных, а память будет неограниченно расти, поэтому в скором времени hashMap будет удален.

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

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

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

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

Современное общество - LRUHashMap

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

Некоторые люди говорят, что я удалю некоторые данные, что неправильно, но как это удалить? Случайное удаление?

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

Поэтому умные люди придумали несколько алгоритмов отсева.Вот три распространённых FIFO,LRU,LFU(есть ещё ARC,MRU желающие могут поискать сами):

FIFO

По принципу «первым пришел — первым вышел» — в этом алгоритме исключения тот, кто первым войдет в кеш, будет исключен первым. Это самое простое, но это приведет к очень низкому проценту попаданий.

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

LRU

Наименее недавно использованный алгоритм.

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

Но с этим еще есть проблема, если есть данные, к которым обращаются 10 000 раз за первые 59 минут часа (видно, что это данные хотспота), а в следующую минуту данные не обращаются , но есть и другие обращения к данным, это приведет к тому, что наши горячие данные отсеются.

LFU

Наименее часто используется в последнее время.

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

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

Вообще говоря, решение, которое мы выбираем, может быть посередине, то есть стоимость реализации не слишком высока, а показатель попаданий тоже хороший.Как реализовать LRUMap?

Мы можем завершить простой LRUMap, унаследовав LinkedHashMap и переопределив метод removeEldestEntry.

class LRUMap extends LinkedHashMap {
    private final int max;
    private Object lock;
    public LRUMap(int max, Object lock) {
        //无需扩容
        super((int) (max * 1.4f), 0.75f, true);
        this.max = max;
        this.lock = lock;
    }

    /**
     * 重写LinkedHashMap的removeEldestEntry方法即可
     * 在Put的时候判断，如果为true，就会删除最老的
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > max;
    }
    public Object getValue(Object key) {
        synchronized (lock) {
            return get(key);
        }
    }
    public void putValue(Object key, Object value) {
        synchronized (lock) {
            put(key, value);
        }
    }
   
    public boolean removeValue(Object key) {
        synchronized (lock) {
            return remove(key) != null;
        }
    }
    public boolean removeAll(){
        clear();
        return true;
    }
}

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

Можно заметить, что в методе построения размер набора преднамеренно установлен на max * 1,4,

В следующем методе removeEldestEntry требуется исключить только size>max, так что наша карта никогда не сможет достичь логики расширения,

Переопределив LinkedHashMap, мы реализовали наш LruMap несколькими простыми способами.

Современное общество - тайник гуавы

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

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

  • Срок действия не поддерживается

  • Автообновление не поддерживается

Поэтому большие ребята из Google не смогли сдержать эти проблемы и изобрели кеш Guava, В кеше Guava вы можете легко использовать его, как следующий код:

public static void main(String[] args) throws ExecutionException {
    LoadingCache<String, String> cache = CacheBuilder.newBuilder()
            .maximumSize(100)
            //写之后30ms过期
            .expireAfterWrite(30L, TimeUnit.MILLISECONDS)
            //访问之后30ms过期
            .expireAfterAccess(30L, TimeUnit.MILLISECONDS)
            //20ms之后刷新
            .refreshAfterWrite(20L, TimeUnit.MILLISECONDS)
            //开启weakKey key 当启动垃圾回收时，该缓存也被回收
            .weakKeys()
            .build(createCacheLoader());
    System.out.println(cache.get("hello"));
    cache.put("hello1", "我是hello1");
    System.out.println(cache.get("hello1"));
    cache.put("hello1", "我是hello2");
    System.out.println(cache.get("hello1"));
}

public static com.google.common.cache.CacheLoader<String, String> createCacheLoader() {
    return new com.google.common.cache.CacheLoader<String, String>() {
        @Override
        public String load(String key) throws Exception {
            return key;
        }
    };
}

Конечно, нет предела погоне за производительностью.

и:

Caffeine: Вторая половина.GitHub.IO/2018/09/09/…

LevelDB: Вторая половина.GitHub.IO/2018/09/06/…

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

В этой статье давайте рассмотрим, как реализовать кэш фиксированного размера.

Код

Определение интерфейса

Чтобы быть совместимым с Map, мы определяем интерфейс кеша, который наследуется от интерфейса Map.

/**
 * 缓存接口
 * @author binbin.hou
 * @since 0.0.1
 */
public interface ICache<K, V> extends Map<K, V> {
}

основная реализация

Мы в основном смотрим на реализацию при установке:

@Override
public V put(K key, V value) {
    //1.1 尝试驱除
    CacheEvictContext<K,V> context = new CacheEvictContext<>();
    context.key(key).size(sizeLimit).cache(this);
    cacheEvict.evict(context);
    //2. 判断驱除后的信息
    if(isSizeLimit()) {
        throw new CacheRuntimeException("当前队列已满，数据添加失败！");
    }
    //3. 执行添加
    return map.put(key, value);
}

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

В противном случае карта фиксированного размера точно не сможет вместить элементы.

стратегия устранения

Могут быть различные стратегии исключения, такие как LRU/LFU/FIFO и т. д. Здесь мы реализуем самый простой FIFO.

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

public class CacheEvictFIFO<K,V> implements ICacheEvict<K,V> {

    /**
     * queue 信息
     * @since 0.0.2
     */
    private Queue<K> queue = new LinkedList<>();

    @Override
    public void evict(ICacheEvictContext<K, V> context) {
        final ICache<K,V> cache = context.cache();
        // 超过限制，执行移除
        if(cache.size() >= context.size()) {
            K evictKey = queue.remove();
            // 移除最开始的元素
            cache.remove(evictKey);
        }

        // 将新加的元素放入队尾
        final K key = context.key();
        queue.add(key);
    }

}

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

Начальный класс

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

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

/**
 * 缓存引导类
 * @author binbin.hou
 * @since 0.0.2
 */
public final class CacheBs<K,V> {

    private CacheBs(){}

    /**
     * 创建对象实例
     * @param <K> key
     * @param <V> value
     * @return this
     * @since 0.0.2
     */
    public static <K,V> CacheBs<K,V> newInstance() {
        return new CacheBs<>();
    }

    /**
     * map 实现
     * @since 0.0.2
     */
    private Map<K,V> map = new HashMap<>();

    /**
     * 大小限制
     * @since 0.0.2
     */
    private int size = Integer.MAX_VALUE;

    /**
     * 驱除策略
     * @since 0.0.2
     */
    private ICacheEvict<K,V> evict = CacheEvicts.fifo();

    /**
     * map 实现
     * @param map map
     * @return this
     * @since 0.0.2
     */
    public CacheBs<K, V> map(Map<K, V> map) {
        ArgUtil.notNull(map, "map");

        this.map = map;
        return this;
    }

    /**
     * 设置 size 信息
     * @param size size
     * @return this
     * @since 0.0.2
     */
    public CacheBs<K, V> size(int size) {
        ArgUtil.notNegative(size, "size");

        this.size = size;
        return this;
    }

    /**
     * 设置驱除策略
     * @param evict 驱除策略
     * @return this
     * @since 0.0.2
     */
    public CacheBs<K, V> evict(ICacheEvict<K, V> evict) {
        this.evict = evict;
        return this;
    }

    /**
     * 构建缓存信息
     * @return 缓存信息
     * @since 0.0.2
     */
    public ICache<K,V> build() {
        CacheContext<K,V> context = new CacheContext<>();
        context.cacheEvict(evict);
        context.map(map);
        context.size(size);

        return new Cache<>(context);
    }

}

тестовое использование

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(2)
        .build();
cache.put("1", "1");
cache.put("2", "2");
cache.put("3", "3");
cache.put("4", "4");
Assert.assertEquals(2, cache.size());
System.out.println(cache.keySet());

По умолчанию используется стратегия «первым пришел – первым обслужен», и в это время ключи выводятся следующим образом:

[3, 4]

резюме

На данный момент реализуется упрощенная версия кеша с заданным размером.

Полный код временно закрыт для этого проекта. Вы можете подписаться на [Lao Ma Xiao Xifeng], ответить на кеш в фоновом режиме и получить исходный код.

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

В следующем разделе мы узнаем, как реализовать кеш, который может указывать срок действия.

Категории