Понимание исходного кода Memcached - LRU I

Распределитель Slab - это основной модуль кэш-системы, который в значительной степени определяет, насколько эффективно может использоваться узкое место - память. Остальные 3 части, а именно алгоритм LRU истечения срока входа; и модель, управляемая событиями, основанная на libevent; и постоянная жесткость в отношении распределения данных построены вокруг этого.

Плита I
Плита II
Плита III
LRU I (эта статья)
LRU II
LRU III
Событийный я

Чаще всего алгоритм LRU сочетается с хэш-картой и называется

Кэш LRU

В LRU-кэше хэш-карта обеспечивает быстрый доступ к кэшированным объектам; а LRU предотвращает бесконечное увеличение кеша, отмечая просроченные или так называемые наименее недавно использованные объекты. Затем мы посмотрим, как LRU работает с точки зрения высокого уровня.

Связанный список

Технически алгоритм LRU работает с связанным списком: всякий раз, когда запись в списке используется (открывается или обновляется), она удаляется из списка и прикрепляется к заголовку списка. Таким образом, чем ближе элемент к концу списка, тем он реже использовался. Следовательно, легко удалить нерелевантные или «просроченные» элементы из хвоста на основе определенной конфигурации.

Суровая карта

Связанный список работает медленно, когда дело доходит до доступа к элементам, поэтому используется другая структура данных. Мы видели, как связанный список объединяет блоки в блоки, чтобы получить свободные списки. В кэше LRU механизм аналогичен, однако это записи хэш-карты вместо фрагментов в slabs на этот раз подключили, что выглядит так:

Мы также можем сгладить связанный список и сделать структуру более понятной,

Основная структура данных - элемент

typedef struct _stritem {
    /* Protected by LRU locks */
    struct _stritem *next;
    struct _stritem *prev;
    /* Rest are protected by an item lock */
    struct _stritem *h_next;    /* hash chain next */
    rel_time_t      time;       /* least recent access */
    rel_time_t      exptime;    /* expire time */
    int             nbytes;     /* size of data */
    unsigned short  refcount;
    uint8_t         nsuffix;    /* length of flags-and-length string */
    uint8_t         it_flags;   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;       /* key length, w/terminating null and padding */
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
... // scr: cas
        char end; // scr: flexible array member indicating the item header "end"
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

Недвижимость в использовании

next, prev, slabs_clsid - item_link_q, item_unlink_q
it_flags - do_item_link, do_item_unlink
time, refcount - do_item_link
h_next - assoc_insert, assoc_delete
nkey - assoc_delete

Структура памяти блока элемента

Мы упомянули элемент данных в do_slabs_free. С помощью этой структуры данных мы теперь можем более внимательно изучить фрагмент.

Затем мы читаем соответствующий код, который выполняет описанные выше операции LRU.

do_item_link

int do_item_link(item *it, const uint32_t hv) { // scr: --------> 1)
...
    it->it_flags |= ITEM_LINKED;                // scr: --------> 2)
    it->time = current_time;

... // scr: stat

    /* Allocate a new CAS ID on link. */
... // scr: cas
    assoc_insert(it, hv);                       // scr: --------> 3)
    item_link_q(it);                            // scr: --------> 4)
    refcount_incr(&it->refcount);               // scr: --------> 5)
... // scr: stat

    return 1;
}

1) hv должно быть сокращенным «хешированным значением».

2) Установите ITEM_LINKED в it->it_flags и установите текущее время на it->time.

Поле it_flags используется в do_slabs_free и do_slabs_alloc

3) Вставьте элемент в хэш-карту.

4) Вставьте элемент в связанный список.

5) Увеличьте количество ссылок.

Это поле инициализируется как 1 в do_slabs_alloc

Здесь стоит отметить, что счетчик ссылок указывает, сколько подмодулей используют один и тот же ресурс, чтобы определить, когда фактически освободить ресурс (в данном конкретном случае item упоминается как slab, так и LRU). Я написал эту статью, в которой объясняется аналогичный механизм C ++.

item_link_q - добавить в связанный список

item_link_q - это потокобезопасная оболочка метода рабочей лошади do_item_link_q.

static void do_item_link_q(item *it) { /* item is the new head */
    item **head, **tail;
    assert((it->it_flags & ITEM_SLABBED) == 0);

    head = &heads[it->slabs_clsid];           // scr: ----------> 1)
    tail = &tails[it->slabs_clsid];
    assert(it != *head);
    assert((*head && *tail) || (*head == 0 && *tail == 0));
    it->prev = 0;                             // scr: ----------> 2)
    it->next = *head;
    if (it->next) it->next->prev = it;
    *head = it;
    if (*tail == 0) *tail = it;
    sizes[it->slabs_clsid]++;                 // scr: ----------> 3)
    return;
}

1) Получите head и tail соответствующего связанного списка LRU, обозначенного slabs_clsid. Обратите внимание, что slabs_clsid солено с типом очереди, поэтому каждая группа плит может включать несколько списков.

2) Стандартные операции «добавления элемента на передний план».

3) Увеличиваем глобальный массив sizes.

assoc_insert - добавить в хеш-карту

int assoc_insert(item *it, const uint32_t hv) { // scr: again, hv -> hash value
    unsigned int oldbucket;

... // scr: expanding related operations
    } else {
        it->h_next = primary_hashtable[hv & hashmask(hashpower)]; // scr:  1)
        primary_hashtable[hv & hashmask(hashpower)] = it;         // scr:  2)
    }

... // scr: expanding related operations
}

1) Разберитесь с потенциальным конфликтом. Если нет, h_next будет установлен на null.

2) Установите элемент в ведро в primary_hashtable.

Опущенная здесь расширяющая логика будет рассмотрена в следующих статьях.

do_item_unlink

void do_item_unlink(item *it, const uint32_t hv) {
    MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes);
    if ((it->it_flags & ITEM_LINKED) != 0) {
        it->it_flags &= ~ITEM_LINKED;         // scr: ----------> 1)
... // scr: stat
        assoc_delete(ITEM_key(it), it->nkey, hv); // scr: ------> 2)
        item_unlink_q(it);                    // scr: ----------> 3)
        do_item_remove(it);                   // scr: ----------> *)
    }
}

1) Очистите ITEM_LINKED в it->it_flags.

2) Удалите элемент из хеш-карты.

3) Удалите элемент из связанного списка.

*) Фактический выпуск item будет рассмотрен в следующей статье.

item_unlink_q - удалить из связанного списка

Точно так же item_unlink_q является потокобезопасной оболочкой метода рабочей лошади do_item_unlink_q.

static void do_item_unlink_q(item *it) {
    item **head, **tail;
    head = &heads[it->slabs_clsid];           // scr: ----------> 1)
    tail = &tails[it->slabs_clsid];

    if (*head == it) {                        // scr: ----------> 2)
        assert(it->prev == 0);
        *head = it->next;
    }
    if (*tail == it) {
        assert(it->next == 0);
        *tail = it->prev;
    }
    assert(it->next != it);
    assert(it->prev != it);

    if (it->next) it->next->prev = it->prev;
    if (it->prev) it->prev->next = it->next;
    sizes[it->slabs_clsid]--;                 // scr: ----------> 3)
    return;
}

1) То же самое, получите head и tail соответствующего связанного списка LRU, обозначенного slabs_clsid.

2) Стандартные операции «удаления элемента из связного списка».

3) Уменьшаем глобальный массив sizes.

assoc_delete - удалить с хеш-карты

static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
    item **pos;
    unsigned int oldbucket;

... // scr: expanding related operations
    } else {
        pos = &primary_hashtable[hv & hashmask(hashpower)]; //scr:1)
    }

    while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
        pos = &(*pos)->h_next; // scr: -------------------------> 2)
    }
    return pos;
}

...

void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
    item **before = _hashitem_before(key, nkey, hv);

    if (*before) {
        item *nxt;
...
        nxt = (*before)->h_next; // scr: -----------------------> 3)
        (*before)->h_next = 0;   /* probably pointless, but whatever. */
        *before = nxt; // scr: ---------------------------------> 4)
        return;
    }
    /* Note:  we never actually get here.  the callers don't delete things
       they can't find. */
    assert(*before != 0);
}

1) Получите хеш-ведро, используя hv.

2) Просмотрите цепочку конфликтов и сравните key. Обратите внимание, что значение результата - это адрес next члена элемента before найденного. Когда нет конфликта, адресом является сама корзина.

3) Установите следующий элемент после найденного во временную переменную nxt.

4) Обновите next член элемента before найденным.

Забрать домой

Попробуй это".

Изначально опубликовано на holmeshe.me.