Имплементация LRU кэша на Go

LRU: Least Recently Used — алгоритм кэширования, при котором вытесняются значения, которые дольше всего не запрашивались. Алгоритмическая сложность O(1), а потому кеш работает очень быстро и используется в memcached.

Кеш имеет очередь фиксированного размера. Когда новый элемент попадает в кеш, то добавляется в начало очереди. При запросе элемента очередь выталкивает элемент в начало, а если нужно освободить место, то из вытесняется последний элемент.

Свой memcached на Go

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

import (
    "container/list"
)

type Item struct {
    Key   string
    Value interface{}
}

type LRU struct {
    capacity int
    items    map[string]*list.Element
    queue    *list.List
}

func NewLru(capacity int) *LRU {
    return &LRU{
        capacity: capacity,
        items:    make(map[string]*list.Element),
        queue:    list.New(),
    }
}

Структура LRU содержит поле с количеством ячеек, поле двусвязного списка *list.List и поле для хранения хеш-таблицы map[string]*list.Element. А Item содержит поля для хранения ключа и значения кэшируемого элемента. Функция конструктор NewLru инициализирует LRU и возвращает ссылку на экземпляр.

Сохраняем значение в кэше

При сохранении элемента в кеше, инициализируем новую структуру Item и добавляем ее в начало очереди c.queue.PushFront(item). Возвращенный очередью *Element добавляем в хеш-таблицу, где ключ это идентификатор записи, а значение это ссылка на элемент очереди.

func (c *LRU) Set(key string, value interface{}) bool {
    if element, exists := c.items[key]; exists == true {
        c.queue.MoveToFront(element)
        element.Value.(*Item).Value = value
        return true
    }

    if c.queue.Len() == c.capacity {
        c.purge()
    }

    item := &Item{
        Key:   key,
        Value: value,
    }

    element := c.queue.PushFront(item)
    c.items[item.Key] = element

    return true
}

Перед добавлением в очередь проверяем нет ли уже такого ключа в хеш-таблице и если есть, то заменяем значение на новое и двигаем в начало очереди c.queue.MoveToFront(element).

Если количество элементов очереди равно максимальному количеству ячеек, то пора выбросить последний элемент из очереди и ключ из хеш-таблицы вызвав функцию purge().

func (c *LRU) purge() {
    if element := c.queue.Back(); element != nil {
        item := c.queue.Remove(element).(*Item)
        delete(c.items, item.Key)
    }
}

Получаем значение из кэша

При запросе элемента из кеша, ищем соответствие ключа в хеш-таблице и при нахождении получаем значение элемента через каст значения на структуру element.Value.(*Item).Value. Перед возвращением перемещаем элемент в начало очереди.

func (c *LRU) Get(key string) interface{} {
    element, exists := c.items[key]
    if exists == false {
        return nil
    }
    c.queue.MoveToFront(element)
    return element.Value.(*Item).Value
}

Дальше можно добавить mutex и сделать функцию потоко-безопасной. А еще можно заменить количество ячеек на размер кеша по объему памяти хранимых сущностей.

Среднеквадратическое отклонение

Расскажу о среднеквадратическом отклонении на примере собак. Имея группу собак рост которых 600, 470, 170, 430 и 300 мм. Как узнать какие из этих собак большие, какие маленькие, а какие можно отнести к средним? Тут на помощь приходит среднеквадратическое отклонениеσ (греческая буква сигма).

Формула очень проста: это квадратный корень из дисперсии случайной величины. Что такое дисперсия? Это среднее арифметическое квадратов разностей от среднего арифметического.

А теперь конкретно на примере наших собак, все вычисления буду писать на python без использования numpy. Первым делом находим среднее арифметическое всех элементов:

dogs = [600, 470, 170, 430, 300]
average = sum(dogs) / len(dogs)
# 394

Теперь надо посчитать дисперсию, для этого из каждой высоты собаки вычитаем среднее арифметическое всех элементов, сумируем и делим на количество элементов:

variance = sum([(n-average)**2 for n in dogs]) / len(dogs)
# 21704

Последним шагом извлекаем квадратный корень из дисперсии:

standard_deviation = variance ** 0.5
# ~147

Таким образом имея среднеквадратическое отклонение (147) и среднее арифметическое (394) можно сказать, что верхний порог для средней собаки — 394 + 147 = 541, а значит собака ростом 600 мм — большая. Для маленьких собак этот порог — 394 - 147 = 247, а значит собака ростом 170 мм - маленькая.

Но что делать если собак очень много и их количество постоянно растет? Обычный подход к вычислению тут не подойдет. В таком случае необходимо заменить среднее арифметическое математическим ожиданием при вычислении дисперсии.

Если вернуться к нашим собакам и мы считаем, что эти 5 собак лишь кусок от большой популяции собак, то при вычислении дисперсии необходимо делить не на число элементов, а на число элементов минус 1.

variance = sum([(n-average)**2 for n in dogs]) / (len(dogs) - 1)
# 27130
standard_deviation = variance ** 0.5
# ~164

HTTP запросы для Python 2 и Python 3

Для Python существует замечательная библиотека для работы со всеми типами HTTP запросов - Requests, но когда нужно сделать что-то без внешних зависимостей, то встает вопрос велосипедостроения. Проблема еще более усиливается когда необходима одновременная поддержка Python 2 и Python 3.

Стандартная библиотека urllib.urlopen не поддерживает методы для отправки PUT и DELETE запросов, а кроме того в Python 3 перенесли большинство методов из urllib2 в urllib.request, что добавляет некоторые костыли в код, для совместимости с Python 2. Таким образом составил себе список того что мне необходимо:

  • Совместимость Python 2 и 3;
  • Отправка GET, POST, PUT, DELETE запросов;
  • Парсинг JSON ответа.

Посидев пару часов собрал свой велосипед совмещающий в себе все эти требования:

import sys
import json

try:
    # python3
    from urllib.request import build_opener, Request, HTTPHandler
    from urllib.error import HTTPError
    from urllib.parse import urlencode
except ImportError:  # pragma: no cover
    # python2
    from urllib2 import build_opener, Request, HTTPHandler, HTTPError
    from urllib import urlencode


def request(url, method='GET', data=None, headers={}):
    if data is not None:
        data = urlencode(data)
        if method in ['GET', 'DELETE']:
            url = url + '?' + data
            data = None
        else:
            x_www = 'application/x-www-form-urlencoded; charset=utf-8'
            headers.update({'Content-Type': x_www})
            if sys.version_info > (3,):  # python3
                data = data.encode('utf-8')

    try:
        opener = build_opener(HTTPHandler)
        req = Request(url, data=data, headers=headers)
        req.get_method = lambda: method
        response = opener.open(req).read()
        data = json.loads(response.decode('utf-8'))
    except HTTPError as e:
        data = json.loads(e.read().decode('utf-8'))
    except ValueError:
        return False

    return data

Можно легко проверить работу всех этих методов используя сервис httpbin.org

data = {'foo': 'bar'}
headers = {'x-header': 'x-value'}

resp = request('https://httpbin.org/get', data=data, headers=headers)
assert resp['headers']['X-Header'] == 'x-value'
assert resp['url'] == 'https://httpbin.org/get?foo=bar'
assert resp['args']['foo'] == 'bar'

resp = request('https://httpbin.org/post', 'POST', data=data, headers=headers)
assert resp['headers']['X-Header'] == 'x-value'
assert resp['url'] == 'https://httpbin.org/post'
assert resp['form']['foo'] == 'bar'

resp = request('https://httpbin.org/put', 'PUT', data=data, headers=headers)
assert resp['headers']['X-Header'] == 'x-value'
assert resp['url'] == 'https://httpbin.org/put'
assert resp['form']['foo'] == 'bar'

resp = request('https://httpbin.org/delete', 'DELETE', data=data, headers=headers)
assert resp['headers']['X-Header'] == 'x-value'
assert resp['url'] == 'https://httpbin.org/delete?foo=bar'
assert resp['args']['foo'] == 'bar'

Альбом с улиц Los Angeles

Гуляя вечером по улицам Лос-Анджелеса к нам подошел веселый чернокожий парень и стал расспрашивать откуда мы, а потом сам рассказал свою историю, начинающего артиста. Дойдя до этого места он предложил нам поддержать его, купив альбом на простом CD и даже оставил на нем свой автограф в надежде, что он станет знаменитым.

Мы решили поддержать его и купили тот альбом. Теперь же спустя полтора года я так и не смог найти о нем ничего нового кроме аккаунта в Instagram и решил выложить тот альбом на SoundCloud, чтобы послушать мог каждый.

Сертификаты Let's Encrypt

Let’s Encrypt крут, а вот официальный клиент настолько ужасен, что уже появилось огромное количество альтернативных решений.

Для своих проектов я выбрал acme-tiny и написал инструкцию как автоматизировать перевыпуск сертификатов каждый месяц.

Установка и настройка клиента letsencrypt

  1. Создаем пользователя letsencrypt и необходимые директории:

    adduser --home /var/www/challenges \
        --shell /bin/sh \
        --disabled-password \
        --disabled-login \
        letsencrypt
    mkdir -p /etc/letsencrypt/domains
    
  2. Добавляем пользователя letsencrypt в sudoers для перезагрузки nginx:

    visudo -f /etc/sudoers.d/letsencrypt
    
    letsencrypt ALL=(ALL) NOPASSWD: /usr/sbin/service nginx reload
    
  3. Генерим основные приватные ключи:

    cd /etc/letsencrypt/
    openssl dhparam -out dhparam.pem 2048
    openssl genrsa 4096 > account.key
    
  4. Скачиваем клиент acme_tiny.py:

    cd /var/www/challenges
    wget https://raw.githubusercontent.com/diafygi/acme-tiny/master/acme_tiny.py
    
  5. Создаем скрипт /var/www/challenges/acme-tiny.sh, для автоматизации. Изменив переменную DOMAINS добавляем имена доменов, которым необходимы сертификаты:

    DOMAINS=( example.com foobar.com )
    DOMAIN_ROOT=/etc/letsencrypt/domains
    ACCOUNT_KEY=/etc/letsencrypt/account.key
    ACME_DIR=/var/www/challenges
    ACME_TINY=${ACME_DIR}/acme_tiny.py
    
    [ -d ${DOMAIN_ROOT} ] || { echo "ERROR: DOMAIN_ROOT dir does not exists"; exit 1; }
    [ -f ${ACCOUNT_KEY} ] || { echo "ERROR: ACCOUNT_KEY not found."; exit 1; }
    [ -d ${ACME_DIR} ] || { echo "ERROR: ACME_DIR dir does not exists"; exit 1; }
    [ -f "$ACME_TINY" ] || { echo "ERROR: ACME_TINY not found."; exit 1; }
    
    wget -O - https://letsencrypt.org/certs/lets-encrypt-x3-cross-signed.pem > ${DOMAIN_ROOT}/intermediate.pem
    
    for DOMAIN in "${DOMAINS[@]}"
    do
      if [ ! -f "${DOMAIN_ROOT}/${DOMAIN}.key" ]; then
        echo "INFO: Generation private key for $DOMAIN";
        openssl genrsa 4096 > ${DOMAIN_ROOT}/${DOMAIN}.key
        openssl req -new -sha256 -key ${DOMAIN_ROOT}/${DOMAIN}.key -subj "/CN=${DOMAIN}" > ${DOMAIN_ROOT}/${DOMAIN}.csr
      fi
    
      echo "INFO: Generation cert for $DOMAIN";
      python ${ACME_TINY} --account-key ${ACCOUNT_KEY} --csr ${DOMAIN_ROOT}/${DOMAIN}.csr --acme-dir ${ACME_DIR} > ${DOMAIN_ROOT}/${DOMAIN}.crt || exit 1
      cat ${DOMAIN_ROOT}/${DOMAIN}.crt ${DOMAIN_ROOT}/intermediate.pem > ${DOMAIN_ROOT}/${DOMAIN}.pem
    done
    
    sudo service nginx reload
    
  6. Устанавливаем права:

    chmod 700 /etc/letsencrypt
    chown -R letsencrypt: /etc/letsencrypt /var/www/challenges
    
  7. Добавляем location в nginx у всех доменов, которым необходимо получать сертификат:

    location /.well-known/acme-challenge/ {
        alias /var/www/challenges/;
        try_files $uri =404;
    }
    
  8. Запускаем:

    su -c 'umask 033; /bin/bash /var/www/challenges/acme-tiny.sh' letsencrypt
    

Настройка автоматического продления

  1. Создаем log файл:

    sudo touch /var/log/acme_tiny.log
    sudo chown letsencrypt: /var/log/acme_tiny.log
    
  2. Добавляем ежемесячную работу в crontab:

    nano /etc/cron.d/letsencrypt
    
    SHELL=/bin/sh
    PATH=/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin
    0 0 1 * * letsencrypt /bin/bash /var/www/challenges/acme-tiny.sh >> /var/log/acme_tiny.log
    

Получаем класс А в Nginx

server {
    listen      443;
    server_name example.com;

    ...

    ssl on;
    ssl_certificate /etc/letsencrypt/domains/example.com.pem;
    ssl_certificate_key /etc/letsencrypt/domains/example.com.key;
    ssl_session_timeout 5m;
    ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
    ssl_ciphers ECDHE-RSA-AES256-GCM-SHA384:ECDHE-RSA-AES128-GCM-SHA256:DHE-RSA-AES256-GCM-SHA384:ECDHE-RSA-AES256-SHA384:ECDHE-RSA-AES128-SHA256:ECDHE-RSA-AES256-SHA:ECDHE-RSA-AES128-SHA:DHE-RSA-AES256-SHA:DHE-RSA-AES128-SHA;
    ssl_session_cache shared:SSL:50m;
    ssl_dhparam /etc/letsencrypt/dhparam.pem;
    ssl_prefer_server_ciphers on;

    ...
}