西安专业做网站建,室内设计最好的公司,网络设计与实施一般包括哪几个阶段,wordpress后台左侧菜单文章目录 过期删除策略和内存淘汰策略内存淘汰策略evictionPoolEntryevictionPoolPopulate Reservoir SamplingdictGetRandomKeydictGetSomeKeysReservoir Samplingchatgpt对Reservoir Sampling的介绍 过期删除策略和内存淘汰策略
详细介绍请参考博客“redis过期删除策略和内存… 文章目录 过期删除策略和内存淘汰策略内存淘汰策略evictionPoolEntryevictionPoolPopulate Reservoir SamplingdictGetRandomKeydictGetSomeKeysReservoir Samplingchatgpt对Reservoir Sampling的介绍 过期删除策略和内存淘汰策略
详细介绍请参考博客“redis过期删除策略和内存淘汰策略”
内存淘汰策略
为了节省内存redis并没有采用传统的方法实现LRU和LFU而是基于随机采样的方式近似实现LRU和LFU并引入淘汰池进行优化。接下来详细看看是如何淘汰池进行优化的。具体实现在evict.c文件中的函数evictionPoolPopulate。
/* This is a helper function for performEvictions(), it is used in order* to populate the evictionPool with a few entries every time we want to* expire a key. Keys with idle time bigger than one of the current* keys are added. Keys are always added if there are free entries.** We insert keys on place in ascending order, so keys with the smaller* idle time are on the left, and keys with the higher idle time on the* right. */这个函数是performEvictions()的辅助函数。每当想要过期一些key时该函数被用来向淘汰池填充一些数据。当淘汰池未满时keys总是被添加反之的话添加具有更大idle time的keys。淘汰池按照idle time升序排序即较小idle time的key存储在淘汰池的左边较大idle time的key存储在淘汰池的右边。/* When an LFU policy is used instead, a reverse frequency indication is used* instead of the idle time, so that we still evict by larger value (larger* inverse frequency means to evict keys with the least frequent accesses).*/当使用LFU策略时用反向频率reverse frequency代替idle time。按照reverse frequency升序排序较大的inverse frequency意味着keys具有较小的lfu值即least frequent accesses。evictionPoolEntry evictionPoolPopulate Reservoir Sampling
count dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);接下来看一下随机采样的逻辑。
dictGetRandomKey
首先看一下随即采取一个dictEntry的逻辑
/* Return a random entry from the hash table. Useful to* implement randomized algorithms */
从hash table中返回一个随机entry。用来实现随机算法。从代码中可以看出在进行随机采样一个dictEntry时会判断dict当前是否处于rehashing阶段如果是的话就进行迁移操作 在redis7.2.2|Dict这篇文章中已经介绍过dict何时会发生rehashing
dictGetSomeKeys
接下来看一下随机采取多个dictEntry的逻辑。
/* This function samples the dictionary to return a few keys from random* locations.** It does not guarantee to return all the keys specified in count, nor* it does guarantee to return non-duplicated elements, however it will make* some effort to do both things.** Returned pointers to hash table entries are stored into des that* points to an array of dictEntry pointers. The array must have room for* at least count elements, that is the argument we pass to the function* to tell how many random elements we need.** The function returns the number of items stored into des, that may* be less than count if the hash table has less than count elements* inside, or if not enough elements were found in a reasonable amount of* steps.** Note that this function is not suitable when you need a good distribution* of the returned items, but only when you need to sample a given number* of continuous elements to run some kind of algorithm or to produce* statistics. However the function is much faster than dictGetRandomKey()* at producing N elements. */
这个函数对字典进行采样从随机位置返回几个键。
它不保证返回count中指定的所有键也不保证返回不重复的元素但是它会努力做到这两件事。
返回的指向哈希表项的指针存储在指向dictEntry指针数组的des中。
数组必须至少有容纳count元素的空间这是我们传递给函数的参数用于告诉我们需要多少个随机元素。
该函数返回存储在des中的项数如果哈希表中包含的元素少于count或者在合理的步骤中没有找到足够的元素则可能小于count。
请注意当您需要返回项的良好分布时此函数不适用而只适用于需要“抽样”给定数量的连续元素以运行某种算法或生成统计数据时。
然而在生成N个元素时该函数比dictGetRandomKey()快得多。在生成N个元素时该函数比dictGetRandomKey()快得多。
从代码中可以看出在进行随机采样一个dictEntry时会判断dict当前是否处于rehashing阶段如果是的话就进行迁移操作 在redis7.2.2|Dict这篇文章中已经介绍过dict何时会发生rehashing
通过研究代码发现在生成N个元素时函数dictGetSomeKeys确实要比函数dictGetRandomKey快得多。因为对于dictGetSomeKeys函数来说只需要确定一个bucket然后沿着list取样即可。但是对于dictGetRandomKey函数每生成一个元素都需要随机找到一个bucket并且还需要计算list的长度并且找到其中一个随机位置。
Reservoir Sampling
/* Collect all the elements of the buckets found non empty while iterating
* To avoid the issue of being unable to sample the end of a long chain,
* we utilize the Reservoir Sampling algorithm to optimize the sampling process.
* This means that even when the maximum number of samples has been reached,
* we continue sampling until we reach the end of the chain.
* See https://en.wikipedia.org/wiki/Reservoir_sampling. */
为了避免在长链末端无法采样的问题我们采用了Reservoir Sampling算法来优化采样过程。
这意味着即使达到了最大样本数我们也会继续采样直到到达链的末端。有关“Reservior Sampling”的详细介绍见https://en.wikipedia.org/wiki/Reservoir_sampling。
chatgpt对Reservoir Sampling的介绍
水库采样法Reservoir Sampling是一种在处理大规模数据流或未知大小的数据集合时用于从中随机抽取固定数量样本的算法。它特别适用于数据流场景因为在数据流开始之前并不知道其总量。 核心思想 水库采样的核心思想是在处理一个可能无限大的数据流时从中抽取固定数量的样本使得每个数据元素被选中的概率是相同的。 操作步骤 假设我们要从数据流中随机抽取k个元素具体步骤如下
初始化创建一个大小为k的“水库”数组并将前k个元素直接存入水库。替换阶段 对于每一个新的元素假设这是第n个元素生成一个随机数r该随机数的范围是[0, n-1]。如果r的值小于k则用这个新元素替换水库中的第r个元素。如果r的值大于等于k则忽略这个元素。
举例说明 假设你有一个数据流其中包含1000个元素你想从中随机抽取10个样本。你会按以下步骤进行
将前10个元素直接放入水库。对第11个元素生成一个随机数r范围是[0, 10]。如果r的值在0到9之间则用第11个元素替换水库中对应位置的元素。如果r等于10则忽略这个元素。重复上述步骤直到处理完所有的1000个元素。
优势
空间效率高只需要存储k个元素的水库不论数据流的大小如何这使得水库采样在内存限制的环境中特别有用。公平性保证了在最终的k个样本中数据流中的每个元素被选中的概率是相同的。
应用场景
在线广告系统随机抽取用户的行为数据用于后续分析。流媒体处理在数据流不断到来的情况下实时生成随机样本。
水库采样是一种简单而有效的算法特别适用于在处理大规模数据时确保样本具有代表性。
