为什么Redis这么快

原文翻译自 https://programming.vip/docs/why-is-redis-so-fast.html

redis-benchmark -t set,lpush -n 100000 -q
SET: 38550.50 requests per second  //Processing 38000 set requests per second
LPUSH: 37821.48 requests per second //Process 37000 lpush requests per second
### Script execution times
redis-benchmark -n 100000 -q script load"redis.call('set','foo','bar')"
script loadredis.call('set','foo','bar'): 37050.76 requests per second

水平轴：连接数；垂直轴：qps

根据官方数据，Redis的QPS可以达到100000(每秒请求)。

为什么Redis这么快？

1. Pure memory structure
2. Single thread

3. Multiplexing

   memory

   KV结构内存数据库，时间复杂度O(1)。

   Single thread

   单线程有什么好处？

4. 没有线程创建或线程销毁所导致的消耗。

5. 避免上下文切换导致的CPU消耗。
6. 它避免了线程之间的竞争问题，如添加锁、释放锁、死锁等。

   异步非阻塞

   异步非阻塞I/O，复用处理并发连接

   为什么Redis是单线程的？

   使用单个线程不是浪费CPU资源吗？

   https://redis.io/topics/faq

   因为单线程已经足够了，CPU并不是Redis的瓶颈。Redis最有可能的瓶颈是机器内存或网络带宽。由于单线程易于实现，CPU不会成为瓶颈，所以采用单线程解决方案是很自然的。

   为什么单线程速度这么快？

   因为Redis是一个基于内存的操作，所以让我们从内存开始。

   虚拟内存(虚拟内存)

   主存：内存；辅助内存：磁盘(硬盘)
   计算机的主内存可以看作是M个连续字节大小单元的数组。每个字节都有一个唯一的地址，称为物理地址(PA)。在早期的计算机中，如果CPU需要内存，则使用物理寻址直接访问主存。
   
   这种方法有几个缺点：
   1.在多用户多任务操作系统中，所有进程共享内存。如果每个进程占用一个物理地址空间，主内存将很快耗尽。我们希望在不同的时间，不同的进程能够共享相同的物理地址空间。
   2.如果所有进程直接访问物理内存，则一个进程可以修改其他进程的内存数据，导致物理地址空间受损，程序将异常运行。
   为了解决这些问题，我们在CPU和内存之间添加了一个中间层。CPU不再使用物理地址进行访问，而是访问虚拟地址。该中间层将地址转换为物理地址，并最终获得数据。这个中间层称为虚拟内存。
   
   当每个进程开始创建时，它将分配一个虚拟地址，然后通过虚拟地址和物理地址的映射获得真实数据，这样进程就不会直接联系物理地址，甚至不知道它调用哪个物理地址数据。
   目前，大多数操作系统都使用虚拟内存，如Windows系统的虚拟内存、Linux系统的交换空间等。Windows虚拟内存(pagefile.sys)是磁盘空间的一部分。
   在32位系统中，虚拟地址空间大小为2^32位=4G。64位系统的最大虚拟地址空间大小是多少？是2^64位=1024*1014 TB=1024 PB=16 EB吗？事实上，64位是不使用的，因为它不使用这么大的空间，而且它会造成大量的系统开销。Linux通常使用较低的48位来表示虚拟地址空间，即2^48位=256 T。

   cat /proc/cpuinfo

   地址大小：40位物理，48位虚拟
   实际物理内存可能比虚拟内存的大小小得多。
   结论：虚拟内存的引入可以提供更大的地址空间，地址空间是连续的，便于编程和链接。此外，物理内存可以隔离，不同的进程操作不相互影响。还可以通过将相同的物理内存块映射到不同的虚拟地址空间来实现内存共享。

   用户空间与核空间

   为了避免用户进程直接操作内核，保证内核安全，操作系统将虚拟内存分为内核空间/ˈkernl/和用户空间两部分。
   
   内核是操作系统的核心。它独立于普通的应用程序，可以访问受保护的内存空间以及底层的硬件设备。
   内核空间存储内核代码和数据，而进程用户空间存储用户程序代码和数据。无论是内核空间还是用户空间，都是在虚拟空间中，它们都是物理地址的映射。
   当进程在内核空间中运行时，它处于内核状态，而当进程在用户空间中运行时，它处于用户状态。
   进程可以在内核空间执行任意命令并调用系统的所有资源；在用户空间，它只能执行简单的操作，不能直接调用系统资源，只有通过系统接口(也称为系统调用)才能向内核发送指令。

   top命令：

   
   用户表示用户空间中CPU时间的百分比，sys表示内核空间中CPU时间的百分比；

   进程切换(上下文切换)

   多任务操作系统如何实现运行的任务数量远远超过CPU的数量？当然，这些任务并不是同时运行的，而是因为系统通过时间切片算法在短时间内依次将CPU分配给它们，从而产生了多任务同时运行的错觉。
   
   为了控制进程的执行，内核必须能够挂起在CPU上运行的进程并继续执行先前挂起的进程。这种行为称为进程切换。

   context是什么？

   在每个任务运行之前，CPU需要知道任务在哪里加载并开始运行。也就是说，系统需要帮助预先设置CPU寄存器和程序计数器，这称为CPU上下文。
   这些保存的上下文存储在系统内核中，并在重新调度任务时再次加载。这样，任务的原始状态就不会受到影响，并且任务看起来会持续运行。
   在切换上下文时，我们需要完成一系列的工作，这是一个非常耗费资源的操作。

   过程阻塞

   由于正在运行的进程发出了系统服务请求(如I/O操作)，但由于某些原因，它无法从操作系统获得即时响应，因此进程只能将自身变为阻塞状态，等待相应事件在唤醒之前出现。进程不会在阻塞状态下消耗CPU资源。

   文件描述符FD

   Linux系统将所有设备视为文件，Linux使用文件描述符来标识每个文件对象。
   文件描述符是内核为有效管理打开的文件而创建的索引。它用于指向打开的文件。执行I/O操作的所有系统调用都通过文件描述符。文件描述符是一个简单的非负整数，用于指示进程打开的每个文件。
   Linux系统中有三个标准的文件描述符。
   0：标准输入(键盘)；1：标准输出(显示)；2：标准错误输出(显示)。

   传统I/O数据拷贝

   当应用程序执行读取系统调用来读取文件描述符(FD)时，如果数据已经存在于用户进程的页存储器中，它将直接从存储器中读取数据。如果数据不存在，将数据从磁盘加载到内核缓冲区，然后将数据从内核缓冲区复制到用户进程的页内存中。(两个副本，两个上下文在用户和内核之间切换)。
   

   阻塞I/O(I/O的阻塞在哪里？)

   当读或写用于读取或写入文件描述符时，如果当前FD不可读，则系统将不会响应其他操作。阻止将数据从设备复制到内核缓冲区。还阻止将数据从内核缓冲区复制到用户空间。在复制完成和内核返回结果之前，用户进程将不会释放块。
   
   为了解决阻塞问题，我们有几个想法。
   1.在服务器端创建多个线程或使用线程池，但在并发性高的情况下，将需要许多线程，系统无法承受，线程的创建和释放需要消耗资源。
   2.请求者定期轮询，并在准备数据后将数据从内核缓存缓冲区复制到用户空间(无阻塞I/O)。这样会有一些延误。

   I/O复用

   I/O指网络I/O。
   多路复用：指多个TCP连接(套接字或通道)。
   重用：指重用一个或多个线程。
   它的基本原理是，内核不监视应用程序本身的连接，而是监视应用程序的文件描述符。
   当客户端操作时，它将生成具有不同事件类型的套接字。在服务器端，I/O复用程序(I/O复用模块)将消息放入队列，然后通过文件事件调度器将消息转发给不同的事件处理器。
   
   有许多多路复用的实现。例如，当用户进程调用复用器时，进程将被阻塞。内核将监视复用器负责的所有套接字。当任何插座的数据准备就绪后，复用器将返回。此时，用户进程调用Read操作将数据从内核缓冲区复制到用户空间。
   
   因此，I/O复用的特点是进程可以通过一种机制同时等待多个文件描述符，而这些文件描述符(套接字描述符)中的任何一个都进入可读状态，SELECT()函数可以返回。
   Redis的多路复用提供了几个选项，例如SELECT、EPOLL、evport和kQueue。编译时可以选择一个。源代码ae.c

   /* Include the best multiplexing layer supported by this system.
   * The following should be ordered by performances, descending. */
   #ifdef HAVE_EVPORT
   #include "ae_evport.c"
   #else
    #ifdef HAVE_EPOLL
    #include "ae_epoll.c"
    #else
        #ifdef HAVE_KQUEUE
        #include "ae_kqueue.c"
        #else
        #include "ae_select.c"
        #endif
    #endif
   #endif

• 该系统由Solaris内核支持；
• Linux内核支持EPOLL；
• KQueue是由Mac系统支持的；
• SELECT由POSIX提供，一般操作系统有支持(最低保障方案)；

源代码：AE_epll。C，ae_select.c，ae_kQuee.c，ae_evport.c

内存恢复

Reids的所有数据都存储在内存中。在某些情况下，需要回收占用的内存空间。内存恢复主要有两种类型：一种是密钥过期，另一种是内存使用量达到最大值(最大值？(内存)触发内存过时。

到期政策

为了达到关键期限，我们有几个想法。

1. 时间过期(主动消除)

每个键设置过期时间都需要创建一个计时器，该计时器将在过期时间后立即清除。这种策略可以立即清除过期的数据，这是非常内存友好的，但是它会消耗大量的CPU资源来处理过期的数据，从而影响缓存的响应时间和吞吐量。

1. 惯性失效(被动消除)

只有当密钥被访问时，才能判断密钥是否过期。如果它过期了，它就会被清除。这种策略可以尽可能地节省CPU资源，但对内存不太友好。在极端情况下，大量过期密钥可能不会再次被访问，因此它们将不会被清除并占用大量内存。
例如，字符串将调用getCommand中的expireifred
Db.c expireIfNered(redisDbdb，robjkey)

/* This function is called when we are going to perform some operation
 * in a given key, but such key may be already logically expired even if
 * it still exists in the database. The main way this function is called
 * is via lookupKey*() family of functions.
 *
 * The behavior of the function depends on the replication role of the
 * instance, because slave instances do not expire keys, they wait
 * for DELs from the master for consistency matters. However even
 * slaves will try to have a coherent return value for the function,
 * so that read commands executed in the slave side will be able to
 * behave like if the key is expired even if still present (because the
 * master has yet to propagate the DEL).
 *
 * In masters as a side effect of finding a key which is expired, such
 * key will be evicted from the database. Also this may trigger the
 * propagation of a DEL/UNLINK command in AOF / replication stream.
 *
 * The return value of the function is 0 if the key is still valid,
 * otherwise the function returns 1 if the key is expired. */
int expireIfNeeded(redisDb *db, robj *key) {
    if (!keyIsExpired(db,key)) return 0;
    /* If we are running in the context of a slave, instead of
     * evicting the expired key from the database, we return ASAP:
     * the slave key expiration is controlled by the master that will
     * send us synthesized DEL operations for expired keys.
     *
     * Still we try to return the right information to the caller,
     * that is, 0 if we think the key should be still valid, 1 if
     * we think the key is expired at this time. */
    if (server.masterhost != NULL) return 1;
    /* Delete the key */
    server.stat_expiredkeys++;
    propagateExpire(db,key,server.lazyfree_lazy_expire);
    notifyKeyspaceEvent(NOTIFY_EXPIRED,
        "expired",key,db->id);
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}

在第二种情况下，每次写入键时，都会发现内存不足。调用活动呼气循环释放一些记忆。
Exire.c活动实例循环(Inttype)

/* Try to expire a few timed out keys. The algorithm used is adaptive and
 * will use few CPU cycles if there are few expiring keys, otherwise
 * it will get more aggressive to avoid that too much memory is used by
 * keys that can be removed from the keyspace.
 *
 * No more than CRON_DBS_PER_CALL databases are tested at every
 * iteration.
 *
 * This kind of call is used when Redis detects that timelimit_exit is
 * true, so there is more work to do, and we do it more incrementally from
 * the beforeSleep() function of the event loop.
 *
 * Expire cycle type:
 *
 * If type is ACTIVE_EXPIRE_CYCLE_FAST the function will try to run a
 * "fast" expire cycle that takes no longer than EXPIRE_FAST_CYCLE_DURATION
 * microseconds, and is not repeated again before the same amount of time.
 *
 * If type is ACTIVE_EXPIRE_CYCLE_SLOW, that normal expire cycle is
 * executed, where the time limit is a percentage of the REDIS_HZ period
 * as specified by the ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC define. */
void activeExpireCycle(int type) {
    /* This function has some global state in order to continue the work
     * incrementally across calls. */
    static unsigned int current_db = 0; /* Last DB tested. */
    static int timelimit_exit = 0;      /* Time limit hit in previous call? */
    static long long last_fast_cycle = 0; /* When last fast cycle ran. */
    int j, iteration = 0;
    int dbs_per_call = CRON_DBS_PER_CALL;
    long long start = ustime(), timelimit, elapsed;
    /* When clients are paused the dataset should be static not just from the
     * POV of clients not being able to write, but also from the POV of
     * expires and evictions of keys not being performed. */
    if (clientsArePaused()) return;
    if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
        /* Don't start a fast cycle if the previous cycle did not exit
         * for time limit. Also don't repeat a fast cycle for the same period
         * as the fast cycle total duration itself. */
        if (!timelimit_exit) return;
        if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
        last_fast_cycle = start;
    }
    /* We usually should test CRON_DBS_PER_CALL per iteration, with
     * two exceptions:
     *
     * 1) Don't test more DBs than we have.
     * 2) If last time we hit the time limit, we want to scan all DBs
     * in this iteration, as there is work to do in some DB and we don't want
     * expired keys to use memory for too much time. */
    if (dbs_per_call > server.dbnum || timelimit_exit)
        dbs_per_call = server.dbnum;
    /* We can use at max ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC percentage of CPU time
     * per iteration. Since this function gets called with a frequency of
     * server.hz times per second, the following is the max amount of
     * microseconds we can spend in this function. */
    timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
    timelimit_exit = 0;
    if (timelimit <= 0) timelimit = 1;
    if (type == ACTIVE_EXPIRE_CYCLE_FAST)
        timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION; /* in microseconds. */
    /* Accumulate some global stats as we expire keys, to have some idea
     * about the number of keys that are already logically expired, but still
     * existing inside the database. */
    long total_sampled = 0;
    long total_expired = 0;
    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        int expired;
        redisDb *db = server.db+(current_db % server.dbnum);
        /* Increment the DB now so we are sure if we run out of time
         * in the current DB we'll restart from the next. This allows to
         * distribute the time evenly across DBs. */
        current_db++;
        /* Continue to expire if at the end of the cycle more than 25%
         * of the keys were expired. */
        do {
            unsigned long num, slots;
            long long now, ttl_sum;
            int ttl_samples;
            iteration++;
            /* If there is nothing to expire try next DB ASAP. */
            if ((num = dictSize(db->expires)) == 0) {
                db->avg_ttl = 0;
                break;
            }
            slots = dictSlots(db->expires);
            now = mstime();
            /* When there are less than 1% filled slots getting random
             * keys is expensive, so stop here waiting for better times...
             * The dictionary will be resized asap. */
            if (num && slots > DICT_HT_INITIAL_SIZE &&
                (num*100/slots < 1)) break;
            /* The main collection cycle. Sample random keys among keys
             * with an expire set, checking for expired ones. */
            expired = 0;
            ttl_sum = 0;
            ttl_samples = 0;
            if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
                num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
            while (num--) {
                dictEntry *de;
                long long ttl;
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;
                ttl = dictGetSignedIntegerVal(de)-now;
                if (activeExpireCycleTryExpire(db,de,now)) expired++;
                if (ttl > 0) {
                    /* We want the average TTL of keys yet not expired. */
                    ttl_sum += ttl;
                    ttl_samples++;
                }
                total_sampled++;
            }
            total_expired += expired;
            /* Update the average TTL stats for this database. */
            if (ttl_samples) {
                long long avg_ttl = ttl_sum/ttl_samples;
                /* Do a simple running average with a few samples.
                 * We just use the current estimate with a weight of 2%
                 * and the previous estimate with a weight of 98%. */
                if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
                db->avg_ttl = (db->avg_ttl/50)*49 + (avg_ttl/50);
            }
            /* We can't block forever here even if there are many keys to
             * expire. So after a given amount of milliseconds return to the
             * caller waiting for the other active expire cycle. */
            if ((iteration & 0xf) == 0) { /* check once every 16 iterations. */
                elapsed = ustime()-start;
                if (elapsed > timelimit) {
                    timelimit_exit = 1;
                    server.stat_expired_time_cap_reached_count++;
                    break;
                }
            }
            /* We don't repeat the cycle if there are less than 25% of keys
             * found expired in the current DB. */
        } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
    }
    elapsed = ustime()-start;
    latencyAddSampleIfNeeded("expire-cycle",elapsed/1000);
    /* Update our estimate of keys existing but yet to be expired.
     * Running average with this sample accounting for 5%. */
    double current_perc;
    if (total_sampled) {
        current_perc = (double)total_expired/total_sampled;
    } else
        current_perc = 0;
    server.stat_expired_stale_perc = (current_perc*0.05)+
                                     (server.stat_expired_stale_perc*0.95);
}

1. 源代码：server.h

   /* Redis database representation. There are multiple databases identified
   * by integers from 0 (the default database) up to the max configured
   * database. The database number is the 'id' field in the structure. */
   typedef struct redisDb {
    dict *dict;                 /* All health values are right */
    dict *expires;              /* Key value pair with expiration time set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
   } redisDb;

   在一定时间间隔内，一定数量的特定数量的数据库字典中的密钥将被扫描，过期的密钥将被清除。这一策略是前两者之间的妥协。通过调整每次扫描的时间间隔和有限的时间，CPU和内存资源可以在不同的情况下达到最佳的平衡效果。
   在Redis中，同时使用两种过期策略，延迟过期和定期过期。

   如果它没有过期，那么如果Redis充满了记忆呢？

   在不影响读取的情况下写入提示OOM错误信息。

   消除策略

   Redis的内存消除策略是指当内存使用量达到最大内存极限时，需要使用消除算法来确定哪些数据被清除，以保证新数据的存储。
   Redis.conf
   #maxMemory-策略删除

   #volatile-lru -> EvictusingapproximatedLRUamongthekeyswithanexpireset.
   #allkeys-lru -> EvictanykeyusingapproximatedLRU.
   #volatile-lfu -> EvictusingapproximatedLFUamongthekeyswithanexpireset.
   #allkeys-lfu -> EvictanykeyusingapproximatedLFU.
   #volatile-random -> Removearandomkeyamongtheoneswithanexpireset.
   #allkeys-random -> Removearandomkey,anykey.
   #volatile-ttl -> Removethekeywiththenearestexpiretime(minorTTL)
   #noeviction -> Don'tevictanything,justreturnanerroronwriteoperations.

   LRU，最近用得最少。判断最近使用的时间，并优先排除目前最远的数据。
   LFU，使用最少，在4.0版中添加。

如果没有消除满足先决条件的密钥，则易失性LRU、易失性随机和易失性TTL等效于不逐出。
建议在正常服务情况下使用易失性LRU删除最近使用最少的密钥。

在传统LRU算法的基础上实现RedisLRU有哪些问题？

需要额外的数据结构存储，这将消耗内存。
RedisLRU改进了传统的LRU算法，并通过随机抽样调整算法的精度。
如果消除策略是LRU，则根据配置的采样值maxMemory“Sample(默认值为5)从数据库中随机选择m个密钥，并以最低的热量消除与密钥对应的缓存数据，因此，采样参数m的值越大，就可以找到更精确的要删除的缓存数据，但也消耗了更多的CPU计算，降低了执行效率。

如何找到最低热度数据？

Redis中的所有对象结构都有一个lru字段，它使用较低的24位无符号来记录对象的热度。创建对象时记录LRU值。当被访问时，LRU值也会被更新。但是没有获得系统的当前时间戳，而是将其设置为全局变量server.lruclock的值。
源代码：server.h

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

Server.lruclock的值是如何产生的？

Redis有一个用于定时处理的函数serverCron。默认情况下，函数updateCachedTime每100 ms调用一次，以更新全局变量的server.lruclock的值。它记录当前Unix时间戳。
源代码：server.c

/* We take a cached value of the unix time in the global state because with
 * virtual memory and aging there is to store the current time in objects at
 * every object access, and accuracy is not needed. To access a global var is
 * a lot faster than calling time(NULL) */
void updateCachedTime(void) {
    time_t unixtime = time(NULL);
    atomicSet(server.unixtime,unixtime);
    server.mstime = mstime();
    /* To get information about daylight saving time, we need to call localtime_r
     * and cache the result. However calling localtime_r in this context is safe
     * since we will never fork() while here, in the main thread. The logging
     * function will call a thread safe version of localtime that has no locks. */
    struct tm tm;
    localtime_r(&server.unixtime,&tm);
    server.daylight_active = tm.tm_isdst;
}

为什么不找出确切的时间并把它放在全局变量中呢？不会耽搁吗？

这样，当在函数lookupKey中更新数据的lru热值时，系统的功能时间不再每次调用，可以提高执行效率。
好的，当对象中有LRU字段值时，您可以计算对象的热度。
函数估计ObjectIdleTime计算指定对象的lru热。其思想是，对象的lru值与全局server.lruclock之间的差异越大(不更新的时间越长)，对象的热度就越低。
来源驱逐.c

/* Given an object returns the min number of milliseconds the object was never
 * requested, using an approximated LRU algorithm. */
unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
    } else {
        return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
                    LRU_CLOCK_RESOLUTION;
    }
}

Lruclock只有24位，可以在几秒钟内存储194天。当它超过24位所能表达的最大时间时，它将从零开始。
Server.h

#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */

在这种情况下，对象的lru可能大于server.lruclock。如果发生这种情况，将添加两个键，而不是减去两个键，以找到最长的键。
为什么不使用传统的哈希表+双向链接列表？需要额外的数据结构，消耗资源。当样本为10时，RedisLRU算法已经可以接近传统的LRU算法。

除了消耗资源外，传统的LRU还有什么问题？

如图所示，假设A在10秒内被访问五次，而B在10秒内被访问三次。因为B最后一次被访问比A晚，在同样的情况下，A首先被回收。

LFU

Server.h

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

当使用这24位作为LFU时，它们被分成两部分：

• 上面的16位用来记录访问时间(以分钟、LDT、最后递减时间为单位)。
• 较低的8位用来记录访问频率，称为计数器(log C，逻辑计数器)。

计数器采用基于概率的对数计数器实现，8位可以代表数百万的访问频率。
在读取和写入对象时，更新LFU值。Db.c-查找键

/* Update LFU when an object is accessed.
 * Firstly, decrement the counter if the decrement time is reached.
 * Then logarithmically increment the counter, and update the access time. */
void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);
    counter = LFULogIncr(counter);
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

生长速率取决于lfu对数系数越大，计数器生长越慢。

redis.conf configuration file
#lfu-log-factor10

如果计数器只增加，它就不会减少，也不会反映物体的热量。当未被访问时，计数器如何减少？
衰减值由衰减因子LFU甲板时间(分钟)控制。如果值为1，则如果没有访问权限，则N分钟将减少。

#lfu-decay-time 1

2020年节目VIP