Redis过期策略和内存淘汰机制

0.前言 既然Redis是内存缓存，那由于内存容量有限，不可能像文件DB那样把数据仍进去就完事了。 并且Redis里存放的多是热点数据，所以需要适时对过期的key进行清理，来释放空间；但是，在清理过后，仍然有可能还是存在大量的“废弃”key，这时候就需要内存淘汰机制来强制清理了。 过期时间 Redis支持为key设置一个生存时间TTL，在经过指定的时间后，Server会自动删除TTL=0的k

Redis
LRU

InnoDB存储引擎中的索引

0. 前言 在InnoDB存储引擎中，表都是根据主键顺序组织存放的，这种存储方式的表称为索引组织表（index organized table）。 在InnoDB存储引擎表中，每张表都有个主键（Primary Key），如果在创建表时没有显式地定义主键，则InnoDB存储引擎会按如下方式选择或创建主键： 首先判断表中是否有非空的唯一索引（Unique NOT NULL），如果有，则该列即为主

MySQL
索引

实现LRU/LFU缓存

0.前言 不管是计算机系统里的Cache缓存，还是现在流行的内存缓存，由于缓存容量的限制，都会设计淘汰算法，即选择哪一块“旧的”数据替换出去，用以存放“最新”的数据。 常见的淘汰算法有： FIFO：先进先出，最先进入缓存的数据，在缓存空间不足时被清除，为了保证最新数据可用，保证实时性 LRU（Least Recently Used）：最近最久未使用，基于访问次数，去除命中次数最少的元素，保证高

算法与数据结构
LRU LFU

MySQL中的「锁」与「事务」

0.前言 一方面要最大程度地利用数据库的并发访问，另外一方面还要确保每个用户能以一致的方式读取和修改数据。因此，便有了「锁」，用于对共享资源的并发访问[1]。 事务（Transaction）是数据库区别于文件系统的重要特性之一。事务会把数据库从一种一致状态转换为另一种一致状态。在数据库提交工作时，可以确保要么所有修改都已经保存了，要么所有修改都不保存。 本文主要以InnoDB为例，学习锁和事务的

MySQL
锁 事务

「分布式ID」生成方案

前言 全局唯一ID，用于唯一标识一个实体（用户、产品等）。在传统的单机架构下，一种常用的做法是使用数据库自增ID来作为主键，唯一标识一个实体。但是在分布式架构下，虽然可以设置自增起始值和自增步长来实现但是受限于业务规模，难以扩展，且受限于DB性能瓶颈。 现有的分布式全局唯一ID可大致分为如下三类： UUID 基于DB 基于雪花ID(Snowflake)方案 需满足的条件 全局唯一：必须保

分布式系统
分布式ID

「TOP K」问题的几种解法

序言 TOPKTOP KTOPK 问题应该是面试必问的算法题了，通常是问数组 numsnumsnums 中第 KKK 大或者第 KKK 小的元素。 通常有如下几种解法： 直接排序 优先队列（大根堆/小根堆） 快速选择（基于快排的划分） 本文以 LC 215. 数组中的第K个最大元素为例分析。 直接排序 这里贴一个快排模板，需要注意的是，每次划分中pivot的选取对快排性能影响很大，极端情况

算法与数据结构
快速选择 优先队列