第一部分 數據結構與對象

[toc]

1. 簡單動態(tài)字符串

? Redis自己構建了一種名為簡單動態(tài)字符串(SDS)的抽象類型,并將其作為Redis的默認字符串表示.在Redis中,包含字符串值的鍵值對在底層都是SDS實現的.C字符串只會作為字面量使用.

(1). SDS的定義

struct sdshdr{
    // 記錄出發(fā)數組中已經使用了的字符數量
    // 也就是sds所保存的字符串的長度
    int len;
    
    // 記錄空閑空間的數量
    int free;
    
    // 字節(jié)數組,存儲字符數據
    char buf[];
}

? SDS遵循C字符串以空字符('\0')結尾的慣例,目的是為了直接重用一部分C字符串庫函數.但是這個空字符是不計入len屬性中的.

(2). SDS和C字符串的區(qū)別

? C字符串并不能滿足Redis在安全性,效率以及功能方面的要求.

1). 獲取字符串長度

? SDS可以常數復雜度的獲取字符串的長度,因為數據結構中已經存儲了字符串的長度,不需要遍歷數組去求累計和.

2). 杜絕緩沖區(qū)溢出

? 在修改前會判斷空間是否足夠使用(free字段的值),而如果使用C字符串,需要先進行手動判斷,保證空間足夠.

? SDS API對SDS進行修改時,API會檢查SDS的空間是否滿足修改所需的要求.如果不足,則會自動進行擴容.

3). 減少修改字符串時帶來的內存充分配次數

? C字符串的底層總是空間大小剛好合適(n+1).這樣對字符串進行修改時,就經常會涉及到內存的重分配.SDS中保留了空閑空間,接觸了字符串長度和底層數組長度的關聯.

? 通過未使用空間,SDS實現了==空間預分配==和==惰性空間釋放==兩種優(yōu)化策略.

1>. 空間預分配

? 每次都額外分配內存,減少內存重新分配.優(yōu)化SDS的增長.

? 額外分配的內存等于所使用的內存,但不超過1 MB.

? 拓展SDS時會優(yōu)先使用空閑空間,如果空閑空間不足,才會重新分配內存.

2>. 惰性空間釋放

? 長度縮短時,不會立刻回收內存.優(yōu)化SDS縮短.

? SDS提供了相應API,可以手動的真正釋放SDS未使用的空間.從而不會造成內存浪費.

4). 二進制安全

? 不需要考慮'/0'的意義,那么就可以存儲二進制數據.

5). 兼容部分C字符串函數

2. 鏈表

Redis使用的C語言沒有內置鏈表的實現,所以Redis構建了自己的實現方式.

當list內存儲了較多的元素或者list中包含的元素都是較長的字符串時,Redis就會使用鏈表作為列表的底層實現.

鏈表的數據結構實現略過.

(1). 鏈表和鏈表節(jié)點的實現

// 鏈表節(jié)點的定義
typedef struct listNode{
    // 前繼節(jié)點
    struct listNode *prev;
    // 后繼節(jié)點
    struct listNode *prev;
    // 指向節(jié)點存儲的數據
    void *value;
}listNode;

// 鏈表的數據結構定義
typedef struct list{
    // 頭結點
    listNode *head;
    // 尾節(jié)點
    listNode *tail;
    // 鏈表長度
    unsigned long len;
    // 復制鏈表節(jié)點的函數
    void *(*dup)(void *ptr);
    // 釋放鏈表節(jié)點的函數
    void (*free)(void *ptr);
    // 節(jié)點值對比函數
    int (*match)(void *ptr, void *key);
}list;

void * 的用法相當于Java中的Object,可以保存所有類型的指針.

? list中存儲了鏈表的長度,所以可以O(1)時間復雜度獲取數據量.

3. 字典

字典在Redis中的應用非常廣泛,Redis中的數據庫就是使用字典作為底層實現的(從數據結構的key得到數據結構的對象).

字典還是哈希類型的底層實現之一,當一個哈希類型包含的鍵值對比較多,或者鍵值對中的元素都是比較成的字符串時,Redis就會使用字典作為哈希類型的底層實現.

(1). 字典的實現

1). 哈希表以及其節(jié)點的定義

? Redis字典所使用的哈希表的定義:

// 哈希表節(jié)點的定義
typedef struct dictEntry{
    // 鍵
    void *key;
    // 值(枚舉類型,分別存儲結構體類型,無符號數和有符號數)
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下一個節(jié)點
    struct dictEntry *next;
}dictEntry;

// 哈希表整體數據結構的定義
typedef struct dictht{
    // 節(jié)點數組(第一個星號表示數組,第二個表示數組中存儲的是指向字節(jié)節(jié)點的指針)
    dictEntry **table;
    // 哈希表的大小
    unsigned long size;
    // 哈希表大小減一,用于方便計算索引值(散列)
    unsigned long sizemask;
    // 已占用的空間數
    unsigned long used;
}

? 從以上定義可以看出,Redis中哈希表的底層和Java中HashMap的底層數據結構定義是一樣的,都是使用數組+鏈表存儲數據,使用鏈地址法(拉鏈法)解決哈希沖突.

2). 字典

? Redis中的字典的數據結構定義:

// 這個結構體中定義了一些操縱特定類型鍵值對的函數,Redis會為不同用途的字典設置不用的函數
// 是為了創(chuàng)建多態(tài)字典使用的
typedef struct dictType{
    // 計算哈希值的函數
    unsigned int (*hashFunction)(const void *key);
    // 復制鍵
    void *(*keyDup)(void *privdata, const void *key);
    // 復制值
    void *(*valDup)(void *privdata, const void *obj);
    // 對比鍵
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 銷毀鍵
    void (*keyDestructor)(void *privadata, void *key);
    // 銷毀值
    void (*valDestructor)(void *privadata, void *obj);
}
// 這個是字典的結構體定義
typedef struct dict{
    // 這個字典使用的方法
    dictType *type;
    // 私有數據
    void *privdata;
    // 每一個字典都會使用兩個哈希表,ht[1]的哈希表只會在ht[0]的哈希表rehash時才會使用
    dictht ht[2];
    // rehash索引,當rehash不再進行時,為-1(相當于狀態(tài)量,根據這個狀態(tài)量判斷從ht[0]或者ht[1]中取出數據)
    int rehashidx;
}

(2). 哈希算法

? 當要插入鍵值對時,先要根據插入的鍵計算出哈希值,然后根據這個哈希值散列到哈希表節(jié)點的數組中.

// 每一個字典使用的哈希方法可能是不一樣的
hash = dict->type->hashFunction(key);
// 得到哈希值之后,對哈希值和數組長度減一按位與得到數組中的下標
index = hash & dict->ht[x].sizemask;

(3). 解決鍵沖突

? Redis中的哈希表使用鏈地址法解決哈希沖突.

? 因為dictEntry中的鏈表是單向鏈表,所以新節(jié)點會使用頭插法進入鏈表.

(4). rehash

Redis中哈希表的rehash機制:

? 二倍對ht[1]擴容(這里保證了容量為2^n,在hash的時候使用了按位與)

? rehash時全部重新hash到另外一張表中

? 釋放原表,然后將新表設置為ht[0],并在ht[1]處創(chuàng)建空白表(這里的空白是指沒有初始化數組,但是有其他部分數據)

哈希表的擴容和收縮:

當滿足以下條件時,程序自動進行哈希表的擴容:

1. 服務器沒有在執(zhí)行BGSAVE或者BGREWRITEAOF命令(后臺線程持久化數據),并且哈希表的負載因子大于1(負載因子: 元素數 / 桶數量)
2. 服務器正在進行后臺線程持久化數據,并且負載因子大于5

另一方面,當負載因子小于0.1時,程序自動進行哈希表的收縮操作.caozuo

(5). 漸進式rehash

? rehash動作并不是一次性執(zhí)行完的,而是分多次,漸進式地完成的.(防止Redis短時間內被rehash占用cpu而停止服務)

? 這個過程是從哈希數組的0號位置向后進行的,rehashidx(rehash索引)表示當前進行到的位置,當rehashidx累加到數組長度時,漸進式rehash結束,設置為-1.

漸進式rehash期間對哈希表的操作:

? 在漸進式rehash進行時,字典會同時使用兩個哈希表,例如:如果要找一個鍵,會現在ht[0]上面尋找,如果沒能找到,再在ht[1]上尋找.

? 所有的新值一律會保存到ht[1]中,也就是新表中,保證ht[0]中的數據只減不增.,并且鎖著rehash的進行被全部復制到新表中,最后被清空.

4. 跳躍表

跳躍表是一種數據結構,通過在每個節(jié)點中維持多個指向其他節(jié)點的指針從而達到快速訪問節(jié)點的目的.

Redis采用跳躍表作為有序集和(zset)的底層實現之一,當zset包含的元素數量較多又或者zset中存儲的都是較長的字符串時,Redis就會使用跳躍表作為zset的底層實現.

同鏈表,字典等數據結構被廣泛的應用在Redis中不同,Redis內部只在zset和集群節(jié)點中使用到了跳躍表.

跳表──沒聽過但很犀利的數據結構

跳表內算法:跳躍表原理

(1). 跳躍表的定義

? 跳躍表是鏈表的進化版解決了鏈表查找元素時間復雜度常量階的缺點.常常用來代替平衡樹(實現更簡單,效率也不低).

? 跳表相當于在鏈表的節(jié)點中存儲了多個next指針,根據跳躍的維度不同加以區(qū)分,在內存表示中將步長(這里的步長并不是確定的,只能大致認為上層的步長比下層的要大)越大的指針放在上面,步長小的放在下面,如此就有了層的概念,如圖所示:

[圖片上傳失敗...(image-c171f1-1590395023188)]

? 查找時,先根據高層級指針向后尋找,如果找到的元素大于要尋找的元素,向回退一步,使用低一層的指針向后訪問.當步長為1并且還沒有找到時,就意味著整個表中都沒有這個元素.

(2). 跳躍表節(jié)點

? 跳躍表節(jié)點的數據結構定義:

typedef struct zskiplistNode {
    // 后退指針
    // 用于從后向前遍歷元素(從前向后只需要挨個訪問層級為0的前進指針即可)
    struct zskiplistNode *backward;
    // 該節(jié)點的分值,跳躍表中元素排列的依據,可以理解為跳躍表也是一個按照分值有序的鏈表
    // 當分值相等時,將存儲對象的大小作為排序的依據
    // 這應該是Redis中跳表實現獨有的
    double score;
    // 節(jié)點內存儲的對象
    robj *obj;
    // 節(jié)點處于各個層的層對象
    struct zskiplistLevel {
        // 前進指針
        struct zskiplistNode *forward;
        // 本次前進的跨度
        unsigned int span;
    } level[];
} zskiplistNode;

1). 層

? 每一個節(jié)點的層數是使用數組存儲的,就可以做到擴容.

? 每創(chuàng)建一個新鏈表節(jié)點時,程序都根據==冪次定律(越大的數,生成的概論越小)生成一個1~32的值作為level數組的大小==,這個大小就是這個節(jié)點最大的層的高度,也就是可以為訪問到的最高的層.

2). 前進指針

? 這個指針是每一個有獨立的,向后訪問時,先使用高層級的前進指針訪問,如果沒找到,再使用低一級的前進指針訪問.直到層級為0.

3). 跨度

? 跨度表示這個前進指針前進的步數,用于在訪問節(jié)點時計算節(jié)點在跳躍表中的排位.

? 指向null的前進指針對應的跨度為0,表示不連接任何節(jié)點.

(3). 跳躍表

? 數據結構定義如下:

typedef struct zskiplist {
    // 頭節(jié)點，尾節(jié)點
    struct zskiplistNode *header, *tail;
    // 節(jié)點數量
    unsigned long length;
    // 目前表內節(jié)點的最大層數
    int level;
} zskiplist;

? 表頭結點是不存儲數據的,并且表內節(jié)點的最大層數也不考慮表頭結點.

? 最大層數用于選擇一開始使用那一層的前進指針進行遍歷.

(4). 跳表的插入(Java實現)

public void insert(int value) {
    int level = randomLevel(); // 冪次定律
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    Node update[] = new Node[level];
    // 將0 ~ leval-1下標處的元素更新為head(跳表頭節(jié)點)
    for (int i = 0; i < level; ++i) {
        update[i] = head;
    }

    // 從最高層向下尋找,類似跳表中的查找
    Node p = head;
    for (int i = level - 1; i >= 0; --i) {
        while (p.forwards[i] != null && p.forwards[i].data < value) {
            // 向后尋找
            p = p.forwards[i];
        }
        update[i] = p;// 更新每一個update,也就是說update記錄的是在每一層中node節(jié)點的前繼節(jié)點
    }

    // 更新每一層,通過update數組
    for (int i = 0; i < level; ++i) {
        newNode.forwards[i] = update[i].forwards[I];
        update[i].forwards[i] = newNode;
    }

    // 更新層數
    if (levelCount < level) levelCount = level;
}

5. 整數集合

整數集合是集合(set)的底層實現之一,當一個集合中只包含整型元素時,并且數量不多,Redis就會使用整數集合作為集合的底層實現.

以數組為底層實現的set

(1). 整數集合的實現

? 整數集合是Redis用于保存整數值的集合抽象數據結構,可以保存int16_t,int32_t或者int64_t.

? 結構體定義如下:

typedef struct intset{
    // 編碼方式
    uint32_t encoding;
    // 集合包含的元素數量
    uint32_t length;
    // 保存元素的數組(這里的類型為最基本的類型,后面根據不同的encoding,使用多個格子表示一個元素)
    int8_t contents[];
} intset;

• encoding:決定了contents數組中值的類型
• length:記錄整個整數集合包含的元素數量
• contents:雖然定義為int8_t,但是實際的類型還是決定于encoding.并且數組中的元素在數組中按照大小升序排列.不包含重復項

? 對整數集合的各種操作類似ArrayList.

? 對元素的查找是二分的,插入操作也會先找這個元素,也是先二分,在移動后面的元素.

(2). 升級

? 當要添加一個元素,但是這個元素超出了現有的編碼方式的取值范圍時,就需要執(zhí)行升級來對數組的元素進行擴充.然后才可以將這個元素插入到整數集合中.

? 大致步驟如下:

1. 根據新元素的類型,擴展整數集合底層數組的空間大小,并且分配新元素的空間(在原有空間基礎上進行擴容,而不是重新分配整個新的數組)
2. 將原先就存在的數據轉換為新的類型,并且放置到正確的位置上,要保證有序性(對舊元素來說,是從后向前遍歷的).在空間的使用上面,起始位置變?yōu)樵瓉淼亩?結束位置變?yōu)槎都右?/li>
3. 將新元素添加到底層數組中

因為能引起升級的元素是超出原有的元素取值范圍的,所以要么比所有元素大,要么比所有元素小,所以最后這個元素會被放在索引處為0或者length-1的位置上.

升級操作是單向的,不存在降級的行為.

(3). 升級的好處

1. 提升靈活性:避免類型錯誤
2. 節(jié)約內存:為了實現上面的做法,也可以直接使用int64_t作為底層實現,不過太過耗費內存.

6. 壓縮鏈表

壓縮鏈表是list和hash的底層實現之一.

當一個list中只包含少量元素并且每一個元素都是小的整數值或者長度較短的字符串時,Redis就會使用壓縮鏈表作為list的底層實現.

當一個hash中只包含少量的鍵值對并且每個鍵值對都是小整數值或者長度較短的字符串時,Redis就會使用壓縮表來作為hash的底層實現.

(1). 壓縮列表的構成

? 壓縮列表是Redis為了節(jié)約內存而開發(fā)的,是由一些列特殊編碼的連續(xù)內存塊組成的順序型數據結構.一個壓縮列表可以包含任意多個節(jié)點,一個節(jié)點可以存儲一個字節(jié)數組或者一個整數值.

? 壓縮列表的組成:

(2). 壓縮列表節(jié)點的構成

? 每一個壓縮列表節(jié)點可以保存一個字節(jié)數組(0-2⁶-1, 0-2¹⁴-1, 0-2³²-1)或者一個整數值(4位無符號,1字節(jié)有符號,3字節(jié)有符號,int16_t類型,int32_t類型,int64_t類型),每一個節(jié)點的構成如下:

1). previous_entry_length

? 前一個節(jié)點的長度(以字節(jié)為單位).

? 如果前一個節(jié)點大小小于254字節(jié),那么這個屬性只占一個字節(jié),如果超出254,那么這個屬性占5字節(jié).

? 記錄這個值的目的在于可以直接計算得出前一個節(jié)點的起始地址.壓縮列表從表尾向表頭遍歷就是通過這個原理實現的.只要擁有了一個指向某節(jié)點其實地址的指針,就可以一直向前尋找,知道到達頭節(jié)點.

2). encoding

? 這個屬性記錄了節(jié)點的content屬性鎖保存的數據的類型以及長度

? 如果存儲的是字節(jié)數組,那么encoding長度為1(00xxxxxx),2(01開頭)或者5字節(jié)(10開頭),去掉開頭的兩位之后表示字節(jié)數組的長度.

? 如果存儲的是數字,encoding起始的兩位為11.

3). content

? 節(jié)點的content屬性負責保存節(jié)點的值,節(jié)點的值可以使字節(jié)數組或者整數,由encoding決定.

(3). 連鎖更新

? 之前的節(jié)點構成中我們知道previous_entry_length屬性可以是1字節(jié)(0~254)也可以是5(255~...)字節(jié).那么如果有若干長度為220~223字節(jié)長度的節(jié)點連續(xù)排列,此時將第一個節(jié)點進行擴容,擴容至224節(jié)點以上,這個節(jié)點的長度是記錄在下一節(jié)點上的,那么下一節(jié)點的previous_entry_length就會由1字節(jié)變?yōu)?字節(jié),會進行空間的重分配,然后繼續(xù)向后發(fā)生連鎖反應.

? 這里需要知道的是,==普通的插入操作(不產生連鎖更新現象)是將插入元素的所有后繼節(jié)點整體向后移動,并不需要挨個的進行擴容==,效率并不低.而連鎖更新現象只有節(jié)點長度為220~223字節(jié)的節(jié)點連續(xù)排列時才會發(fā)生,概率非常低,并且對三五個節(jié)點的連鎖更新并不會影響性能.

7. 對象

? 之前的6個小結介紹了Redis中使用到的6種底層數據結構,但Redis并沒有直接使用這些數據結構來實現NoSQL數據庫,而是創(chuàng)建了對象系統(tǒng),這個系統(tǒng)包含字符串對象(string),列表對象(list),哈希對象(hash),集合對象(set)和有序集和對象(zset).每一種對象都至少用到了一種底層數據結構.

? 針對不同的使用場景,為一個對象設置多種不同的數據結構實現,從而優(yōu)化使用效率.

? Redis還為對象系統(tǒng)實現了基于引用計數的內存回收機制.

? Redis的對象帶有訪問時間的記錄信息.空轉時間較長的元素是可能被優(yōu)先刪除的.

(1). 對象的類型與編碼

? Redis使用對象來表示數據庫中的鍵和值,也就是說,我們在Redis數據庫中新建一個鍵值對,Redis至少會創(chuàng)建兩個對象,一個對象充當鍵,一個對象充當值.

? 每一個對象都由一個redisObject表示.

typedef struct redisObject{
    // Redis對象類型,就是Redis中5種數據結構,分別對應五個不同的常量
    unsigned type : 4;
    // 編碼,也就是底層數據結構的類型對應的符號
    unsigned encoding : 4;
    // 指向實際底層數據結構(實際內存)的指針
    void *ptr;
} robj;

(2). Redis對象類型和底層數據結構的對應

? 跳表和字典可以使用同一種編碼,也就是說,在Redis對象中,跳表和字典是搭配使用的.但字典可以單獨存在.

(2). string對象

? 字符串對象的編碼可以是int,raw或者embstr.

? 如果是int類型,那么ptr指針指向一個long類型的變量.

? 如果是row類型,那么ptr指向一個sds結構體.兩次內存分配.

? 如所示embstr類型,那么在==redisObject的后面緊接著就是sds結構體的內存==.只進行一次內存分配.

? 需要知道的是,浮點型的數值是使用后兩種類型當做字符串存儲的.

編碼轉換:

? int編碼的字符串經過一系列操作(如追加式的拼接)后,不再是整數值,就會變成raw編碼的字符串.

? ==embstr編碼的字符串對象沒有任何修改程序,所以是只讀的.所以對embstr編碼的字符串進行修改時,就會轉換成raw編碼的字符串==

(3). list對象

? 列表對象的編碼可以是ziplist(壓縮列表)或者linkedlist(雙端列表).

? 如果使用ziplist作為編碼,ptr指針指向的是一個壓縮列表,壓縮列表的每一項就是list中的每一個元素.

? 如果使用linkedlist作為編碼,創(chuàng)建的將會是一個鏈表,ptr指針指向鏈表對象(而非頭節(jié)點),每一個節(jié)點都是字符串對象(字符串對象是Redis對象中唯一可以被嵌套的).

(4). hash對象

? 哈希對象的編碼可以是ziplist或者hashtable(字典).

? 使用ziplist作為編碼時,當有新的鍵值對進入hash對象時,程序先將保存了鍵的壓縮列表節(jié)點推入列表尾,再添加值.也就是說,鍵和值一一對應,==先是鍵再是值==,只靠這個約定限制.先添加的鍵值對在空間上處于后添加的鍵值對之前.

? 使用hashtable作為編碼的哈希對象,那么底層就跟Java中的HashMap差不多,鍵和值都必須是字符串對象

(5). set對象

? 集合對象的編碼可以使intset(整數集合)或者hashtable(字典).

? 使用intset作為編碼,那么ptr指針指向一個整數集合結構體,內部實現類似于元素不重復的ArrayList(并且有整數集合的特性:內部動態(tài)類型和升級).

? 使用hashtable作為編碼,那么ptr指針指向一個字典結構體,其中字典只有鍵,所有的值都為NULL,這種實現很想Java中的HashSet.

(6). zset對象

? 有序集和的編碼可以是ziplist或者zkiplist(搭配hashtable).

? ziplist編碼的有序集和對象使用壓縮列表作為底層實現,每兩個連續(xù)的壓縮列表節(jié)點表示一個zset節(jié)點,前一個保存元素成員,后一個保存分值.內部按分值升序排列.

? skiplist編碼的有序集和內部同事包含一個字典和一個跳表.其中的跳表按分值從小到大保存了所有集合元素.跳表節(jié)點的object屬性保存了元素的成員,score屬性保存了元素的分值.字典存儲了所有成員到分值的映射.

? ==值得一提的是,雖然使用了兩種結構共同表示zset,但是底層的數據都是使用string表示的,在這兩種結構中,通過共享指針做到了極小的內存開銷.==

==為什么要使用跳表和字典同時實現有序集和:==

? ==理論上這兩種數據結構都可以單獨完成zset的實現,但是單一使用字典,會導致無法按照有序的方式排列元素,導致每次執(zhí)行范圍型操作時,都需要遍歷并排序所有元素;單一使用跳表,根據成員查找分值的時間復雜度會大大上升.==

(7). 類型檢查和命令多態(tài)

? Redis中用于操作數據的命令分為兩類:一類是對任何鍵都可以使用的命令,如DEL,TYPE等.另一類只能對特定的鍵執(zhí)行,例如:SET,GET,APPEND,STRLEN只能對字符串的鍵執(zhí)行(使用錯誤會報錯).

1). 類型檢查的實現

? Redis根據redisObject的type屬性實現類型的檢查.

? 在執(zhí)行一個類型特定命令之前,服務器會檢查輸入的鍵的值對象是否為執(zhí)行命令所需的類型,如果是曹會執(zhí)行命令,否則會返回一個類型錯誤.

2). 多態(tài)命令的實現

? Redis還會根據redisObject的不同編碼方式,選擇執(zhí)行不同的代碼來執(zhí)行命令.也就是說,在內部通過簡單的類型判斷來完成硬編碼的方法選擇,從而實現多態(tài).

(8). 內存回收

? Redis在字節(jié)的對象系統(tǒng)中構建了一個引用計數技術實現的內存回收機制.

? 在redisObject中有一個字段為refcount,保存了這個對象被使用的數量,初始化為1.

? 計數器的增加可以認為是兩種現象:新的鍵指向這個值,在一個Redis程序中被持有.

(9). 對象共享

? Redis中如果有兩個100的string,那么不會在內存中存在兩個一樣的100,而是指向同一片內存,然后這個100的redisObject中的計數器加一.

? 目前來說,Redis服務器在初始化時會創(chuàng)建0~9999一萬個字符串對象,后面使用時直接共享即可,而不是創(chuàng)建新的對象.

(10). 對象的空轉時長

? redisObject結構包含的隊后一個屬性,:ru屬性.記錄了對象最后一次被命令程序訪問的時間.將當前時間減去這個lru時間就可以計算出空轉時間.

? 這個時間可以被用在服務器上的內存回收算法LRU(最近最少使用算法).