redis 如何实现 LRU

LRU 是一个缓存置换算法，在缓存有限的情况下，如果有新的数据加载至缓存，则需要考虑将不会再继续被访问的数据剔除掉，但是缓存是否会被访问是没有办法预测的，所以，LRU 是基于一个假设实现：

这也是 LRU 实现的一个思路，它首先实现一个双向链表，当一个 key 被访问时，则将这个 key 放到双向链表的头部，当时缓存不可用时，从尾部逐个剔除

如果按照这样的假设实现，会存在一些缺陷，假设我们现在有一张数据表，执行如下 SQL 语句:

上面这条 SQL 的作用是将数据表中的所有数据读取出来，我们再将该数据表中的所有数据读取出后就不再继续使用，那么对于 LRU 的双向链表在头部会有大量数据占用，导致热点数据被逐出缓存以致于会出现大量磁盘 I/O

MySQL Innodb 的 buufer pool 实现了一个改进版的 LRU,它将 LRU 的双向链表分为两部分，一个是 newlist 另一个是 oldlist，newlist 主要是用于存放头部热点数据，oldlist 用于存放非热点数据，当首次加载一个 page 时，会将数据放到 oldlist 的头部，再次访问的时候会移动到 newlist

而对于 redis ，redis 整体是一个大的 dict,如果要想实现双向链表，需要给每一个 key 新增两个指针，占用 16 个字节大小，并且需要一个额外的 list 结构存储双向链表的头尾节点信息，这样会占用一定的内存空间，导致 redis 性能下降，所以，redis 并没有实现双向链表

redis 整体是一个大的 dict，每一个 value 被保存为一个 redisobj 结构，每一个 redisobj 结构都包含有一个 lru 字段，该字段存储的是一个时间戳，当根据 key 获取值的时候，会调用 lookup 函数，如果开启了 LRU 模式，则该函数会将 lru 的替换成当前秒级的时间戳，然后 redis 再使用随机采样法，从 dict 中筛选出 5 个key(注意：这里的 5 个 key 是可以修改的，由 maxmemory-smples 控制)，比较 lru 值的大小，淘汰掉最小的那个

在 redis 30 以后对该算法进行了一个升级，新的算法维护了一个候选池(pool)，首次筛选出来的 key 会被全部放入到候选池中，在后续的筛选过程中只有 lru 小于候选池中最小的 lru 才能被放入到候选池，直至候选池放满，当候选池满了的时候，如果有新的数据继续放入，则需要将候选池中 lru 字段最大值取出

然后在淘汰的时候，只需要将候选池中 lru 字段值最小的淘汰掉即可

前面的两篇文章中，我们分别介绍了扩大与缩小SQL数据库环境之间的区别以及通过水平数据分区或垂直数据分区分解数据表。在本系列的最后一部分，我们将深入了解如何利用分布式分区视图来分解数据表。
分布式分区视图可以将来自一个或多个SQL Server数据库中的数据连接起来。当开发一个水平分区数据库环境时，你可以使用分布式分区视图将来自不同服务器的分区表连接起来，使得这些数据看起来像来自同一个服务器。
你可以设计这些视图，因此，如果你的潜在数据表结构设计合理的话，查询优化器就可以知道从那个数据表得到查询需要的数据，从而加速运行。一个设计合理的分布式分区视图还可以实现更新、插入和删除。我们将在本文的下一部分深入探讨它是如何实现这样 *** 作的。
示例
本例中，我们假设SalesHistory表非常大，如果水平分割表中的各行记录到不同的服务器上，这将对我们很有利。每个服务器上的SalesHistory表的表结构是一样的，不过，一台服务器上存放该国东部地区的销售信息，而另外一台存放该国西部地区的销售信息。
我们根据Region（地区）字段和SaleID 来区分表中的各条记录。其中SaleID字段是整型数据域，我们为该国不同的地区设定了不同的SaleID。
这个字段对于设计概念来说非常重要，因为这是我们用来作为分区键值字段。（注意：要在缩小场景中进行表的设计，这一点极其重要，因为这样表中的各行是唯一的，从而可区别于其它服务器上的表。）这个字段集合是分区键。
设计很多SaleHistory表，根据所在的表SaleID始终是唯一可区别的。我们可以通过CHECK约束来实现这一点。
我们将使用两个独立的SQL Server实例，对于本例，这两个实例在同一台机器上。服务器的名字叫Chapman，实例分别称为实例A和实例B。这两个实例都是SQL Server 2005开发版，允许远程连接以及Windows和SQL Server认证。
使用脚本创建SalesDB数据库，设置每台服务器的lazy schema validation选项，使用该选项在SQL Server中通过确保在确实需要服务器上的数据时才进行服务器链接请求来提高性能。
列表A中的脚本需要在两个数据库实例上运行。列表B用来创建SalesDB数据库中的读者登录及用户，该脚本也需要在两个数据库实例上运行。

直观上看，数据库中的数据都是按表存储的；更微观地看，这些表都是按行存储的。每执行一
次select查询，数据库都会返回一个结果集，这个结果集由若干行组成。所以，一个自然而然
的想法就是在Redis中找到一种对应于数据库l行的数据结构。Redis中提供了五种基本数据结构
，即字符串（string）、列表（list）、哈希（hash）、集合（set）和有序集合（sorted
set）。经过调研，发现适合存储行的数据结构有两种，即string和hash。
要把数据库的行数据存入string，首先需要对行数据进行格式化。事实上，结果集的
每一行都可以看做若干由字段名和其对应值组成的键值对集合。这种键值对结构很容易让我们
想起Json格式。因此，这里选用Json格式作为结果集每一行的格式化模板。根据这一想法，我
们可以实现将结果集格式化为若干Json对象，并将Json对象转化为字符串存入Redis。

要把数据库的行数据存入hash，过程要比把数据存入string直观很多。这是由hash的结构性质
决定的——hash本身就是一个键值对集合：一个“父键”下面包含了很多“子键”，每个“子
键”都对应一个值。根据前面的分析可知，结果集中的每一行实际上也是键值对集合。用
Redis键值对集合表示数据库键值对集合应该再合适不过了：对于结果集中的某一行，字段对应
于hash的“子键”，字段对应的值就是hash“子键”对应的值，即结果集的一行刚好对应一个
hash

Redis hash是一个string类型的field和value的映射表一个key可对应多个field，一个field对应一个value。将一个对象存储为hash类型，较于每个字段都存储成string类型更能节省内存。

高性能计算机集群系统是一个是基于网络、面向科研的小型高性能并行计算系统，该系统通过一组松散集成的计算机软件和硬件高度紧密地协作完成计算工作。通过局域网连接集群系统中的单个计算机节点，使之同时完成同一个工作，以达到高工作效率、高计算速度和高可靠性能。

该系统的基础是主控节点、计算节点等硬件基础平台和互联系统，系统分层次设计，按照Intel的高性能计算生态系统部署，自上而下，按照“HPC并行应用程序→中间件集群管理和通信库以及各类软件优化工具→ *** 作系统→计算节点和主控节点的硬件平台→系统环境”的部署进行设计，包括散热、电源、空间布局等规范化的设计。

1总的老说，优化方案中只有两种，一种是给查询的字段加组合索引。另一种是给在用户和数据库中增加缓存
2添加索引方案：面对1~2千的并发是没有压力的，在往上则限制的瓶颈就是数据库最大连接数了，在上面中我用show global status like 'Max_used_connections’查看数据库可以知道数据库最大响应连接数是5700多，超过这个数tomcat直接报错连接被拒绝或者连接已经失效
3缓存方案：在上面的测试可以知道，要是我们事先把数据库的千万条数据同步到redis缓存中，瓶颈就是我们的设备硬件性能了，假如我们的主机有几百个核心CPU，就算是千万级的并发下也可以完全无压力，带个用户很好的。
4索引+缓存方案：缓存事先没有要查询的数据，在一万的并发下测试数据库毫无压力，程序先通过查缓存再查数据库大大减轻了数据库的压力，即使缓存不命中在一万的并发下也能正常访问,在10万并发下数据库依然没压力，但是redis服务器设置最大连接数300去处理10万的线程，4核CPU处理不过来，很多redis连接不了。我用show global status like 'Max_used_connections'查看数据库发现最大响应连接数是388，这么低所以数据库是不会挂掉的。雷达下载更专业。
5使用场景：a几百或者2000以下并发直接加上组合索引就可以了。b不想加索引又高并发的情况下可以先事先把数据放到缓存中，硬件设备支持下可解决百万级并发。c加索引且缓存事先没有数据，在硬件设备支持下可解决百万级并发问题。d不加索引且缓存事先没有数据，不可取，要80多秒才能得到结果，用户体验极差。
6原理：其实使用了redis的话为什么数据库不会崩溃是因为redis最大连接数为300，这样数据库最大同时连接数也是300多，所以不会挂掉，至于redis为什么设置为300是因为设置的太高就会报错(连接被拒绝)或者等待超时(就算设置等待超时的时间很长也会报这个错)。

大致为两种措施：

一、脚本同步：

1、自己写脚本将数据库数据写入到redis/memcached。

2、这就涉及到实时数据变更的问题（mysqlrowbinlog的实时分析），binlog增量订阅Alibaba的canal，以及缓存层数据丢失/失效后的数据同步恢复问题。

二、业务层实现：

1、先读取nosql缓存层，没有数据再读取mysql层，并写入数据到nosql。

2、nosql层做好多节点分布式（一致性hash），以及节点失效后替代方案（多层hash寻找相邻替代节点），和数据震荡恢复了。

redis实现数据库缓存的分析：

对于变化频率非常快的数据来说，如果还选择传统的静态缓存方式（Memocached、FileSystem等）展示数据，可能在缓存的存取上会有很大的开销，并不能很好的满足需要，而Redis这样基于内存的NoSQL数据库，就非常适合担任实时数据的容器。

但是往往又有数据可靠性的需求，采用MySQL作为数据存储，不会因为内存问题而引起数据丢失，同时也可以利用关系数据库的特性实现很多功能。所以就会很自然的想到是否可以采用MySQL作为数据存储引擎，Redis则作为Cache。

MySQL到Redis数据复制方案，无论MySQL还是Redis，自身都带有数据同步的机制，比较常用的MySQL的Master/Slave模式，就是由Slave端分析Master的binlog来实现的，这样的数据复制其实还是一个异步过程，只不过当服务器都在同一内网时，异步的延迟几乎可以忽略。那么理论上也可用同样方式，分析MySQL的binlog文件并将数据插入Redis。

因此这里选择了一种开发成本更加低廉的方式，借用已经比较成熟的MySQLUDF，将MySQL数据首先放入Gearman中，然后通过一个自己编写的PHPGearmanWorker，将数据同步到Redis。比分析binlog的方式增加了不少流程，但是实现成本更低，更容易 *** 作。

Redis支持五种数据类型：string（字符串），hash（哈希），list（列表），set（集合）及zset(sorted set：有序集合)。

意思是 redis 的 string 可以包含任何数据。比如jpg或者序列化的对象，string 类型的值最大能存储 512MB。

Redis hash是一个 string 类型的 field 和 value 的映射表，hash 特别适合用于存储对象。

Redis list是简单的字符串列表，按照插入顺序排序。可以添加一个元素到列表的头部（左边）或者尾部（右边）。

Redis的Set是string类型的无序集合，集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是O(1)。

Redis zset 和 set 一样也是string类型元素的集合,且不允许重复的成员，不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。

---