Wetts's blog

数据结构-布隆过滤器.md

发表于 2021-04-07 分类于数据结构

转自：https://zhuanlan.zhihu.com/p/43263751

在进入正文之前，之前看到的有句话我觉得说得很好：

Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one.

大意是不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。

什么是布隆过滤器

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

实现原理

HashMap 的问题

讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 $O(1)$ 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。

布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7，则上图转变为：

Ok，我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：

值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。

这是为什么呢？答案跟简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。

支持删除么

感谢评论区提醒，传统的布隆过滤器并不支持删除操作。但是名为 Counting Bloom filter 的变种可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。可以参考文章 Counting Bloom Filter 的原理和实现

注：【首先需要判断一定存在，才能进行删除】

如何选择哈希函数个数和布隆过滤器长度

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率

如何选择适合业务的 k 和 m 值呢，这里直接贴一个公式：

如何推导这个公式这里只是提一句，因为对于使用来说并没有太大的意义，你让一个高中生来推会推得很快。k 次哈希函数某一 bit 位未被置为 1 的概率为：

$\left(1-\frac{1}{m}\right)^{k}$

插入n个元素后依旧为 0 的概率和为 1 的概率分别是：

$\left(1-\frac{1}{m}\right)^{n k} 1-\left(1-\frac{1}{m}\right)^{n k}$

标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 1，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定

$\left[1-\left(1-\frac{1}{m}\right)^{n k}\right]^{k} \approx\left(1-e^{-k n / m}\right)^{k}$

最佳实践

常见的适用常见有，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

另外，既然你使用布隆过滤器来加速查找和判断是否存在，那么性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。

大Value拆分

Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。

拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。

缓存-缓存雪崩，缓存穿透，缓存击穿出现的原因及解决方案.md

发表于 2021-04-07 分类于缓存

转自：https://blog.csdn.net/zzti_erlie/article/details/104655455

缓存雪崩

出现过程

假设有如下一个系统，高峰期请求为5000次/秒，4000次走了缓存，只有1000次落到了数据库上，数据库每秒1000的并发是一个正常的指标，完全可以正常工作，但如果缓存宕机了，或者缓存设置了相同的过期时间，导致缓存在同一时刻同时失效，每秒5000次的请求会全部落到数据库上，数据库立马就死掉了，因为数据库一秒最多抗2000个请求，如果DBA重启数据库，立马又会被新的请求打死了，这就是缓存雪崩。

解决方法

事前：redis高可用，主从+哨兵，redis cluster，避免全盘崩溃
事中：本地ehcache缓存 + hystrix限流&降级，避免MySQL被打死
事后：redis持久化RDB+AOF，快速恢复缓存数据
缓存的失效时间设置为随机值，避免同时失效

缓存穿透

出现过程

假如客户端每秒发送5000个请求，其中4000个为黑客的恶意攻击，即在数据库中也查不到。举个例子，用户id为正数，黑客构造的用户id为负数，如果黑客每秒一直发送这4000个请求，缓存就不起作用，数据库也很快被打死。

解决方法

对请求参数进行校验，不合理直接返回
查询不到的数据也放到缓存，value为空，如 set -999 “”
使用布隆过滤器，快速判断key是否在数据库中存在，不存在直接返回

第一种是最基本的策略，第二种其实并不常用，第三种比较常用。

为什么第二种并不常用呢？

因为如果黑客构造的请求id是随机数，第二种并不能起作用，反而由于缓存的清空策略，（例如清除最近没有被访问的缓存）导致有用的缓存被清除了。

缓存击穿

出现过程

设置了过期时间的key，承载着高并发，是一种热点数据。从这个key过期到重新从MySQL加载数据放到缓存的一段时间，大量的请求有可能把数据库打死。缓存雪崩是指大量缓存失效，缓存击穿是指热点数据的缓存失效

解决方法

设置key永远不过期，或者快过期时，通过另一个异步线程重新设置key

当从缓存拿到的数据为null，重新从数据库加载数据的过程上锁，下面写个分布式锁实现的demo

Redis实现分布式锁

加锁执行命令

1	SET resource_name random_value NX PX 30000

解锁执行脚本

if redis.call("get", KEYS[1]) == ARGV[1] then 
    return redis.call("del", KEYS[1]) 
else 
    return 0 
end

写一个分布式锁工具类

public class LockUtil {

    private static final String OK = "OK";
    private static final Long LONG_ONE = 1L;
    private static final String script = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";

    public static boolean tryLock(String key, String value, long expire) {
        Jedis jedis = RedisPool.getJedis();
        SetParams setParams = new SetParams();
        setParams.nx().px(expire);
        return OK.equals(jedis.set(key, value, setParams));
    }

    public static boolean releaseLock(String key, String value) {
        Jedis jedis = RedisPool.getJedis();
        return LONG_ONE.equals(jedis.eval(script, 1, key, value));
    }
}

工具类写起来还是挺简单的

示例代码

public String getData(String key) {
	String lockKey = "key";
	String lockValue = String.valueOf(System.currentTimeMillis());
	long expireTime = 1000L;
	String value = getFromRedis(key);
	if (value == null) {
		if (LockUtil.tryLock(lockKey, lockValue, expireTime)) {
			// 从数据库取值并放到redis中
			LockUtil.releaseLock(lockKey, lockValue);
		} else {
			// sleep一段时间再从缓存中拿
			Thread.sleep(100);
			getFromRedis(key);
		}
	}
	return value;
}

高并发-高并发下如何保证接口的幂等性.md

发表于 2021-03-24 分类于高并发

转自：https://blog.csdn.net/zzti_erlie/article/details/106910362

介绍

幂等性就是同一个操作执行多次，产生的效果一样。如 http 的 get 请求，数据库的 select 请求就是幂等的

在分布式系统中，保证接口的幂等性非常重要，如提交订单，扣款等接口都要保证幂等性，不然会造成重复创建订单，重复扣款，那么如何保证接口的幂等性呢？

前端保证幂等性的方法

按钮只能点击一次

用户点击按钮后将按钮置灰，或者显示 loading 状态

RPG 模式

即 Post-Redirect-Get，当客户提交表单后，去执行一个客户端的重定向，转到提交成功页面。避免用户按 F5 刷新导致的重复提交，也能消除按浏览器后退键导致的重复提交问题。目前绝大多数公司都是这样做的，比如淘宝，京东等

后端保证幂等性的方法

使用唯一索引

对业务唯一的字段加上唯一索引，这样当数据重复时，插入数据库会抛异常

状态机幂等

如果业务上需要修改订单状态，例如订单状态有待支付，支付中，支付成功，支付失败。设计时最好只支持状态的单向改变。这样在更新的时候就可以加上条件，多次调用也只会执行一次。例如想把订单状态更新为支持成功，则之前的状态必须为支付中

1	update table_name set status = 支付成功 where status = 支付中

乐观锁实现幂等

查询数据获得版本号

通过版本号去更新，版本号匹配则更新，版本号不匹配则不更新

-- 假如查询出的 version 为 1
select version from table_name where userid = 10;
-- 给用户的账户加10
update table_name set money = money -10, version = version + 1 where userid = 10 and version = 1

也可以通过条件来实现乐观锁，如库存不能超卖，数量不能小于 0

1	update table_name set num = num - 10 where num - 10 >= 0

防重表

增加一个防重表，业务唯一的id作为唯一索引，如订单号，当想针对订单做一系列操作时，可以向防重表中插入一条记录，插入成功，执行后续操作，插入失败，则不执行后续操作。本质上可以看成是基于MySQL实现的分布式锁。根据业务场景决定执行成功后，是否删除防重表中对应的数据

分布式锁实现幂等

执行方法时，先根据业务唯一的 id 获取分布式锁，获取成功，则执行，失败则不执行。分布式锁可以基于 redis，zookeeper，mysql 来实现，分布式锁的细节就不介绍了

select+insert

先查询一下有没有符合要求的数据，如果没有再执行插入。没有并发的系统中可以保证幂等性，高并发下不要用这种方法，也会造成数据的重复插入。我一般做消息幂等的时候就是先 select，有数据直接返回，没有数据加分布式锁进行 insert 操作

全局唯一号实现幂等

通过 source（来源）+ seq（序列号）来判断请求是否重复，重复则直接返回请求重复提交，否则执行。如当多个三方系统调用服务的时候，就可以采用这种方式

Java-多线程-多个线程执行完毕后，才执行另一个线程.md

发表于 2021-02-12 分类于 Java

转自：https://blog.csdn.net/zzti_erlie/article/details/100047508

CountDownLatch

去掉try catch版本

public static void main(String[] args) throws InterruptedException {

	/**
	 * Thread-1 在路上耗时4秒
	 * Thread-2 在路上耗时0秒
	 * Thread-0 在路上耗时4秒
	 * Thread-2 到达车站了
	 * Thread-1 到达车站了
	 * Thread-0 到达车站了
	 * 老司机，发车
	 */
	CountDownLatch countDownLatch = new CountDownLatch(3);
	Random random = new Random();
	for (int i = 0; i < 3; i++) {
		new Thread(() -> {
			//返回[0,5)的值
			int time = random.nextInt(5);
			System.out.println(Thread.currentThread().getName() + " 在路上耗时" + time + "秒");
			TimeUnit.SECONDS.sleep(time);
			System.out.println(Thread.currentThread().getName() + " 到达车站了");
			countDownLatch.countDown();
		}).start();
	}
	countDownLatch.await();
	System.out.println("老司机，发车");
}

先来演示一下用法，可以看到所有子线程都执行完毕才会执行主线程。实现这个功能主要靠的是 CountDownLatch 的 2 个方法 await() 和 countDown()。

new 一个 CountDownLatch 时会传一个计数器的值，上面的例子为 3。调用 await() 方法时判断计数是否为 0，如果不为 0 则呈等待状态。其他线程可以调用 countDown() 方法将计数减 1，当计数减到位 0 时，则呈等待的线程继续执行。

CyclicBarrier

去掉try catch版本

public static void main(String[] args) {

	/**
	 * Thread-1 在路上耗时0秒
	 * Thread-2 在路上耗时2秒
	 * Thread-1 到达车站了
	 * Thread-0 在路上耗时3秒
	 * Thread-2 到达车站了
	 * Thread-0 到达车站了
	 * 老司机，发车
	 */
	CyclicBarrier cyclicBarrier = new CyclicBarrier(3, ()->{
		System.out.println("老司机，发车");
	});
	Random random = new Random();
	for (int i = 0; i < 3; i++) {
		new Thread(() -> {
			//返回[0,5)的值
			int time = random.nextInt(5);
			System.out.println(Thread.currentThread().getName() + " 在路上耗时" + time + "秒");
			TimeUnit.SECONDS.sleep(time);
			System.out.println(Thread.currentThread().getName() + " 到达车站了");
			cyclicBarrier.await();
		}).start();
	}
}

CountDownLatch 的计数器只能使用一次，而 CyclicBarrier 的计数器可以使用 reset() 方法重置。挺简单的就不再演示。因为这 2 个工具类都用到了 AQS，而 AQS 的原理很长，因此在本文就不介绍 AQS 的实现了

CompletableFuture

去掉try catch版本

public static void main(String[] args) {
    /**
     * ForkJoinPool.commonPool-worker-1 在路上耗时4秒
     * ForkJoinPool.commonPool-worker-2 在路上耗时3秒
     * ForkJoinPool.commonPool-worker-1 到达车站了
     * ForkJoinPool.commonPool-worker-2 到达车站了
     * 老司机，发车
     */
    Random random = new Random();
    CompletableFuture future1 = CompletableFuture.runAsync(() -> {
        int time = random.nextInt(5);
        System.out.println(Thread.currentThread().getName() + " 在路上耗时" + time + "秒");
        TimeUnit.SECONDS.sleep(random.nextInt());
        System.out.println(Thread.currentThread().getName() + " 到达车站了");
    });
    CompletableFuture future2 = CompletableFuture.runAsync(() -> {
        int time = random.nextInt(5);
        System.out.println(Thread.currentThread().getName() + " 在路上耗时" + time + "秒");
        TimeUnit.SECONDS.sleep(random.nextInt());
        System.out.println(Thread.currentThread().getName() + " 到达车站了");
    });
    CompletableFuture.allOf(future1, future2).thenRun(() -> {
        System.out.println("老司机，发车");
    });
}

Java-多线程-线程状态转换图.md

发表于 2021-02-11 分类于 Java

转自：https://blog.csdn.net/zzti_erlie/article/details/95242525

介绍

简易的线程状态如下图

Java Thread线程内部有一个枚举内部类State，定义了Java语言线程状态的枚举值

NEW（初始化状态）
RUNNABLE （可运行/运行状态）
BLOCKED（阻塞状态）
WAITING （无时限等待）
TIMED_WAITING（有时限等待）
TERMINATED（终止状态）

Java 将操作系统层面的阻塞状态细分为 BLOCK，WAITING，TIMED_WAITING 三种状态

NEW：新建状态，线程被创建但未启动的状态。创建线程有三种方式

继承Thread类
实现Runnable接口
实现Callable接口

我们最常用的是通过实现接口这种方式，Runnable 和 Callable 接口的区别如下

Runnable 无法获取返回值，而 Callable 可以获取返回值
Runnable 无法抛出异常，而 Callable可以抛出异常

RUNNABLE（就绪状态）：调用start之后运行之前的状态
RUNNING（运行状态）：线程正在运行
BLOCKED（阻塞状态）：进入以下状态，有以下几种情况

BLOCK（同步阻塞）：锁被其他线程占用，如等待进入 synchronized 方法或者代码块
WAITING（主动阻塞）：执行Object.wait()，Thread.join() 等
TIMED_WAITING（等待阻塞）：执行 Object.wait(long)，Thread.sleep(long) 等

DEAD（终止状态）：线程执行完毕

最后将各种方法补充到线程状态图上

Java-多线程-一直往线程池里面放任务，会发生什么.md

发表于 2021-02-11 分类于 Java

转自：https://blog.csdn.net/zzti_erlie/article/details/108552109

线程池的各种参数

面试的时候最常问的就是线程池的各种参数的含义，和线程池的整个运行流程，这个一定要会

ThreadPoolExecutor 一共有 4 个构造函数，但最后调用的都是如下构造函数

来类比学习一下这些参数，我们把线程池类比为项目组，线程是这个公司的成员

corePoolSize：线程池中最少的线程数，一个项目组总得有 corePoolSize 人坚守阵地，都是签订劳动合同了，不能随便撤。
maximumPoolSize：当项目很忙时，就得加人，请其他项目组的人来帮忙。但是公司空间有限，最多只能加到 maximumPoolSize 个人。当项目闲了，就得撤人了，最多能撤到 corePoolSize 个人
keepAliveTime & unit：上面提到项目根据忙闲来增减人员，那在编程世界里，如何定义忙和闲呢？如果一个线程在 keepAliveTime（时间数字）* unit（时间单位）时间内都没有执行任务，说明这个线程很闲。如果此时线程数大于 corePoolSize，这个线程就要被回收了
workQueue：就是任务队列
threadFactory：自定义如果创建线程，例如给线程指定一个有意义的名字
handler：workQueue满了（排期满了），再提交任务，该怎么处理呢？这个就是处理策略，线程池提供了4种策略，你也可以实现RejectedExecutionHandler接口来自定义策略

类	策略
AbortPolicy	丢弃任务，抛运行时异常（默认的处理策略）
CallerRunsPolicy	执行任务
DiscardPolicy	忽视，什么都不会发生
DiscardOldestPolicy	丢弃队列里最近的一个任务，并执行当前任务

线程池的工作流程

可以参照一下源码理解一下下面的流程

线程池刚创建时，里面没有一个线程。任务队列是作为参数传进来的。不过，就算队列里面有任务，线程池也不会马上执行他们。
当调用 execute() 方法添加一个任务时，线程池会做如下判断：
1. 如果正在运行的线程数量小于 corePoolSize，那么马上创建线程运行这个任务
2. 如果正在运行的线程数量大于或等于 corePoolSize，那么将这个任务放入队列
3. 如果这时候队列满了，而且正在运行的线程数量小于 maximunPoolSize，那么还是要创建非核心线程立刻运行这个任务
4. 如果队列满了，而且正在运行的线程数量大于或等于 maximunPoolSize，那么线程池会抛出 RejectedExecutionException
当一个线程完成任务时，它会从队列中取下一个任务来执行
当一个线程无事可做，超过一定的时间（keepAliveTime）时，线程池会判断，如果当前运行的线程数大于 corePoolSize，那么这个线程就被停掉。所以线程池的所有任务完成后，它最终会收缩到 corePoolSize 的大小

可以用如下图来表示整体流程

Redis-原理-内存淘汰策略.md

发表于 2020-10-19 分类于 Redis

转自：https://zhuanlan.zhihu.com/p/105587132

过期策略

定期删除

redis 会将每个设置了过期时间的 key 放入到一个独立的字典中，以后会定期遍历这个字典来删除到期的 key。

Redis 默认会每秒进行十次过期扫描（100ms 一次），过期扫描不会遍历过期字典中所有的 key，而是采用了一种简单的贪心策略。

从过期字典中随机 20 个 key；
删除这 20 个 key 中已经过期的 key；
如果过期的 key 比率超过 1/4，那就重复步骤 1；

redis 默认是每隔 100ms 就随机抽取一些设置了过期时间的 key，检查其是否过期，如果过期就删除。注意这里是随机抽取的。为什么要随机呢？你想一想假如 redis 存了几十万个 key ，每隔 100ms 就遍历所有的设置过期时间的 key 的话，就会给 CPU 带来很大的负载。

惰性删除

所谓惰性策略就是在客户端访问这个 key 的时候，redis 对 key 的过期时间进行检查，如果过期了就立即删除，不会给你返回任何东西。

定期删除可能会导致很多过期 key 到了时间并没有被删除掉。所以就有了惰性删除。假如你的过期 key，靠定期删除没有被删除掉，还停留在内存里，除非你的系统去查一下那个 key，才会被 redis 给删除掉。这就是所谓的惰性删除，即当你主动去查过期的 key 时，如果发现 key 过期了，就立即进行删除，不返回任何东西。

总结：定期删除是集中处理，惰性删除是零散处理。

为什么需要淘汰策略

有了以上过期策略的说明后，就很容易理解为什么需要淘汰策略了，因为不管是定期采样删除还是惰性删除都不是一种完全精准的删除，就还是会存在 key 没有被删除掉的场景，所以就需要内存淘汰策略进行补充。

内存淘汰策略

noeviction：当内存使用超过配置的时候会返回错误，不会驱逐任何键
allkeys-lru：加入键的时候，如果过限，首先通过 LRU 算法驱逐最久没有使用的键
volatile-lru：加入键的时候如果过限，首先从设置了过期时间的键集合中驱逐最久没有使用的键
allkeys-random：加入键的时候如果过限，从所有 key 随机删除
volatile-random：加入键的时候如果过限，从过期键的集合中随机驱逐
volatile-ttl：从配置了过期时间的键中驱逐马上就要过期的键
volatile-lfu：从所有配置了过期时间的键中驱逐使用频率最少的键
allkeys-lfu：从所有键中驱逐使用频率最少的键

LRU

标准 LRU 实现方式

新增 key value 的时候首先在链表结尾添加 Node 节点，如果超过 LRU 设置的阈值就淘汰队头的节点并删除掉 HashMap 中对应的节点。
修改 key 对应的值的时候先修改对应的 Node 中的值，然后把 Node 节点移动队尾。
访问 key 对应的值的时候把访问的 Node 节点移动到队尾即可。

Redis 的 LRU 实现

Redis 维护了一个 24 位时钟，可以简单理解为当前系统的时间戳，每隔一定时间会更新这个时钟。每个 key 对象内部同样维护了一个 24 位的时钟，当新增 key 对象的时候会把系统的时钟赋值到这个内部对象时钟。比如我现在要进行 LRU，那么首先拿到当前的全局时钟，然后再找到内部时钟与全局时钟距离时间最久的（差最大）进行淘汰，这里值得注意的是全局时钟只有 24 位，按秒为单位来表示才能存储 194 天，所以可能会出现 key 的时钟大于全局时钟的情况，如果这种情况出现那么就两个相加而不是相减来求最久的 key。

struct redisServer {
       pid_t pid; 
       char *configfile; 
       //全局时钟
       unsigned lruclock:LRU_BITS; 
       ...
};
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    /* key对象内部时钟 */
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

Redis 中的 LRU 与常规的 LRU 实现并不相同，常规 LRU 会准确的淘汰掉队头的元素，但是 Redis 的 LRU 并不维护队列，只是根据配置的策略要么从所有的 key 中随机选择 N 个（N 可以配置）要么从所有的设置了过期时间的 key 中选出 N 个键，然后再从这 N 个键中选出最久没有使用的一个 key 进行淘汰。

下图是常规 LRU 淘汰策略与 Redis 随机样本取一键淘汰策略的对比，浅灰色表示已经删除的键，深灰色表示没有被删除的键，绿色表示新加入的键，越往上表示键加入的时间越久。从图中可以看出，在 redis 3 中，设置样本数为 10 的时候能够很准确的淘汰掉最久没有使用的键，与常规 LRU 基本持平。

为什么要使用近似 LRU？

性能问题，由于近似 LRU 算法只是最多随机采样 N 个 key 并对其进行排序，如果精准需要对所有 key 进行排序，这样近似 LRU 性能更高
内存占用问题，redis 对内存要求很高，会尽量降低内存使用率，如果是抽样排序可以有效降低内存的占用
实际效果基本相等，如果请求符合长尾法则，那么真实 LRU 与 Redis LRU 之间表现基本无差异
在近似情况下提供可自配置的取样率来提升精准度，例如通过 CONFIG SET maxmemory-samples <count> 指令可以设置取样数，取样数越高越精准，如果你的 CPU 和内存有足够，可以提高取样数看命中率来探测最佳的采样比例。

LFU

LFU 是在 Redis4.0 后出现的，LRU 的最近最少使用实际上并不精确，考虑下面的情况，如果在|处删除，那么 A 距离的时间最久，但实际上 A 的使用频率要比 B 频繁，所以合理的淘汰策略应该是淘汰 B。LFU 就是为应对这种情况而生的。

1
2
3

A~~A~~A~~A~~A~~A~~A~~A~~A~~A~~~|

B~~~~~B~~~~~B~~~~~B~~~~~~~~~~~~B|

LFU 把原来的 key 对象的内部时钟的 24 位分成两部分，前 16 位还代表时钟，后 8 位代表一个计数器。16 位的情况下如果还按照秒为单位就会导致不够用，所以一般这里以时钟为单位。而后 8 位表示当前 key 对象的访问频率，8 位只能代表 255，但是 redis 并没有采用线性上升的方式，而是通过一个复杂的公式，通过配置如下两个参数来调整数据的递增速度。

lfu-log-factor 可以调整计数器 counter 的增长速度，lfu-log-factor 越大，counter 增长的越慢。
lfu-decay-time 是一个以分钟为单位的数值，可以调整 counter 的减少速度。

所以这两个因素就对应到了 LFU 的 Counter 减少策略和增长策略，它们实现逻辑分别如下。

降低 LFUDecrAndReturn

先从高 16 位获取最近的降低时间 ldt 以及低 8 位的计数器 counter 值
计算当前时间 now 与 ldt 的差值（now-ldt），当 ldt 大于 now 时，那说明是过了一个周期，按照 65535-ldt+now 计算（16 位一个周期最大 65535）
使用第 2 步计算的差值除以 lfu_decay_time，即 LFUTimeElapsed(ldt) / server.lfu_decay_time，已过去 n 个 lfu_decay_time，则将 counter 减少 n。

增长 LFULogIncr

获取 0-1 的随机数 r

计算 0-1 之间的控制因子 p，它的计算逻辑如下

//LFU_INIT_VAL默认为5
baseval = counter - LFU_INIT_VAL;
//计算控制因子
p = 1.0/(baseval*lfu_log_factor+1);

如果 r 小于 p，counter 增长 1

p 取决于当前 counter 值与 lfu_log_factor 因子，counter 值与 lfu_log_factor 因子越大，p 越小，r 小于 p 的概率也越小，counter 增长的概率也就越小。增长情况如下图：

从左到右表示 key 的命中次数，从上到下表示影响因子，在影响因子为 100 的条件下，经过 10M 次命中才能把后 8 位值加满到 255.

新生 KEY 策略

另外一个问题是，当创建新对象的时候，对象的 counter 如果为 0，很容易就会被淘汰掉，还需要为新生 key 设置一个初始 counter。counter 会被初始化为 LFU_INIT_VAL，默认 5。

分布式锁-基于redis的setnx()、get()、getset()方法分布式锁.md

发表于 2020-10-18 分类于分布式

转自：https://www.cnblogs.com/changemax/p/12311520.html

redis 命令讲解：

setex()命令：

SETEX key seconds value

将值 value 关联到 key ，并将 key 的生存时间设为 seconds (以秒为单位)。

如果 key 已经存在， SETEX 命令将覆写旧值。

这个命令类似于以下两个命令：

1 2	SET key value EXPIRE key seconds # 设置生存时间

不同之处是， SETEX 是一个原子性(atomic)操作，关联值和设置生存时间两个动作会在同一时间内完成，该命令在 Redis 用作缓存时，非常实用。

可用版本：>= 2.0.0
时间复杂度：$O(1)$
返回值：
- 设置成功时返回 OK 。
- 当 seconds 参数不合法时，返回一个错误。

setnx()命令：

SETNX key value

将 key 的值设为 value ，当且仅当 key 不存在。

若给定的 key 已经存在，则 SETNX 不做任何动作。

SETNX 是『SET if Not eXists』(如果不存在，则 SET)的简写。

可用版本：>= 1.0.0
时间复杂度：$O(1)$
返回值：
- 设置成功，返回 1 。
- 设置失败，返回 0 。

get()命令：

GET key

返回 key 所关联的字符串值。

如果 key 不存在那么返回特殊值 nil 。

假如 key 储存的值不是字符串类型，返回一个错误，因为 GET 只能用于处理字符串值。

可用版本：>= 1.0.0
时间复杂度：$O(1)$
返回值：
- 当 key 不存在时，返回 nil ，否则，返回 key 的值。
- 如果 key 不是字符串类型，那么返回一个错误。

getset()命令：

GETSET key value

将给定 key 的值设为 value ，并返回 key 的旧值(old value)。

当 key 存在但不是字符串类型时，返回一个错误。

可用版本：>= 1.0.0
时间复杂度：$O(1)$
返回值：
- 返回给定 key 的旧值。
- 当 key 没有旧值时，也即是， key 不存在时，返回 nil 。

具体的使用步骤如下：

setnx(lockkey, 当前时间+过期超时时间) ，如果返回 1，则获取锁成功；如果返回 0 则没有获取到锁，转向 2。
get(lockkey) 获取值 oldExpireTime ，并将这个 value 值与当前的系统时间进行比较，如果小于当前系统时间，则认为这个锁已经超时，可以允许别的请求重新获取，转向 3。
计算 newExpireTime=当前时间+过期超时时间，然后 getset(lockkey, newExpireTime) 会返回当前 lockkey 的值 currentExpireTime。
判断 currentExpireTime 与 oldExpireTime 是否相等，如果相等，说明当前 getset 设置成功，获取到了锁。如果不相等，说明这个锁又被别的请求获取走了，那么当前请求可以直接返回失败，或者继续重试。
在获取到锁之后，当前线程可以开始自己的业务处理，当处理完毕后，比较自己的处理时间和对于锁设置的超时时间，如果小于锁设置的超时时间，则直接执行 delete 释放锁；如果大于锁设置的超时时间，则不需要再锁进行处理。

BeanSearch.md

发表于 2020-06-29 分类于算法

使用一个模型来进行机器翻译时，并不是从得到的分布中进行随机取样，而是你要找到一个句子，使得条件概率最大化。

贪心搜索是一种来自计算机科学的算法，生成第一个词的分布以后，它将会根据你的条件语言模型挑选出最有可能的第一个词进入你的机器翻译模型中，在挑选出第一个词之后它将会继续挑选出最有可能的第二个词，然后继续挑选第三个最有可能的词，这种算法就叫做贪心搜索。这种方法得到的有可能是局部最优解，而不是全局最优解。

然而全排列所有组合，由于排列数量过于巨大，也没有可行性。

集束搜索（beam search）算法可以应用到寻找全局最优解上。

集束搜索（Beam Search）

贪婪算法只会挑出最可能的那一个单词，然后继续。而集束搜索则会考虑多个选择，集束搜索算法会有一个参数 B，叫做集束宽（beam width）。例如：把这个集束宽设成 3，这样就意味着集束搜索不会只考虑一个可能结果，而是一次会考虑 3 个。

Beam Search 改进

概率公式可表示为：$P(y^{<1>}|X)$ $P(y^{< 2 >}|X,y^{< 1 >})$ $P(y^{< 3 >}|X,y^{< 1 >},y^{< 2>})$…$P(y^{< T_{y} >}|X,y^{<1 >},y^{<2 >}\ldots y^{< T_{y} - 1 >})$。

这些概率值都是小于 1 的，通常远小于 1。很多小于 1 的数乘起来，会得到很小很小的数字，会造成数值下溢（numerical underflow）。数值下溢就是数值太小了，导致电脑的浮点表示不能精确地储存，因此在实践中,我们不会最大化这个乘积，而是取 $log$ 值。如果在这加上一个 $log$，最大化这个 $log$ 求和的概率值，在选择最可能的句子 $y$ 时，你会得到同样的结果。

如果参照原来的目标函数（this original objective），如果有一个很长的句子，那么这个句子的概率会很低，因为乘了很多项小于 1 的数字来估计句子的概率。所以如果乘起来很多小于 1 的数字，那么就会得到一个更小的概率值，所以这个目标函数有一个缺点，它可能不自然地倾向于简短的翻译结果，它更偏向短的输出，因为短句子的概率是由更少数量的小于 1 的数字乘积得到的，所以这个乘积不会那么小。顺便说一下，这里也有同样的问题，概率的 $log$ 值通常小于等于 1，实际上在 $log$ 的这个范围内，所以加起来的项越多，得到的结果越负，所以对这个算法另一个改变也可以使它表现的更好，也就是我们不再最大化这个目标函数了，我们可以把它归一化，通过除以翻译结果的单词数量（normalize this by the number of words in your translation）。这样就是取每个单词的概率对数值的平均了，这样很明显地减少了对输出长的结果的惩罚（**this significantly reduces the penalty for outputting longer translations.**）。

在实践中，有个探索性的方法，相比于直接除 $T_{y}$，也就是输出句子的单词总数，我们有时会用一个更柔和的方法（a softer approach），在 $T_{y}$ 上加上指数 $a$，$a$ 可以等于 0.7。如果 $a$ 等于 1，就相当于完全用长度来归一化，如果 $a$ 等于 0，$T_{y}$ 的 0 次幂就是 1，就相当于完全没有归一化，这就是在完全归一化和没有归一化之间。$a$ 就是算法另一个超参数（hyper parameter），需要调整大小来得到最好的结果。