Java学习指南
  • Java 编程的逻辑
  • Java进阶
  • Java FrameWorks
  • 了解 USB Type-A,B,C 三大标准接口
  • 深入浅出DDD
  • 重构:改善既有代码的设计
  • 面试大纲
  • 云原生
    • 什么是无服务器(what is serverless)?
  • 博客
    • 深入分析Log4j 漏洞
  • 博客
    • Serverless之快速搭建Spring Boot应用
  • 博客
    • 使用 Prometheus + Grafana + Spring Boot Actuator 监控应用
  • 博客
    • 使用 Prometheus + Grafana 监控 MySQL
  • 博客
    • 使用Github Actions + Docker 部署Spring Boot应用
  • 博客
    • Redis分布式锁之Redisson的原理和实践
  • 博客
    • 数据库中的树结构应该怎样去设计
  • 学习&成长
    • 如何成为技术大牛
  • 开发工具
    • Git Commit Message Guidelines
  • 开发工具
    • git命名大全
  • 开发工具
    • Gradle vs Maven Comparison
  • 开发工具
    • Swagger2常用注解及其说明
  • 开发工具
    • 简明 VIM 练级攻略
  • 微服务
    • 十大微服务设计模式和原则
  • 微服务
    • 微服务下的身份认证和令牌管理
  • 微服务
    • 微服务坏味道之循环依赖
  • 设计模式
    • 设计模式 - JDK中的设计模式
  • 设计模式
    • 设计模式 - Java三种代理模式
  • 设计模式
    • 设计模式 - 六大设计原则
  • 设计模式
    • 设计模式 - 单例模式
  • 设计模式
    • 设计模式 - 命名模式
  • 设计模式
    • 设计模式 - 备忘录模式
  • 设计模式
    • 设计模式 - 概览
  • 设计模式
    • 设计模式 - 没用的设计模式
  • 质量&效率
    • Homebrew 替换国内镜像源
  • 质量&效率
    • 工作中如何做好技术积累
  • Java FrameWorks
    • Logback
      • 自定义 logback 日志过滤器
  • Java FrameWorks
    • Mybatis
      • MyBatis(十三) - 整合Spring
  • Java FrameWorks
    • Mybatis
      • MyBatis(十二) - 一些API
  • Java FrameWorks
    • Mybatis
      • Mybatis(一) - 概述
  • Java FrameWorks
    • Mybatis
      • Mybatis(七) - 结果集的封装与映射
  • Java FrameWorks
    • Mybatis
      • Mybatis(三) - mapper.xml及其加载机制
  • Java FrameWorks
    • Mybatis
      • Mybatis(九) - 事务
  • Java FrameWorks
    • Mybatis
      • Mybatis(二) - 全局配置文件及其加载机制
  • Java FrameWorks
    • Mybatis
      • Mybatis(五) - SqlSession执行流程
  • Java FrameWorks
    • Mybatis
      • Mybatis(八) - 缓存
  • Java FrameWorks
    • Mybatis
      • Mybatis(六) - 动态SQL的参数绑定与执行
  • Java FrameWorks
    • Mybatis
      • Mybatis(十) - 插件
  • Java FrameWorks
    • Mybatis
      • Mybatis(十一) - 日志
  • Java FrameWorks
    • Mybatis
      • Mybatis(四) - Mapper接口解析
  • Java FrameWorks
    • Netty
      • Netty 可靠性分析
  • Java FrameWorks
    • Netty
      • Netty - Netty 线程模型
  • Java FrameWorks
    • Netty
      • Netty堆外内存泄露排查盛宴
  • Java FrameWorks
    • Netty
      • Netty高级 - 高性能之道
  • Java FrameWorks
    • Shiro
      • Shiro + JWT + Spring Boot Restful 简易教程
  • Java FrameWorks
    • Shiro
      • 非常详尽的 Shiro 架构解析!
  • Java FrameWorks
    • Spring
      • Spring AOP 使用介绍,从前世到今生
  • Java FrameWorks
    • Spring
      • Spring AOP 源码解析
  • Java FrameWorks
    • Spring
      • Spring Event 实现原理
  • Java FrameWorks
    • Spring
      • Spring Events
  • Java FrameWorks
    • Spring
      • Spring IOC容器源码分析
  • Java FrameWorks
    • Spring
      • Spring Integration简介
  • Java FrameWorks
    • Spring
      • Spring MVC 框架中拦截器 Interceptor 的使用方法
  • Java FrameWorks
    • Spring
      • Spring bean 解析、注册、实例化流程源码剖析
  • Java FrameWorks
    • Spring
      • Spring validation中@NotNull、@NotEmpty、@NotBlank的区别
  • Java FrameWorks
    • Spring
      • Spring 如何解决循环依赖?
  • Java FrameWorks
    • Spring
      • Spring 异步实现原理与实战分享
  • Java FrameWorks
    • Spring
      • Spring中的“for update”问题
  • Java FrameWorks
    • Spring
      • Spring中的设计模式
  • Java FrameWorks
    • Spring
      • Spring事务失效的 8 大原因
  • Java FrameWorks
    • Spring
      • Spring事务管理详解
  • Java FrameWorks
    • Spring
      • Spring计时器StopWatch使用
  • Java FrameWorks
    • Spring
      • 详述 Spring MVC 框架中拦截器 Interceptor 的使用方法
  • Java FrameWorks
    • Spring
      • 透彻的掌握 Spring 中@transactional 的使用
  • Java
    • Java IO&NIO&AIO
      • Java IO - BIO 详解
  • Java
    • Java IO&NIO&AIO
      • Java NIO - IO多路复用详解
  • Java
    • Java IO&NIO&AIO
      • Java N(A)IO - Netty
  • Java
    • Java IO&NIO&AIO
      • Java IO - Unix IO模型
  • Java
    • Java IO&NIO&AIO
      • Java IO - 分类
  • Java
    • Java IO&NIO&AIO
      • Java NIO - 基础详解
  • Java
    • Java IO&NIO&AIO
      • Java IO - 常见类使用
  • Java
    • Java IO&NIO&AIO
      • Java AIO - 异步IO详解
  • Java
    • Java IO&NIO&AIO
      • Java IO概述
  • Java
    • Java IO&NIO&AIO
      • Java IO - 设计模式
  • Java
    • Java IO&NIO&AIO
      • Java NIO - 零拷贝实现
  • Java
    • Java JVM
      • JVM 优化经验总结
  • Java
    • Java JVM
      • JVM 内存结构
  • Java
    • Java JVM
      • JVM参数设置
  • Java
    • Java JVM
      • Java 内存模型
  • Java
    • Java JVM
      • 从实际案例聊聊Java应用的GC优化
  • Java
    • Java JVM
      • Java 垃圾回收器G1详解
  • Java
    • Java JVM
      • 垃圾回收器Shenandoah GC详解
  • Java
    • Java JVM
      • 垃圾回收器ZGC详解
  • Java
    • Java JVM
      • 垃圾回收基础
  • Java
    • Java JVM
      • 如何优化Java GC
  • Java
    • Java JVM
      • 类加载机制
  • Java
    • Java JVM
      • 类字节码详解
  • Java
    • Java 基础
      • Java hashCode() 和 equals()
  • Java
    • Java 基础
      • Java 基础 - Java native方法以及JNI实践
  • Java
    • Java 基础
      • Java serialVersionUID 有什么作用?
  • Java
    • Java 基础
      • Java 泛型的类型擦除
  • Java
    • Java 基础
      • Java 基础 - Unsafe类解析
  • Java
    • Java 基础
      • Difference Between Statement and PreparedStatement
  • Java
    • Java 基础
      • Java 基础 - SPI机制详解
  • Java
    • Java 基础
      • Java 基础 - final
  • Java
    • Java 基础
      • Java中static关键字详解
  • Java
    • Java 基础
      • 为什么说Java中只有值传递?
  • Java
    • Java 基础
      • Java 基础 - 即时编译器原理解析及实践
  • Java
    • Java 基础
      • Java 基础 - 反射
  • Java
    • Java 基础
      • Java多态的面试题
  • Java
    • Java 基础
      • Java 基础 - 异常机制详解
  • Java
    • Java 基础
      • 为什么要有抽象类?
  • Java
    • Java 基础
      • 接口的本质
  • Java
    • Java 基础
      • Java 基础 - 枚举
  • Java
    • Java 基础
      • Java 基础 - 泛型机制详解
  • Java
    • Java 基础
      • Java 基础 - 注解机制详解
  • Java
    • Java 基础
      • 为什么 String hashCode 方法选择数字31作为乘子
  • Java
    • Java 并发
      • Java 并发 - 14个Java并发容器
  • Java
    • Java 并发
      • Java 并发 - AQS
  • Java
    • Java 并发
      • Java 并发 - BlockingQueue
  • Java
    • Java 并发
      • Java 并发 - CAS
  • Java
    • Java 并发
      • Java 并发 - Condition接口
  • Java
    • Java 并发
      • Java 并发 - CopyOnWriteArrayList
  • Java
    • Java 并发
      • Java 并发 - CountDownLatch、CyclicBarrier和Phaser对比
  • Java
    • Java 并发
      • Java 并发 - Fork&Join框架
  • Java
    • Java 并发
      • Java 并发 - Java CompletableFuture 详解
  • Java
    • Java 并发
      • Java 并发 - Java 线程池
  • Java
    • Java 并发
      • Java 并发 - Lock接口
  • Java
    • Java 并发
      • Java 并发 - ReentrantLock
  • Java
    • Java 并发
      • Java 并发 - ReentrantReadWriteLock
  • Java
    • Java 并发
      • Java 并发 - Synchronized
  • Java
    • Java 并发
      • Java 并发 - ThreadLocal 内存泄漏问题
  • Java
    • Java 并发
      • Java 并发 - ThreadLocal
  • Java
    • Java 并发
      • Java 并发 - Volatile
  • Java
    • Java 并发
      • Java 并发 - 从ReentrantLock的实现看AQS的原理及应用
  • Java
    • Java 并发
      • Java 并发 - 公平锁和非公平锁
  • Java
    • Java 并发
      • Java 并发 - 内存模型
  • Java
    • Java 并发
      • Java 并发 - 原子类
  • Java
    • Java 并发
      • Java 并发 - 如何确保三个线程顺序执行?
  • Java
    • Java 并发
      • Java 并发 - 锁
  • Java
    • Java 的新特性
      • Java 10 新特性概述
  • Java
    • Java 的新特性
      • Java 11 新特性概述
  • Java
    • Java 的新特性
      • Java 12 新特性概述
  • Java
    • Java 的新特性
      • Java 13 新特性概述
  • Java
    • Java 的新特性
      • Java 14 新特性概述
  • Java
    • Java 的新特性
      • Java 15 新特性概述
  • Java
    • Java 的新特性
      • Java 8的新特性
  • Java
    • Java 的新特性
      • Java 9 新特性概述
  • Java
    • Java 调试排错
      • 调试排错 - Java Debug Interface(JDI)详解
  • Java
    • Java 调试排错
      • 调试排错 - CPU 100% 排查优化实践
  • Java
    • Java 调试排错
      • 调试排错 - Java Heap Dump分析
  • Java
    • Java 调试排错
      • 调试排错 - Java Thread Dump分析
  • Java
    • Java 调试排错
      • 调试排错 - Java动态调试技术原理
  • Java
    • Java 调试排错
      • 调试排错 - Java应用在线调试Arthas
  • Java
    • Java 调试排错
      • 调试排错 - Java问题排查:工具单
  • Java
    • Java 调试排错
      • 调试排错 - 内存溢出与内存泄漏
  • Java
    • Java 调试排错
      • 调试排错 - 在线分析GC日志的网站GCeasy
  • Java
    • Java 调试排错
      • 调试排错 - 常见的GC问题分析与解决
  • Java
    • Java 集合
      • Java 集合 - ArrayList
  • Java
    • Java 集合
      • Java 集合 - HashMap 和 ConcurrentHashMap
  • Java
    • Java 集合
      • Java 集合 - HashMap的死循环问题
  • Java
    • Java 集合
      • Java 集合 - LinkedHashSet&Map
  • Java
    • Java 集合
      • Java 集合 - LinkedList
  • Java
    • Java 集合
      • Java 集合 - PriorityQueue
  • Java
    • Java 集合
      • Java 集合 - Stack & Queue
  • Java
    • Java 集合
      • Java 集合 - TreeSet & TreeMap
  • Java
    • Java 集合
      • Java 集合 - WeakHashMap
  • Java
    • Java 集合
      • Java 集合 - 为什么HashMap的容量是2的幂次方
  • Java
    • Java 集合
      • Java 集合 - 概览
  • Java
    • Java 集合
      • Java 集合 - 高性能队列Disruptor详解
  • 分布式
    • RPC
      • ⭐️RPC - Dubbo&hsf&Spring cloud的区别
  • 分布式
    • RPC
      • ⭐️RPC - Dubbo的架构原理
  • 分布式
    • RPC
      • ⭐️RPC - HSF的原理分析
  • 分布式
    • RPC
      • ⭐️RPC - 你应该知道的RPC原理
  • 分布式
    • RPC
      • ⭐️RPC - 动态代理
  • 分布式
    • RPC
      • 深入理解 RPC 之协议篇
  • 分布式
    • RPC
      • RPC - 序列化和反序列化
  • 分布式
    • RPC
      • ⭐️RPC - 服务注册与发现
  • 分布式
    • RPC
      • RPC - 核心原理
  • 分布式
    • RPC
      • ⭐️RPC - 框架对比
  • 分布式
    • RPC
      • ⭐️RPC - 网络通信
  • 分布式
    • 分布式事务
      • 分布式事务 Seata TCC 模式深度解析
  • 分布式
    • 分布式事务
      • 分布式事务的实现原理
  • 分布式
    • 分布式事务
      • 常用的分布式事务解决方案
  • 分布式
    • 分布式事务
      • 手写实现基于消息队列的分布式事务框架
  • 分布式
    • 分布式算法
      • CAP 定理的含义
  • 分布式
    • 分布式算法
      • Paxos和Raft比较
  • 分布式
    • 分布式算法
      • 分布式一致性与共识算法
  • 分布式
    • 分布式锁
      • ⭐️分布式锁的原理及实现方式
  • 分布式
    • 搜索引擎
      • ElasticSearch与SpringBoot的集成与JPA方法的使用
  • 分布式
    • 搜索引擎
      • 全文搜索引擎 Elasticsearch 入门教程
  • 分布式
    • 搜索引擎
      • 十分钟学会使用 Elasticsearch 优雅搭建自己的搜索系统
  • 分布式
    • 搜索引擎
      • 腾讯万亿级 Elasticsearch 技术解密
  • 分布式
    • 日志系统
      • Grafana Loki 简明教程
  • 分布式
    • 日志系统
      • 分布式系统中如何优雅地追踪日志
  • 分布式
    • 日志系统
      • 如何优雅地记录操作日志?
  • 分布式
    • 日志系统
      • 日志收集组件—Flume、Logstash、Filebeat对比
  • 分布式
    • 日志系统
      • 集中式日志系统 ELK 协议栈详解
  • 分布式
    • 消息队列
      • 消息队列 - Kafka
  • 分布式
    • 消息队列
      • 消息队列 - Kafka、RabbitMQ、RocketMQ等消息中间件的对比
  • 分布式
    • 消息队列
      • 消息队列之 RabbitMQ
  • 分布式
    • 消息队列
      • 消息队列 - 使用docker-compose构建kafka集群
  • 分布式
    • 消息队列
      • 消息队列 - 分布式系统与消息的投递
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息的可靠性传输
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息的顺序性
  • 分布式
    • 消息队列
      • 消息队列 - 如何保证消息队列的高可用
  • 分布式
    • 消息队列
      • 消息队列 - 消息队列设计精要
  • 分布式
    • 监控系统
      • 深度剖析开源分布式监控CAT
  • 大数据
    • Flink
      • Flink架构与核心组件
  • 微服务
    • Dubbo
      • 基于dubbo的分布式应用中的统一异常处理
  • 微服务
    • Dubbo
      • Vim快捷键
  • 微服务
    • Service Mesh
      • Istio 是什么?
  • 微服务
    • Service Mesh
      • OCTO 2.0:美团基于Service Mesh的服务治理系统详解
  • 微服务
    • Service Mesh
      • Service Mesh是什么?
  • 微服务
    • Service Mesh
      • Spring Cloud向Service Mesh迁移
  • 微服务
    • Service Mesh
      • 数据挖掘算法
  • 微服务
    • Service Mesh
      • Seata Saga 模式
  • 微服务
    • Spring Cloud
      • Seata TCC 模式
  • 微服务
    • Spring Cloud
      • Spring Cloud Config
  • 微服务
    • Spring Cloud
      • Seata AT 模式
  • 微服务
    • Spring Cloud
      • Spring Cloud Gateway
  • 微服务
    • Spring Cloud
      • Spring Cloud OpenFeign 的核心原理
  • 微服务
    • Spring Cloud
      • Seata XA 模式
  • 数据库
    • Database Version Control
      • Liquibase vs. Flyway
  • 数据库
    • Database Version Control
      • Six reasons to version control your database
  • 数据库
    • MySQL
      • How Sharding Works
  • 数据库
    • MySQL
      • MySQL InnoDB中各种SQL语句加锁分析
  • 数据库
    • MySQL
      • MySQL 事务隔离级别和锁
  • 数据库
    • MySQL
      • MySQL 索引性能分析概要
  • 数据库
    • MySQL
      • MySQL 索引设计概要
  • 数据库
    • MySQL
      • MySQL出现Waiting for table metadata lock的原因以及解决方法
  • 数据库
    • MySQL
      • MySQL的Limit性能问题
  • 数据库
    • MySQL
      • MySQL索引优化explain
  • 数据库
    • MySQL
      • MySQL索引背后的数据结构及算法原理
  • 数据库
    • MySQL
      • MySQL行转列、列转行问题
  • 数据库
    • MySQL
      • 一条SQL更新语句是如何执行的?
  • 数据库
    • MySQL
      • 一条SQL查询语句是如何执行的?
  • 数据库
    • MySQL
      • 为什么 MySQL 使用 B+ 树
  • 数据库
    • MySQL
      • 为什么 MySQL 的自增主键不单调也不连续
  • 数据库
    • MySQL
      • 为什么我的MySQL会“抖”一下?
  • 数据库
    • MySQL
      • 为什么数据库不应该使用外键
  • 数据库
    • MySQL
      • 为什么数据库会丢失数据
  • 数据库
    • MySQL
      • 事务的可重复读的能力是怎么实现的?
  • 数据库
    • MySQL
      • 大众点评订单系统分库分表实践
  • 数据库
    • MySQL
      • 如何保证缓存与数据库双写时的数据一致性?
  • 数据库
    • MySQL
      • 浅谈数据库并发控制 - 锁和 MVCC
  • 数据库
    • MySQL
      • 深入浅出MySQL 中事务的实现
  • 数据库
    • MySQL
      • 浅入浅出MySQL 和 InnoDB
  • 数据库
    • PostgreSQL
      • PostgreSQL upsert功能(insert on conflict do)的用法
  • 数据库
    • Redis
      • Redis GEO & 实现原理深度分析
  • 数据库
    • Redis
      • Redis 和 I/O 多路复用
  • 数据库
    • Redis
      • Redis分布式锁
  • 数据库
    • Redis
      • Redis实现分布式锁中的“坑”
  • 数据库
    • Redis
      • Redis总结
  • 数据库
    • Redis
      • 史上最全Redis高可用技术解决方案大全
  • 数据库
    • Redis
      • Redlock:Redis分布式锁最牛逼的实现
  • 数据库
    • Redis
      • 为什么 Redis 选择单线程模型
  • 数据库
    • TiDB
      • 新一代数据库TiDB在美团的实践
  • 数据库
    • 数据仓库
      • 实时数仓在有赞的实践
  • 数据库
    • 数据库原理
      • OLTP与OLAP的关系是什么?
  • 数据库
    • 数据库原理
      • 为什么 OLAP 需要列式存储
  • 系统设计
    • DDD
      • Domain Primitive
  • 系统设计
    • DDD
      • Repository模式
  • 系统设计
    • DDD
      • 应用架构
  • 系统设计
    • DDD
      • 聊聊如何避免写流水账代码
  • 系统设计
    • DDD
      • 领域层设计规范
  • 系统设计
    • DDD
      • 从三明治到六边形
  • 系统设计
    • DDD
      • 阿里盒马领域驱动设计实践
  • 系统设计
    • DDD
      • 领域驱动设计(DDD)编码实践
  • 系统设计
    • DDD
      • 领域驱动设计在互联网业务开发中的实践
  • 系统设计
    • 基础架构
      • 容错,高可用和灾备
  • 系统设计
    • 数据聚合
      • GraphQL及元数据驱动架构在后端BFF中的实践
  • 系统设计
    • 数据聚合
      • 高效研发-闲鱼在数据聚合上的探索与实践
  • 系统设计
    • 服务安全
      • JSON Web Token 入门教程
  • 系统设计
    • 服务安全
      • 你还在用JWT做身份认证嘛?
  • 系统设计
    • 服务安全
      • 凭证(Credentials)
  • 系统设计
    • 服务安全
      • 授权(Authorization)
  • 系统设计
    • 服务安全
      • 理解OAuth2.0
  • 系统设计
    • 服务安全
      • 认证(Authentication)
  • 系统设计
    • 架构案例
      • 微信 Android 客户端架构演进之路
  • 系统设计
    • 高可用架构
      • 业务高可用的保障:异地多活架构
  • 计算机基础
    • 字符编码
      • Base64原理解析
  • 计算机基础
    • 字符编码
      • 字符编码笔记:ASCII,Unicode 和 UTF-8
  • 计算机基础
    • 操作系统
      • 为什么 CPU 访问硬盘很慢
  • 计算机基础
    • 操作系统
      • 为什么 HTTPS 需要 7 次握手以及 9 倍时延
  • 计算机基础
    • 操作系统
      • 为什么 Linux 默认页大小是 4KB
  • 计算机基础
    • 操作系统
      • 磁盘IO那些事
  • 计算机基础
    • 操作系统
      • 虚拟机的3种网络模式
  • 计算机基础
    • 服务器
      • mac终端bash、zsh、oh-my-zsh最实用教程
  • 计算机基础
    • 服务器
      • Nginx强制跳转Https
  • 计算机基础
    • 服务器
      • curl 的用法指南
  • 计算机基础
    • 网络安全
      • 如何设计一个安全的对外接口?
  • 计算机基础
    • 网络安全
      • 浅谈常见的七种加密算法及实现
  • 计算机基础
    • 网络编程
      • MQTT - The Standard for IoT Messaging
  • 计算机基础
    • 网络编程
      • 两万字长文 50+ 张趣图带你领悟网络编程的内功心法
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有 TIME_WAIT 状态
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有性能问题
  • 计算机基础
    • 网络编程
      • 为什么 TCP 协议有粘包问题
  • 计算机基础
    • 网络编程
      • 为什么 TCP 建立连接需要三次握手
  • 计算机基础
    • 网络编程
      • 为什么 TCP/IP 协议会拆分数据
  • 计算机基础
    • 网络编程
      • 使用 OAuth 2 和 JWT 为微服务提供安全保障
  • 计算机基础
    • 网络编程
      • 四种常见的 POST 提交数据方式
  • 计算机基础
    • 网络编程
      • 有赞TCP网络编程最佳实践
  • 计算机基础
    • 网络编程
      • 看完这篇HTTP,跟面试官扯皮就没问题了
  • 计算机基础
    • 网络编程
      • 详细解析 HTTP 与 HTTPS 的区别
  • 质量&效率
    • 快捷键
      • Idea快捷键(Mac版)
  • 质量&效率
    • 快捷键
      • Shell快捷键
  • 质量&效率
    • 快捷键
      • conduit
  • 质量&效率
    • 敏捷开发
      • Scrum的3种角色
  • 质量&效率
    • 敏捷开发
      • Scrum的4种会议
  • 质量&效率
    • 敏捷开发
      • ThoughtWorks的敏捷开发
  • 质量&效率
    • 敏捷开发
      • 敏捷开发入门教程
  • 运维&测试
    • Docker
      • Docker (容器) 的原理
  • 运维&测试
    • Docker
      • Docker Compose:链接外部容器的几种方式
  • 运维&测试
    • Docker
      • Docker 入门教程
  • 运维&测试
    • Docker
      • Docker 核心技术与实现原理
  • 运维&测试
    • Docker
      • Dockerfile 最佳实践
  • 运维&测试
    • Docker
      • Docker开启Remote API 访问 2375端口
  • 运维&测试
    • Docker
      • Watchtower - 自动更新 Docker 镜像与容器
  • 运维&测试
    • Kubernetes
      • Kubernetes 介绍
  • 运维&测试
    • Kubernetes
      • Kubernetes 在有赞的实践
  • 运维&测试
    • Kubernetes
      • Kubernetes 学习路径
  • 运维&测试
    • Kubernetes
      • Kubernetes如何改变美团的云基础设施?
  • 运维&测试
    • Kubernetes
      • Kubernetes的三种外部访问方式:NodePort、LoadBalancer 和 Ingress
  • 运维&测试
    • Kubernetes
      • 谈 Kubernetes 的架构设计与实现原理
  • 运维&测试
    • 压测
      • 全链路压测平台(Quake)在美团中的实践
  • 运维&测试
    • 测试
      • Cpress - JavaScript End to End Testing Framework
  • 运维&测试
    • 测试
      • 代码覆盖率-JaCoCo
  • 运维&测试
    • 测试
      • 浅谈代码覆盖率
  • 运维&测试
    • 测试
      • 测试中 Fakes、Mocks 以及 Stubs 概念明晰
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP中的Bean是如何被AOP代理的
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP原生动态代理和Cglib动态代理
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP实现方式(xml&注解)
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP是如何收集切面类并封装的
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP概述
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP的底层核心后置处理器
  • Java FrameWorks
    • Spring
      • Spring AOP
        • Spring AOP的延伸知识
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(一)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(三)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(二)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(五)
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - IOC(四) - 循环依赖与解决方案
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot - 启动引导
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot JarLauncher
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot Web Mvc 自动装配
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 使用ApplicationListener监听器
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 声明式事务
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot 嵌入式容器
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot引起的“堆外内存泄漏”排查及经验总结
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot的启动流程
  • Java FrameWorks
    • Spring
      • Spring Boot
        • Spring Boot自动化配置源码分析
  • Java FrameWorks
    • Spring
      • Spring Boot
        • 如何自定义Spring Boot Starter?
  • Java FrameWorks
    • Spring
      • Spring IOC
        • IOC - 模块装配和条件装配
  • Java FrameWorks
    • Spring
      • Spring IOC
        • IOC - 配置源(xml,注解)
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Environment
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring ApplicationContext
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanDefinition
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanFactory
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanFactoryPostProcessor
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring BeanPostProcessor
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(一) - 概述
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(三) - 实例化阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(二) - BeanDefinition
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(五) - 销毁阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Bean的生命周期(四) - 初始化阶段
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring ComponentScan
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Events
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 基础篇
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 总结
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC 进阶篇
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring IOC容器的生命周期
  • Java FrameWorks
    • Spring
      • Spring IOC
        • Spring Resource
  • Java FrameWorks
    • Spring
      • Spring MVC
        • DispatcherServlet的初始化原理
  • Java FrameWorks
    • Spring
      • Spring MVC
        • DispatcherServlet的核心工作原理
  • Java FrameWorks
    • Spring
      • Spring MVC
        • WebMvc的架构设计与组件功能解析
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Boot 2 + Spring Security 5 + JWT 的单页应用 Restful 解决方案
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Security Oauth
  • Java FrameWorks
    • Spring
      • Spring Security
        • Spring Security
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • DispatcherHandler的工作原理(传统方式)
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • DispatcherHandler的工作原理(函数式端点)
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • WebFlux的自动装配
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • 快速了解响应式编程与Reactive
  • Java FrameWorks
    • Spring
      • Spring WebFlux
        • 快速使用WebFlux
  • 分布式
    • 协调服务
      • Zookeeper
        • Zookeeper - 客户端之 Curator
  • 分布式
    • 协调服务
      • Zookeeper
        • 详解分布式协调服务 ZooKeeper
  • 分布式
    • 协调服务
      • etcd
        • 高可用分布式存储 etcd 的实现原理
  • 数据库
    • Database Version Control
      • Flyway
        • Database Migrations with Flyway
  • 数据库
    • Database Version Control
      • Flyway
        • How Flyway works
  • 数据库
    • Database Version Control
      • Flyway
        • Rolling Back Migrations with Flyway
  • 数据库
    • Database Version Control
      • Flyway
        • The meaning of the concept of checksums
  • 数据库
    • Database Version Control
      • Liquibase
        • Introduction to Liquibase Rollback
  • 数据库
    • Database Version Control
      • Liquibase
        • LiquiBase中文学习指南
  • 数据库
    • Database Version Control
      • Liquibase
        • Use Liquibase to Safely Evolve Your Database Schema
  • 系统设计
    • 流量控制
      • RateLimiter
        • Guava Rate Limiter实现分析
  • 系统设计
    • 流量控制
      • Sentinel
        • Sentinel 与 Hystrix 的对比
  • 系统设计
    • 流量控制
      • Sentinel
        • Sentinel工作主流程
  • 系统设计
    • 流量控制
      • 算法
        • 分布式服务限流实战
  • 系统设计
    • 解决方案
      • 秒杀系统
        • 如何设计一个秒杀系统
  • 系统设计
    • 解决方案
      • 红包系统
        • 微信高并发资金交易系统设计方案--百亿红包背后的技术支撑
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 什么是预排序遍历树算法(MPTT,Modified Preorder Tree Traversal)
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 加密算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 推荐系统算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • linkerd
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 查找算法
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 缓存淘汰算法中的LRU和LFU
  • 计算机基础
    • 数据结构与算法
      • 其他相关
        • 负载均衡算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Paxos算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Raft算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - Snowflake算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - ZAB算法
  • 计算机基础
    • 数据结构与算法
      • 分布式算法
        • 分布式算法 - 一致性Hash算法
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Bitmap & Bloom Filter
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Map & Reduce
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - Trie树/数据库/倒排索引
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 分治/hash/排序
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 双层桶划分
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 外(磁盘文件)排序
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理 - 布隆过滤器
  • 计算机基础
    • 数据结构与算法
      • 大数据处理
        • 大数据处理算法
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 文本预处理:后缀树(Suffix Tree)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:BM 算法 (Boyer-Moore)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:KMP 算法(Knuth-Morris-Pratt)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配 - 模式预处理:朴素算法(Naive)(暴力破解)
  • 计算机基础
    • 数据结构与算法
      • 字符串匹配算法
        • 字符串匹配
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 分支限界算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 分治算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 动态规划算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 回溯算法
  • 计算机基础
    • 数据结构与算法
      • 常用算法
        • 贪心算法
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 十大排序算法
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(一)之3种简单排序(选择,冒泡,直接插入)
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(三)之堆排序
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(二)之希尔排序
  • 计算机基础
    • 数据结构与算法
      • 排序算法
        • 图解排序算法(四)之归并排序
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 树的高度和深度
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 红黑树深入剖析及Java实现
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 线性结构 - Hash
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 线性结构 - 数组、链表、栈、队列
  • 计算机基础
    • 数据结构与算法
      • 数据结构
        • 逻辑结构 - 树
  • 运维&测试
    • 测试
      • Spock
        • Groovy 简明教程
  • 运维&测试
    • 测试
      • Spock
        • Spock 官方文档
  • 运维&测试
    • 测试
      • Spock
        • Spock单元测试框架介绍以及在美团优选的实践
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(一)
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(三)
  • 运维&测试
    • 测试
      • TDD
        • TDD 实践 - FizzFuzzWhizz(二)
  • 运维&测试
    • 测试
      • TDD
        • 测试驱动开发(TDD)- 原理篇
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Nacos
          • Nacos 服务注册的原理
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Nacos
          • Nacos 配置中心原理分析
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • 服务调用过程
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Bus
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Consul
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Seata
          • Spring Cloud Stream
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Sentinel
          • Sentinel 与 Hystrix 的对比
  • 微服务
    • Spring Cloud
      • Spring Cloud Alibaba
        • Sentinel
          • Sentinel
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • How Hystrix Works
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Hystrix
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Hystrix原理与实战
  • 微服务
    • Spring Cloud
      • Spring Cloud Netflix
        • Hystrix
          • Spring Cloud Hystrix基本原理
由 GitBook 提供支持
在本页
  • 1. 倔强青铜
  • 2. 荣耀黄金
  • 3. 最强王者
  • 4. 荣耀王者
  • 5. 推荐阅读

这有帮助吗?

  1. 计算机基础
  2. 数据结构与算法
  3. 其他相关

缓存淘汰算法中的LRU和LFU

上一页其他相关下一页计算机基础

最后更新于2年前

这有帮助吗?

转载:

已经 0202 年了,大厂面试手撸算法题已经是标配。第一轮就遇到手撸 LRU / LFU 的几率还是挺大的。LeetCode 上 和 ,LRU 是 Medium 难度,LFU 是 Hard 难度,面试官眼里认为这 2 个问题是最最最基础的。这篇文章就来聊聊面试中 LRU / LFU 的青铜与王者。

缓存淘汰算法不仅仅只有 LRU / LFU 这两种,还有很多种,TLRU (Time aware least recently used),PLRU (Pseudo-LRU),SLRU (Segmented LRU),LFRU (Least frequent recently used),LFUDA (LFU with dynamic aging),LIRS (Low inter-reference recency set),ARC (Adaptive Replacement Cache),FIFO (First In First Out),MRU (Most recently used),LIFO (Last in first out),FILO (First in last out),CAR (Clock with adaptive replacement) 等等。感兴趣的同学可以把这每一种都用代码实现一遍。

1. 倔强青铜

面试官可能就直接拿出 LeetCode 上这 2 道题让你来做的。在笔者拿出标准答案之前,先简单介绍一下 LRU 和 LFU 的概念。

2021-04-11-yH19Va

LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。如上图,要插入 F 的时候,此时需要淘汰掉原来的一个页面。

根据 LRU 的策略,每次都淘汰最近最久未使用的页面,所以先淘汰 A 页面。再插入 C 的时候,发现缓存中有 C 页面,这个时候需要把 C 页面放到首位,因为它被使用了。以此类推,插入 G 页面,G 页面是新页面,不在缓存中,所以淘汰掉 B 页面。插入 H 页面,H 页面是新页面,不在缓存中,所以淘汰掉 D 页面。插入 E 的时候,发现缓存中有 E 页面,这个时候需要把 E 页面放到首位。插入 I 页面,I 页面是新页面,不在缓存中,所以淘汰掉 F 页面。

可以发现,LRU 更新和插入新页面都发生在链表首,删除页面都发生在链表尾。

LRU 要求查询尽量高效,O(1) 内查询。那肯定选用 map 查询。修改,删除也要尽量 O(1) 完成。搜寻常见的数据结构,链表,栈,队列,树,图。树和图排除,栈和队列无法任意查询中间的元素,也排除。所以选用链表来实现。但是如果选用单链表,删除这个结点,需要 O(n) 遍历一遍找到前驱结点。所以选用双向链表,在删除的时候也能 O(1) 完成。

由于 Go 的 container 包中的 list 底层实现是双向链表,所以可以直接复用这个数据结构。定义 LRUCache 的数据结构如下:

import "container/list"

type LRUCache struct {
    Cap  int
    Keys map[int]*list.Element
    List *list.List
}

type pair struct {
    K, V int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        Cap: capacity,
        Keys: make(map[int]*list.Element),
        List: list.New(),
    }
}

这里需要解释 2 个问题,list 中的值存的是什么?pair 这个结构体有什么用?

type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element

	// The list to which this element belongs.
	list *List

	// The value stored with this element.
	Value interface{}
}

在 container/list 中,这个双向链表的每个结点的类型是 Element。Element 中存了 4 个值,前驱和后继结点,双向链表的头结点,value 值。这里的 value 是 interface 类型。笔者在这个 value 里面存了 pair 这个结构体。这就解释了 list 里面存的是什么数据。

为什么要存 pair 呢?单单指存 v 不行么,为什么还要存一份 key ?原因是在 LRUCache 执行删除操作的时候,需要维护 2 个数据结构,一个是 map,一个是双向链表。在双向链表中删除淘汰出去的 value,在 map 中删除淘汰出去 value 对应的 key。如果在双向链表的 value 中不存储 key,那么再删除 map 中的 key 的时候有点麻烦。如果硬要实现,需要先获取到双向链表这个结点 Element 的地址。然后遍历 map,在 map 中找到存有这个 Element 元素地址对应的 key,再删除。这样做时间复杂度是 O(n),做不到 O(1)。所以双向链表中的 Value 需要存储这个 pair。

LRUCache 的 Get 操作很简单,在 map 中直接读取双向链表的结点。如果 map 中存在,将它移动到双向链表的表头,并返回它的 value 值,如果 map 中不存在,返回 -1。

func (c *LRUCache) Get(key int) int {
	if el, ok := c.Keys[key]; ok {
		c.List.MoveToFront(el)
		return el.Value.(pair).V
	}
	return -1
}

LRUCache 的 Put 操作也不难。先查询 map 中是否存在 key,如果存在,更新它的 value,并且把该结点移到双向链表的表头。如果 map 中不存在,新建这个结点加入到双向链表和 map 中。最后别忘记还需要维护双向链表的 cap,如果超过 cap,需要淘汰最后一个结点,双向链表中删除这个结点,map 中删掉这个结点对应的 key。

func (c *LRUCache) Put(key int, value int) {
	if el, ok := c.Keys[key]; ok {
		el.Value = pair{K: key, V: value}
		c.List.MoveToFront(el)
	} else {
		el := c.List.PushFront(pair{K: key, V: value})
		c.Keys[key] = el
	}
	if c.List.Len() > c.Cap {
		el := c.List.Back()
		c.List.Remove(el)
		delete(c.Keys, el.Value.(pair).K)
	}
}

总结,LRU 是由一个 map 和一个双向链表组成的数据结构。map 中 key 对应的 value 是双向链表的结点。双向链表中存储 key-value 的 pair。双向链表表首更新缓存,表尾淘汰缓存。如下图:

提交代码以后,成功通过所有测试用例。

LFU 是 Least Frequently Used 的缩写,即最不经常最少使用,也是一种常用的页面置换算法,选择访问计数器最小的页面予以淘汰。如下图,缓存中每个页面带一个访问计数器。

根据 LFU 的策略,每访问一次都要更新访问计数器。当插入 B 的时候,发现缓存中有 B,所以增加访问计数器的计数,并把 B 移动到访问计数器从大到小排序的地方。再插入 D,同理先更新计数器,再移动到它排序以后的位置。当插入 F 的时候,缓存中不存在 F,所以淘汰计数器最小的页面的页面,所以淘汰 A 页面。此时 F 排在最下面,计数为 1。

这里有一个比 LRU 特别的地方。如果淘汰的页面访问次数有多个相同的访问次数,选择最靠尾部的。如上图中,A、B、C 三者的访问次数相同,都是 1 次。要插入 F,F 不在缓存中,此时要淘汰 A 页面。F 是新插入的页面,访问次数为 1,排在 C 的前面。也就是说相同的访问次数,按照新旧顺序排列,淘汰掉最旧的页面。这一点是和 LRU 最大的不同的地方。

可以发现,LFU 更新和插入新页面可以发生在链表中任意位置,删除页面都发生在表尾。

LFU 同样要求查询尽量高效,O(1) 内查询。依旧选用 map 查询。修改和删除也需要 O(1) 完成,依旧选用双向链表,继续复用 container 包中的 list 数据结构。LFU 需要记录访问次数,所以每个结点除了存储 key,value,需要再多存储 frequency 访问次数。

还有 1 个问题需要考虑,一个是如何按频次排序?相同频次,按照先后顺序排序。如果你开始考虑排序算法的话,思考方向就偏离最佳答案了。排序至少 O(nlogn)。重新回看 LFU 的工作原理,会发现它只关心最小频次。其他频次之间的顺序并不关心。所以不需要排序。用一个 min 变量保存最小频次,淘汰时读取这个最小值能找到要删除的结点。相同频次按照先后顺序排列,这个需求还是用双向链表实现,双向链表插入的顺序体现了结点的先后顺序。相同频次对应一个双向链表,可能有多个相同频次,所以可能有多个双向链表。用一个 map 维护访问频次和双向链表的对应关系。删除最小频次时,通过 min 找到最小频次,然后再这个 map 中找到这个频次对应的双向链表,在双向链表中找到最旧的那个结点删除。这就解决了 LFU 删除操作。

LFU 的更新操作和 LRU 类似,也需要用一个 map 保存 key 和双向链表结点的映射关系。这个双向链表结点中存储的是 key-value-frequency 三个元素的元组。这样通过结点中的 key 和 frequency 可以反过来删除 map 中的 key。

定义 LFUCache 的数据结构如下:

import "container/list"

type LFUCache struct {
	nodes    map[int]*list.Element
	lists    map[int]*list.List
	capacity int
	min      int
}

type node struct {
	key       int
	value     int
	frequency int
}

func Constructor(capacity int) LFUCache {
	return LFUCache{nodes: make(map[int]*list.Element),
		lists:    make(map[int]*list.List),
		capacity: capacity,
		min:      0,
	}
}

LFUCache 的 Get 操作涉及更新 frequency 值和 2 个 map。在 nodes map 中通过 key 获取到结点信息。在 lists 删除结点当前 frequency 结点。删完以后 frequency ++。新的 frequency 如果在 lists 中存在,添加到双向链表表首,如果不存在,需要新建一个双向链表并把当前结点加到表首。再更新双向链表结点作为 value 的 map。最后更新 min 值,判断老的 frequency 对应的双向链表中是否已经为空,如果空了,min++。

func (this *LFUCache) Get(key int) int {
	value, ok := this.nodes[key]
	if !ok {
		return -1
	}
	currentNode := value.Value.(*node)
	this.lists[currentNode.frequency].Remove(value)
	currentNode.frequency++
	if _, ok := this.lists[currentNode.frequency]; !ok {
		this.lists[currentNode.frequency] = list.New()
	}
	newList := this.lists[currentNode.frequency]
	newNode := newList.PushFront(currentNode)
	this.nodes[key] = newNode
	if currentNode.frequency-1 == this.min && this.lists[currentNode.frequency-1].Len() == 0 {
		this.min++
	}
	return currentNode.value
}

LFU 的 Put 操作逻辑稍微多一点。先在 nodes map 中查询 key 是否存在,如果存在,获取这个结点,更新它的 value 值,然后手动调用一次 Get 操作,因为下面的更新逻辑和 Get 操作一致。如果 map 中不存在,接下来进行插入或者删除操作。判断 capacity 是否装满,如果装满,执行删除操作。在 min 对应的双向链表中删除表尾的结点,对应的也要删除 nodes map 中的键值。

由于新插入的页面访问次数一定为 1,所以 min 此时置为 1。新建结点,插入到 2 个 map 中。

func (this *LFUCache) Put(key int, value int) {
	if this.capacity == 0 {
		return
	}
	// 如果存在,更新访问次数
	if currentValue, ok := this.nodes[key]; ok {
		currentNode := currentValue.Value.(*node)
		currentNode.value = value
		this.Get(key)
		return
	}
	// 如果不存在且缓存满了,需要删除
	if this.capacity == len(this.nodes) {
		currentList := this.lists[this.min]
		backNode := currentList.Back()
		delete(this.nodes, backNode.Value.(*node).key)
		currentList.Remove(backNode)
	}
	// 新建结点,插入到 2 个 map 中
	this.min = 1
	currentNode := &node{
		key:       key,
		value:     value,
		frequency: 1,
	}
	if _, ok := this.lists[1]; !ok {
		this.lists[1] = list.New()
	}
	newList := this.lists[1]
	newNode := newList.PushFront(currentNode)
	this.nodes[key] = newNode
}

总结,LFU 是由两个 map 和一个 min 指针组成的数据结构。一个 map 中 key 存的是访问次数,对应的 value 是一个个的双向链表,此处双向链表的作用是在相同频次的情况下,淘汰表尾最旧的那个页面。另一个 map 中 key 对应的 value 是双向链表的结点,结点中比 LRU 多存储了一个访问次数的值,即结点中存储 key-value-frequency 的元组。此处双向链表的作用和 LRU 是类似的,可以根据 map 中的 key 更新双向链表结点中的 value 和 frequency 的值,也可以根据双向链表结点中的 key 和 frequency 反向更新 map 中的对应关系。如下图:

提交代码以后,成功通过所有测试用例。

2. 荣耀黄金

面试中如果给出了上面青铜的答案,可能会被追问,“还有没有其他解法?” 虽然目前青铜的答案已经是最优解了,但是面试官还想考察多解。

先考虑 LRU。数据结构上想不到其他解法了,但从打败的百分比上,看似还有常数的优化空间。笔者反复思考,觉得可能导致运行时间变长的地方是在 interface{} 类型推断,其他地方已无优化的空间。手写一个双向链表提交试试,代码如下:

type LRUCache struct {
	head, tail *Node
	keys       map[int]*Node
	capacity   int
}

type Node struct {
	key, val   int
	prev, next *Node
}

func ConstructorLRU(capacity int) LRUCache {
	return LRUCache{keys: make(map[int]*Node), capacity: capacity}
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.keys[key]; ok {
		this.Remove(node)
		this.Add(node)
		return node.val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, ok := this.keys[key]; ok {
		node.val = value
		this.Remove(node)
		this.Add(node)
		return
	} else {
		node = &Node{key: key, val: value}
		this.keys[key] = node
		this.Add(node)
	}
	if len(this.keys) > this.capacity {
		delete(this.keys, this.tail.key)
		this.Remove(this.tail)
	}
}

func (this *LRUCache) Add(node *Node) {
	node.prev = nil
	node.next = this.head
	if this.head != nil {
		this.head.prev = node
	}
	this.head = node
	if this.tail == nil {
		this.tail = node
		this.tail.next = nil
	}
}

func (this *LRUCache) Remove(node *Node) {
	if node == this.head {
		this.head = node.next
		if node.next != nil {
			node.next.prev = nil
		}
		node.next = nil
		return
	}
	if node == this.tail {
		this.tail = node.prev
		node.prev.next = nil
		node.prev = nil
		return
	}
	node.prev.next = node.next
	node.next.prev = node.prev
}

提交以后还真的 100% 了。

上述代码实现的 LRU 本质并没有优化,只是换了一个写法,没有用 container 包而已。

利用 Priority Queue 维护一个最小堆,堆顶是访问次数最小的元素。map 中的 value 存储的是优先队列中结点。

import "container/heap"

type LFUCache struct {
	capacity int
	pq       PriorityQueue
	hash     map[int]*Item
	counter  int
}

func Constructor(capacity int) LFUCache {
	lfu := LFUCache{
		pq:       PriorityQueue{},
		hash:     make(map[int]*Item, capacity),
		capacity: capacity,
	}
	return lfu
}

Get 和 Put 操作要尽量的快,有 2 个问题需要解决。当访问次数相同时,如何删除掉最久的元素?当元素的访问次数发生变化时,如何快速调整堆?为了解决这 2 个问题,定义如下的数据结构:

// An Item is something we manage in a priority queue.
type Item struct {
	value     int // The value of the item; arbitrary.
	key       int
	frequency int // The priority of the item in the queue.
	count     int // use for evicting the oldest element
	// The index is needed by update and is maintained by the heap.Interface methods.
	index int // The index of the item in the heap.
}

堆中的结点存储这 5 个值。count 值用来决定哪个是最老的元素,类似一个操作时间戳。index 值用来 re-heapify 调整堆的。接下来实现 PriorityQueue 的方法。

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
	if pq[i].frequency == pq[j].frequency {
		return pq[i].count < pq[j].count
	}
	return pq[i].frequency < pq[j].frequency
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value int, frequency int, count int) {
	item.value = value
	item.count = count
	item.frequency = frequency
	heap.Fix(pq, item.index)
}

在 Less() 方法中,frequency 从小到大排序,frequency 相同的,按 count 从小到大排序。按照优先队列建堆规则,可以得到,frequency 最小的在堆顶,相同的 frequency,count 最小的越靠近堆顶。

在 Swap() 方法中,记得要更新 index 值。在 Push() 方法中,插入时队列的长度即是该元素的 index 值,此处也要记得更新 index 值。update() 方法调用 Fix() 函数。Fix() 函数比先 Remove() 再 Push() 一个新的值,花销要小。所以此处调用 Fix() 函数,这个操作的时间复杂度是 O(log n)。

这样就维护了最小 Index Priority Queue。Get 操作非常简单:

func (this *LFUCache) Get(key int) int {
	if this.capacity == 0 {
		return -1
	}
	if item, ok := this.hash[key]; ok {
		this.counter++
		this.pq.update(item, item.value, item.frequency+1, this.counter)
		return item.value
	}
	return -1
}

在 hashmap 中查询 key,如果存在,counter 时间戳累加,调用 Priority Queue 的 update 方法,调整堆。

func (this *LFUCache) Put(key int, value int) {
	if this.capacity == 0 {
		return
	}
	this.counter++
	// 如果存在,增加 frequency,再调整堆
	if item, ok := this.hash[key]; ok {
		this.pq.update(item, value, item.frequency+1, this.counter)
		return
	}
	// 如果不存在且缓存满了,需要删除。在 hashmap 和 pq 中删除。
	if len(this.pq) == this.capacity {
		item := heap.Pop(&this.pq).(*Item)
		delete(this.hash, item.key)
	}
	// 新建结点,在 hashmap 和 pq 中添加。
	item := &Item{
		value: value,
		key:   key,
		count: this.counter,
	}
	heap.Push(&this.pq, item)
	this.hash[key] = item
}

用最小堆实现的 LFU,Put 时间复杂度是 O(capacity),Get 时间复杂度是 O(capacity),不及 2 个 map 实现的版本。巧的是最小堆的版本居然打败了 100%。

3. 最强王者

在面试者回答出黄金级的问题了以后,面试官可能会继续追问一个更高级的问题。“如何实现一个高并发且线程安全的 LRU 呢?”。遇到这个问题,上文讨论的代码模板就失效了。要想做到高并发,需要考虑 2 点,第一点内存分配与回收 GC 一定要快,最好是 Zero GC 开销,第二点执行操作耗时最少。详细的,由于要做到高并发,瞬间的 TPS 可能会很大,所以要最快的分配内存,开辟新的内存空间。垃圾回收也不能慢,否则内存会暴涨。针对 LRU / LFU 这个问题,执行的操作是 get 和 set,耗时需要最少。耗时高了,系统吞吐率会受到严重影响,TPS 上不去了。再者,在高并发的场景中,一定会保证线程安全。这里就需要用到锁。最简单的选用读写锁。以下举例以 LRUCache 为例。LFUCache 原理类似。(以下代码先给出改造新增的部分,最后再给出完整版)

type LRUCache struct {
    sync.RWMutex
}

func (c *LRUCache) Get(key int) int {
	c.RLock()
	defer c.RUnlock()
	
	……
}

func (c *LRUCache) Put(key int, value int) {
	c.Lock()
  	defer c.Unlock()
  	
	……
}

上述代码虽然能保证线程安全,但是并发量并不高。因为在 Put 操作中,写锁会阻碍读锁,这里会锁住。接下来的优化思路很清晰,拆分大锁,让写锁尽可能的少阻碍读锁。一句话就是将锁颗粒化。

如上图,将一个大的临界区拆分成一个个小的临界区。代码如下:

type LRUCache struct {
    sync.RWMutex
    shards map[int]*LRUCacheShard
}

type LRUCacheShard struct {
  	Cap  int
	Keys map[int]*list.Element
	List *list.List
	sync.RWMutex
}

func (c *LRUCache) Get(key int) int {
	shard, ok := c.GetShard(key, false)
	if ok == false {
		return -1
	}
	shard.RLock()
	defer shard.RUnlock()
	
	……
}

func (c *LRUCache) Put(key int, value int) {
  	shard, _ := c.GetShard(key, true)
	shard.Lock()
	defer shard.Unlock()
	
	……
}

func (c *LRUCache) GetShard(key int, create bool) (shard *LRUCacheShard, ok bool) {
	hasher := sha1.New()
	hasher.Write([]byte(key))
	shardKey := fmt.Sprintf("%x", hasher.Sum(nil))[0:2]

	c.lock.RLock()
	shard, ok = c.shards[shardKey]
	c.lock.RUnlock()

	if ok || !create {
		return
	}

	//only time we need to write lock
	c.lock.Lock()
	defer c.lock.Unlock()
	//check again in case the group was created in this short time
	shard, ok = c.shards[shardKey]
	if ok {
		return
	}

	shard = &LRUCacheShard{
		Keys: make(map[int]*list.Element),
		List: list.New(),
	}
	c.shards[shardKey] = shard
	ok = true
	return
}

通过上述的改造,利用哈希把原来的 LRUCache 分为了 256 个分片(2^8)。并且写锁锁住只发生在分片不存在的时候。一旦分片被创建了,之后都是读锁。这里依旧是小瓶颈,继续优化,消除掉这里的写锁。优化代码很简单,在创建的时候创建所有分片。

func New(capacity int) LRUCache {
	shards := make(map[string]*LRUCacheShard, 256)
	for i := 0; i < 256; i++ {
		shards[fmt.Sprintf("%02x", i)] = &LRUCacheShard{
			Cap:  capacity,
			Keys: make(map[int]*list.Element),
			List: list.New(),
		}
	}
	return LRUCache{
		shards: shards,
	}
}

func (c *LRUCache) Get(key int) int {
	shard := c.GetShard(key)
	shard.RLock()
	defer shard.RUnlock()
	
	……
}

func (c *LRUCache) Put(key int, value int) {
  	shard := c.GetShard(key)
	shard.Lock()
	defer shard.Unlock()
	
	……
}

func (c *LRUCache) GetShard(key int) (shard *LRUCacheShard) {
  hasher := sha1.New()
  hasher.Write([]byte(key))
  shardKey :=  fmt.Sprintf("%x", hasher.Sum(nil))[0:2]
  return c.shards[shardKey]
}

到这里,大的临界区已经被拆分成细颗粒度了。在细粒度的锁内部,还包含双链表结点的操作,对结点的操作涉及到锁竞争。成熟的缓存系统如 memcached,使用的是全局的 LRU 链表锁,而 Redis 是单线程的所以不需要考虑并发的问题。回到 LRU,每个 Get 操作需要读取 key 值对应的 value,需要读锁。与此同时,Get 操作也涉及到移动最近最常使用的结点,需要写锁。Set 操作只涉及写锁。需要注意的一点,Get 和 Set 先后执行顺序非常关键。例如,先 get 一个不存在的 key,返回 nil,再 set 这个 key。如果先 set 这个 key,再 get 这个key,返回的就是不是 nil,而是对应的 value。所以在保证锁安全(不发生死锁)的情况下,还需要保证每个操作时序的正确性。能同时满足这 2 个条件的非带缓冲的 channel 莫属。先来看看消费 channel 通道里面数据的处理逻辑:

func (c *CLRUCache) doMove(el *list.Element) bool {
	if el.Value.(Pair).cmd == MoveToFront {
		c.list.MoveToFront(el)
		return false
	}
	newel := c.list.PushFront(el.Value.(Pair))
	c.bucket(el.Value.(Pair).key).update(el.Value.(Pair).key, newel)
	return true
}

还值得一提的是,get 和 set 的写操作有 2 种类型,一种是 MoveToFront,另外一种是当结点不存在的时候,需要先创建一个新的结点,并移动到头部。这个操作即 PushFront。笔者这里在结点中加入了 cmd 标识,默认值是 MoveToFront。

目前为止,下一步的优化思路确定使用带缓冲的 channel 了。用几个呢?答案是用 2 个。除去上面讨论的写入操作,还要管理 remove 操作。由于 LRU 逻辑的特殊性,它保证了移动结点和移除结点一定分开在双链表两端。也就是说在双链表两边同时操作,相互不影响。双链表的临界区范围可以进一步的缩小,可以缩小到结点级。最终方案就定下来了。用 2 个带缓冲的 channel,分别处理移动结点和删除结点,这两个 channel 可以在同一个协程中一起处理,互不影响。

func (c *CLRUCache) worker() {
	defer close(c.control)
	for {
		select {
		case el, ok := <-c.movePairs:
			if ok == false {
				goto clean
			}
			if c.doMove(el) && c.list.Len() > c.cap {
				el := c.list.Back()
				c.list.Remove(el)
				c.bucket(el.Value.(Pair).key).delete(el.Value.(Pair).key)
			}
		case el := <-c.deletePairs:
			c.list.Remove(el)
		case control := <-c.control:
			switch msg := control.(type) {
			case clear:
				for _, bucket := range c.buckets {
					bucket.clear()
				}
				c.list = list.New()
				msg.done <- struct{}{}
			}
		}
	}
clean:
	for {
		select {
		case el := <-c.deletePairs:
			c.list.Remove(el)
		default:
			close(c.deletePairs)
			return
		}
	}
}

以下性能测试部分是面试结束后,笔者测试的。面试时写完代码,并没有当场 Benchmark。

go test -bench BenchmarkGetAndPut1 -run none -benchmem -cpuprofile cpuprofile.out -memprofile memprofile.out -cpu=8goos: darwin
goarch: amd64
pkg: github.com/halfrost/LeetCode-Go/template
BenchmarkGetAndPut1-8            368578              2474 ns/op             530 B/op         14 allocs/op
PASS
ok      github.com/halfrost/LeetCode-Go/template        1.022s

BenchmarkGetAndPut2 只是简单的全局加锁,会有死锁的情况。可以看到方案一的性能还行,368578 次循环平均出来的结果,平均一次 Get/Set 需要 2474 ns,那么 TPS 大约是 300K/s,可以满足一般高并发的需求。

最后看看这个版本下的 CPU 消耗情况,符合预期:

内存分配情况,也符合预期:

至此,你已经是王者了。

4. 荣耀王者

这里是附加题部分。面试官问到这里就和 LRU/LFU 直接关系不大了,更多的考察的是如何设计一个高并发的 Cache。笔者之所以在这篇文章最后提一笔,是想给读者扩展思维。面试官会针对你给出的高并发版的 LRU 继续问,“你觉得你写的这个版本缺点在哪里?和真正的 Cache 比,还有哪些欠缺?”

在上一节“最强王者”中,粗略的实现了一个高并发的 LRU。但是这个方案还不是最完美的。当高并发高到一个临界值的时候,即 Get 请求的速度达到 Go 内存回收速度的几百倍,几万倍的时候。bucket 分片被清空,试图访问该分片中的 key 的 goroutine 开始分配内存,而先前的内存仍未完全释放,从而导致内存使用量激增和 OOM 崩溃。所以这种方法的性能不能随内核数量很好地扩展。

另外这种粗略的方式是以缓存数目作为 Cap 的,没有考虑每个 value 的大小。以缓存数目作为基准,是没法限制住内存大小的。如果高负载的业务,设置大的 Cap,极端的讲,每个 value 都非常大,几十个 MB,整体内存消耗可能上百 GB。如果是低负载的业务,设置很小的 Cap,极端情况,每个 value 特别小。总内存大小可能在 1KB。这样看,内存上限和下限浮动太大了,无法折中限制。

欠缺的分为 2 部分,一部分是功能性,一部分是性能。功能性方面欠缺 TTL,持久化。TTL 是过期时间,到时间需要删除 key。持久化是将缓存中的数据保存至文件中,或者启动的时候从文件中读取。

性能方面欠缺的是高效的 hash 算法,高命中率,内存限制,可伸缩性。

高效的 hash 算法指的是类似 AES Hash,针对 CPU 是否支持 AES 指令集进行了判断,当 CPU 支持 AES 指令集的时候,它会选用 AES Hash 算法。一些高效的 hash 算法用汇编语言实现的。

内存限制。无限大的缓存实际上是不可能的。高速缓存必须有大小限制。如何制定一套高效的淘汰的策略就变的很关键。LRU 这个淘汰策略好么?针对不同的使用场景,LRU 并不是最好的,有些场景下 LFU 更加适合。这里有一篇论文 [TinyLFU: A Highly Efficient Cache Admission Policy](https://dgraph.io/blog/refs/TinyLFU - A Highly Efficient Cache Admission Policy.pdf),这篇论文中讨论了一种高效缓存准入策略。TinyLFU 是一种与淘汰无关的准入策略,目的是在以很少的内存开销来提高命中率。主要思想是仅在新的 key 的估计值高于正要被逐出的 key 的估计值时才允许进入 Cache。当缓存达到容量时,每个新的 key 都应替换缓存中存在的一个或多个密钥。并且,传入 key 的估值应该比被淘汰出去的 key 估值高。否则新的 key 禁止进入缓存中。这样做也为了保证高命中率。

在将新 key 放入 TinyLFU 中之前,还可以使用 bloom 过滤器首先检查该密钥是否之前已被查看过。仅当 key 在布隆过滤器中已经存在时,才将其插入 TinyLFU。这是为了避免长时间不被看到的长尾键污染 TinyLFU。

最后看看 Go 实现的几个开源 Cache 库。关于这些 Cache 的源码分析,本篇文章就不展开了。(有时间可能会单独再开一篇文章详解)。感兴趣的读者可以自己查阅源码。

以下是这几个库的性能曲线图:

在一小时内对 CODASYL 数据库的引用:

在商业站点上运行的数据库服务器,该服务器在商业数据库之上运行 ERP 应用程序:

循环访问模式:

大型商业搜索引擎响应各种 Web 搜索请求而启动的磁盘读取访问:

吞吐量:

5. 推荐阅读

  • [Adaptive Software Cache Management](https://dgraph.io/blog/refs/Adaptive Software Cache Management.pdf)

  • [TinyLFU: A Highly Efficient Cache Admission Policy](https://dgraph.io/blog/refs/TinyLFU - A Highly Efficient Cache Admission Policy.pdf)

2021-04-11-F6HAHV
2021-04-11-HzGpXP
2021-04-11-Dh4WS6
2021-04-11-3ZNQep
2021-04-11-WrRxYk
2021-04-11-IIA02a
2021-04-11-QOOgyW
2021-04-11-hBdRQR

LFU 的另外一个思路是利用 这个数据结构。别被名字吓到,Index Priority Queue = map + Priority Queue,仅此而已。

2021-04-11-pkSlLv

提交以后,LRU 和 LFU 都打败了 100%。上述代码都封装好了,在 LeetCode-Go 中,讲解也更新到了 《LeetCode Cookbook》第三章的和中。LRU 的最优解是 map + 双向链表,LFU 的最优解是 2 个 map + 多个双向链表。其实热身刚刚结束,接下来才是本文的重点。

2021-04-11-KQ42mV
2021-04-11-FJiSZj

最终完整的代码放在了。最后简单的跑一下 Benchmark 看看性能如何。

2021-04-11-giM3JM
2021-04-11-SSCnBR

高命中率方面,可以参考 这篇论文,在这篇论文里面提出了 2 种方式:prefetching 和 batching。简单说一下 batching 的方式。在等待临界区之前,先填满 ring buffer。如该论文所述,借用 ring buffer 这种方式,几乎没有开销,从而大大降低了竞争。实现 ring buffer 可以考虑使用 sync.Pool 而不是其他的数据结构(切片,带区互斥锁等),原因是性能优势主要是由于线程本地存储的内部使用,而其他的数据结构没有这相关的 API。

2021-04-11-3Xopdn
2021-04-11-OlYYhO

关于到底选择 LRU 还是 LFU 还是 LRU + LFU ,这个话题比较大,展开讨论又可以写好几篇新文章了。感兴趣的读者可以看看这篇论文,[Adaptive Software Cache Management](https://dgraph.io/blog/refs/Adaptive Software Cache Management.pdf) ,从标题上看,自适应的软件缓存管理,就能看出它在探讨了这个问题。论文的基本思想是在主缓存段之前放置一个 LRU “窗口”,并使用爬山技术自适应地调整窗口大小以最大化命中率。 已经取得了很好的效果。

2021-04-11-lawvhV

可伸缩性方面,选择合适的缓存大小,可以避免 ,在多核系统中,其中不同的原子计数器(每个8字节)位于同一高速缓存行(通常为64字节)中。对这些计数器之一进行的任何更新都会导致其他计数器被标记为无效。这将强制为拥有该高速缓存的所有其他核心重新加载高速缓存,从而在高速缓存行上创建写争用。为了实现可伸缩性,应该确保每个原子计数器完全占用完整的缓存行。因此,每个内核都在不同的缓存行上工作。

2021-04-11-eZaXpu

,BigCache 根据 key 的哈希将数据分为 shards。每个分片都包含一个映射和一个 ring buffer。每当设置新元素时,它都会将该元素追加到相应分片的 ring buffer 中,并且缓冲区中的偏移量将存储在 map 中。如果同一元素被 Set 多次,则缓冲区中的先前条目将标记为无效。如果缓冲区太小,则将其扩展直到达到最大容量。每个 map 中的 key 都是一个 uint32 hash,其值是一个 uint32 指针,指向该值与元数据信息一起存储的缓冲区中的偏移量。如果存在哈希冲突,则 BigCache 会忽略前一个键并将当前键存储到映射中。预先分配较少,较大的缓冲区并使用 map[uint32]uint32 是避免承担 GC 扫描成本的好方法。

,FreeCache 通过减少指针数量避免了 GC 开销。 无论其中存储了多少条目,都只有 512 个指针。通过 key 的哈希值将数据集分割为 256 个段。将新 key 添加到高速缓存时,将使用 key 哈希值的低八位来标识段 ID。每个段只有两个指针,一个是存储 key 和 value 的 ring buffer,另一个是用于查找条目的索引 slice。数据附加到 ring buffer 中,偏移量存储到排序 slice 中。如果 ring buffer 没有足够的空间,则使用修改后的 LRU 策略从 ring buffer 的开头开始,在该段中淘汰 key。如果条目的最后访问时间小于段的平均访问时间,则从 ring buffer 中删除该条目。要在 Get 的高速缓存中查找条目,请在相应插槽 slot 中的排序数组中执行二进制搜索。此外还有一个加速的优化,使用 key 的哈希的 LSB 9-16 选择一个插槽 slot。将数据划分为多个插槽 slot 有助于减少在缓存中查找键时的搜索空间。每个段都有自己的锁,因此它支持高并发访问。

,groupcache 是一个分布式的缓存和缓存填充库,在许多情况下可以替代 memcached。在许多情况下甚至可以用来替代内存缓存节点池。groupcache 实现原理和本文在上一章节中实现的方式是一摸一样的。

,fastcache 并没有缓存过期的概念。仅在高速缓存大小溢出时才从高速缓存中淘汰 key 值。key 的截止期限可以存储在该值内,以实现缓存过期。fastcache 缓存由许多 buckets 组成,每个 buckets 都有自己的锁。这有助于扩展多核 CPU 的性能,因为多个 CPU 可以同时访问不同的 buckets。每个 buckets 均由一个 hash(key)->(key,value)的映射和 64KB 大小的字节 slice(块)组成,这些字节 slice 存储已编码的(key,value)。每个 buckets 仅包含 chunksCount 个指针。例如,64GB 缓存将包含大约 1M 指针,而大小相似的 map[string][]byte 将包含 1B指针,用于小的 key 和 value。这样做可以节约巨大的 GC 开销。与每个 bucket 中的单个 chunk 相比,64KB 大小的 chunk 块减少了内存碎片和总内存使用量。如果可能,将大 chunk 块分配在堆外。这样做可以减少了总内存使用量,因为 GC 无需要 GOGC 调整即可以更频繁地收集未使用的内存。

,ristretto 拥有非常优秀的缓存命中率。淘汰策略采用简单的 LFU,性能与 LRU 相当,并且在搜索和数据库跟踪上具有更好的性能。存入策略采用 TinyLFU 策略,它几乎没有内存开销(每个计数器 12 位)。淘汰策略根据代价值判断,任何代价值大的 key 都可以淘汰多个代价值较小的 key(代价值可以是自定义的衡量标准)。

2021-04-11-lJARGX
2021-04-11-4wkQws
2021-04-11-GoOHog
2021-04-11-XHtcci
2021-04-11-46oKe2
2021-04-11-ZHVLfi
2021-04-11-zBGYVl

Index Priority Queue
完整代码
第三节 LRUCache
第四节 LFUCache
这里
BP-Wrapper: A System Framework Making Any Replacement Algorithms (Almost) Lock Contention Free
A high performance caching library for Java 8 — Caffeine
False Sharing
bigcache
freecache
groupCache
fastcache
ristretto
BP-Wrapper: A System Framework Making Any Replacement Algorithms (Almost) Lock Contention Free
LIRS: An Efficient Low Inter-reference Recency Set Replacement - Policy to Improve Buffer Cache Performance
ARC: A Self-Tuning, Low Overhead Replacement Cache
面试中 LRU / LFU 的青铜与王者
146. LRU Cache
460. LFU Cache