понедельник, сентября 29, 2014

"Пропавшие" ключи на Redis Slaves

Если вы используете ключи со сроком действия в Redis, вы можете сильно удивиться, как только добавите новый Redis slave к своему master серверу: на вашем slave сервере может не хватать до 25% ключей. Это особенно часто случается, если у вас есть большое количество ключей со сроком действия.

На slave сервере потерялись ключи? Данные утеряны? Короткий ответ - "нет". Тем не менее, было бы полезно понять, почему, собственно, ваш slave показывает меньшее количество ключей, даже если вы не потеряли никаких данных. Причина в двух деталях реализации - как Redis работает с ключами, чей срок жизни истёк и как мастер Redis посылает данные для новых slave серверов.

Как в Redis заканчивается срок жизни для ключей?

Просроченные ключи в Redis не удаляются из памяти в тот момент, когда истекает срок их жизни. Вместо этого, они удаляются с помощью одного из двух методов:

  1. Когда вы пытаетесь читать или писать, сервер Redis сначала проверяет, существует ли этот ключ и имеет ли он срок действия. Если он существует и просрочен, Redis удаляет его из оперативной памяти до выполнения операции.
  2. Чтобы избежать ситуации, в которой ключи останутся в памяти навсегда, если к ключам не обращались, Redis использует простой пассивный алгоритм: каждые 10 миллисекунд, он берёт 100 случайных ключи со сроком жизни и сразу удаляет любые ключи, срок жизни которых уже истёк. Если удалось удались 25 или более ключей, Redis берёт еще 100 ключей и т.д.
Понимание того, как работает второй метод очень важно, т.к. это означает, что до 25% из ваших ключей могут быть уже просрочены, но еще не были удалены из памяти. При этом Redis будет по прежнему их учитывать и в "ключах" и в "истекает" при выводе INFO, пока они не будут исключены из памяти.

Как Redis шлёт данные на slave сервер?

Когда новый slave подключатся к master, мастер создает RDB снимок своего набора ключей  и отправляет его в slave. А когда Redis создает RDB снимки, он не включает в него просроченные ключи, даже если они еще не удалены из памяти.

Так почему же на slave меньше ключей, чем на master?

При подключении, slave к Redis серверу он получает набор данных, который не включает в себя ключи с истёкшим сроком жизни, даже если они еще ​​не были удалены из памяти. И поскольку до 25% от вашего общего количества ключей, могут быть ключи срок жизни которых уже истёк, твой slave может показывать количество ключей до 25% ниже, чем у мастера. Кроме того, это та же самая причина, при которой ваши ключи со сроком жизни могут потеряться при восстановлении сервера Redis из резервной копии RDB.

Оригинал на английском языке: http://www.redisgreen.net/blog/missing-keys-on-redis-slave/?utm_source=redisweekly&utm_medium=email

суббота, сентября 13, 2014

Используем Lua чтобы сделать multi-get для хешей в Redis

На нашем текущем проекте в Tradier мы активно используем хеши в Redis. Нам очень нравиться универсальность Redis - разные типы данных создают широкий диапазон возможностей. И нас впечатляет поведение Redis, когда приходится быстро писать много данных. При этом впечатление от быстрой записи несколько меркнет как только приходится делать мулти чтение .

Используя Redis Ruby Gem мы начали с конвейерных (pipilined) запросов. Pipiline запросы в Redis возвращают массив с результатами всех операций в конвейере:
data = {}

$redis.pipelined do
  keys.each do |key|
    data[key] = $redis.hgetall(key)
  end
end

data.each do |key,value|
  data[k] = v.value
end
Такой подход оказался весьма медленным, как только мы стали работать с большими наборами ключей. Очень хотелось чего-то похожего на multi-get в Memcached. И использование Lua скриптов в Redis выглядело самой интересной альтернативой любым других решениям, чтобы сделать такую фичу. Не особо работая с Lua мы очень удивились тому, как много можно сделать с использованием Lua скриптов. Используя Lua мы можем за один запрос к Redis получить все ключи, которые нам нужны:
local collate = function (key)
  local raw_data = redis.call('HGETALL', key)
  local data = {}

  for idx = 1, #raw_data, 2 do
    data[raw_data[idx]] = raw_data[idx + 1]
  end

  return data;
end

local data = {}

for _, key in ipairs(KEYS) do
  data[key] = collate(key)
end
Код реально простой. Мы можем пройтись по переданным в функцию ключам и собрать данные из разных хешей в одну кучу. Проблемы начались, когда мы стали отправлять данные обратно в ruby. Оказалось, что объекты в Lua не всегда просто сериализуются в объекты Ruby. Реализация Lua в Redis позволяет использовать сериализацию в cjson и cmsgpack. Нам надо просто вернуть всё назад:
-- return json
return cjson.encode(response)

-- return messagepack
return cmsgpack.pack(data)
Выбирая между pipelined запросами, lua + json и lua + messagepack, последний вариант оказался самым быстрым. Наша финальная реализация:
require 'redis'
require 'redis'
require 'msgpack'

keys = %w(FOO BAR BAZ)

lua_msgpack_loader = <<LUA
local collate = function (key)
  local raw_data = redis.call('HGETALL', key)
  local hash_data = {}

  for idx = 1, #raw_data, 2 do
    hash_data[raw_data[idx]] = raw_data[idx + 1]
  end

  return hash_data;
end

local data = {}

for _, key in ipairs(KEYS) do
  data[key] = collate(key)
end

return cmsgpack.pack(data)
LUA

redis = ::Redis.new(:driver => :hiredis)
data = MessagePack.unpack(redis.eval(lua_msgpack_loader, :keys => keys))
И конечно же результаты тестов для 10к ключей:
                     user     system      total        real
lua + json        0.350000   0.010000   0.360000 (  1.242315)
lua + msgpack     0.260000   0.020000   0.280000 (  1.146377)
redis pipelined   1.070000   0.020000   1.090000 (  1.759858)
В целом, мы были приятно удивлены как Redis и Lua позволяют делать классные вещи!

Оригинал на английском языке: http://stdout.tradier.com/development/2014/07/10/using-lua-to-implement-multi-get-on-redis-hashes.html?utm_source=redisweekly&utm_medium=email#.VBLQO8J_sud

четверг, сентября 11, 2014

Развлекаемся с геоданными с MariaDB и ElasticSearch

Собираем геоданные

У Google есть классное API для геокодирования адресов. Я получил кучу данных, когда я искал адрес моего любимого футбольного клуба:
curl -XGET https://maps.googleapis.com/maps/api/geocode/json?address=Stadion+Feijenoord
Смотрите сами https://maps.googleapis.com/maps/api/geocode/json?address=Stadion+Feijenoord
Но больше всего нам интересны геоданные:
"geometry" : {
    "location" : {
        "lat" : 51.8939035,
        "lng" : 4.5231352
    },
}
Широта(lat) и долгота (lng) это координаты, которые определяют положение на сфере, в нашем случае на нашей родной планете.
С этими данным можно делать много классных вычислений типа определения дистанции между двумя точками или вычисления какие места расположены в определенном радиусе от точки.

Сохраняем геоданные в MariaDB

В MySQL 5.6 появилась возможность хранения пространственных данных. Теперь вы можете хранить геоданные в специальном типе данных POINT. Примечание: Если хотите потренироваться сами, предлагаю сразу создать песочницу в виртуалке. Я описываю как это сделать в конце статьи. Создадим колонку с типом POINT:
CREATE DATABASE demo;
CREATE TABLE demo.important_locations (location POINT NULL DEFAULT NULL);
Теперь можно вставить широту и долготу:
INSERT INTO demo.important_locations(location) VALUES(GeomFromText('POINT(51.8939035 4.5231352)',0));
А теперь давайте посчитаем расстояние от стадиона до мэрии, где мы отпразднуем наш успех!

Расчет расстояния в MariaDB

Вы ожидаете что будет простая функция для расчета расстояния между координатами? Ну, на самом деле да. Она называется st_distance(g1, g2) и доступна с MySQL 5.6. Но есть нюанс: расстояние вычисляется использую систему координат на плоскости вместо сферических координат. Вы можете прочитать про это в этой статье по Google Maps API.
Кратко: это выражение для расчета дистанции от стадиона к мэрии в координатах (51.9228644,4.4792299):
SELECT (
  6371 * acos(
    cos(radians(51.9228644)) * cos(radians(x(location))) * cos(radians(y(location)) - radians(4.4792299))
    +
    sin(radians(51.9228644)) * sin(radians(x(location)))
  )
) AS distance
FROM demo.important_locations
ORDER BY distance;
И расстояние - 4.409 километра!
+--------------------+
| distance           |
+--------------------+
| 4.4092536956929855 |
+--------------------+
1 row in set (0.00 sec)

Храним геоданные в ElasticSearch

В ElasticSearch тоже есть специальный тип данных geo_point для хранения геометрических данных.
Создадим новый индекс с полем типа geo_point:
curl -XPUT http://localhost:9200/important_locations -d '
{
  "mappings": {
    "location": {
      "properties": {
        "name": {"type": "string"},
        "location": {"type": "geo_point"}
      }
    }
  }
}'
Проверяем:
curl -XGET 'http://localhost:9200/important_locations/_mapping'
{
  "important_locations":{
    "location":{
      "properties":{
        "location":{
          "type":"geo_point"
        },
        "name":{
          "type":"string"
        }
      }
    }
  }
}
Теперь добавим несколько мест в наш индекс:
curl -XPOST http://localhost:9200/important_locations/location/ -d '{"name": "Fanshop Centraal Station Rotterdam", "location": {"lat": "51.924285", "lon": "4.469892"}}'
curl -XPOST http://localhost:9200/important_locations/location/ -d '{"name": "Fanshop Stadion", "location": {"lat": "51.893423", "lon": "4.525188"}}'
curl -XPOST http://localhost:9200/important_locations/location/ -d '{"name": "Fanshop Station de Kuip", "location": {"lat": "51.891288", "lon": "4.513916"}}'
curl -XPOST http://localhost:9200/important_locations/location/ -d '{"name": "Fanshop Coolsingel", "location": {"lat": "51.91862", "lon": "4.480092"}}'
Я хочу узнать какие фанатские магазины расположены рядом с мэрией с сортировкой результатов по расстоянию:
curl -XGET 'http://localhost:9200/important_locations/_search?pretty=true' -d '
{
    "sort" : [
        {
            "_geo_distance" : {
                "location" : {
                    "lat" : 51.92286439999999,
                    "lon" : 4.479229999999999
                },
                "order" : "asc",
                "unit" : "km"
            }
        }
    ],
    "query": {
        "filtered" : {
            "query" : {
                "match_all" : {}
            }
        }
    }
}'
Расстояние в поле sort :
{
  "took" : 173,
  "timed_out" : false,
  "_shards" : {
    "total" : 5,
    "successful" : 5,
    "failed" : 0
  },
  "hits" : {
    "total" : 4,
    "max_score" : null,
    "hits" : [ {
      "_index" : "important_locations",
      "_type" : "location",
      "_id" : "OpuBlM6nQFOZ5lCEcBVA8w",
      "_score" : null, "_source" : {"name": "Fanshop Coolsingel", "location": {"lat": "51.91862", "lon": "4.480092"}},
      "sort" : [ 0.47564430077142694 ]
    }, {
      "_index" : "important_locations",
      "_type" : "location",
      "_id" : "xL0Oy5XqRs-DgZQqjMgTiQ",
      "_score" : null, "_source" : {"name": "Fanshop Centraal Station Rotterdam", "location": {"lat": "51.924285", "lon": "4.469892"}},
      "sort" : [ 0.6595521711295553 ]
    }, {
      "_index" : "important_locations",
      "_type" : "location",
      "_id" : "RwhR9pXuRP2GBse3JmjdGA",
      "_score" : null, "_source" : {"name": "Fanshop Station de Kuip", "location": {"lat": "51.891288", "lon": "4.513916"}},
      "sort" : [ 4.241464778143902 ]
    }, {
      "_index" : "important_locations",
      "_type" : "location",
      "_id" : "5TV1jQm1ROqvbD3oFR0k7Q",
      "_score" : null, "_source" : {"name": "Fanshop Stadion", "location": {"lat": "51.893423", "lon": "4.525188"}},
      "sort" : [ 4.5449626829339085 ]
    } ]
  }
}
Меньше полу километра! Круто, правда? Можно еще лучше! Давайте оставим только магазины в километровом радиусе от стадиона:
curl -XGET 'http://localhost:9200/important_locations/_search?pretty=true' -d '
{
  "query": {
    "filtered" : {
        "query" : {
            "match_all" : {}
        },
        "filter" : {
            "geo_distance" : {
                "distance" : "1km",
                "location" : {
                    "lat" : 51.8939035,
                    "lon" : 4.5231352
                }
            }
        }
    }
  }
}'
{
  "took" : 15,
  "timed_out" : false,
  "_shards" : {
    "total" : 5,
    "successful" : 5,
    "failed" : 0
  },
  "hits" : {
    "total" : 2,
    "max_score" : 1.0,
    "hits" : [ {
      "_index" : "important_locations",
      "_type" : "location",
      "_id" : "RwhR9pXuRP2GBse3JmjdGA",
      "_score" : 1.0, "_source" : {"name": "Fanshop Station de Kuip", "location": {"lat": "51.891288", "lon": "4.513916"}}
    }, {
      "_index" : "important_locations",
      "_type" : "location",
      "_id" : "5TV1jQm1ROqvbD3oFR0k7Q",
      "_score" : 1.0, "_source" : {"name": "Fanshop Stadion", "location": {"lat": "51.893423", "lon": "4.525188"}}
    } ]
  }
}
Видим, что условию удовлетворяют только два из четырех магазинов. Надо отметить из на карте!

Совет профи: пользовательские типы в Doctrine.

Я показал как добавить POINT в MariaDB используя функцию GeomFromText. На практике мы используем Doctrine ORM чтобы управлять такими данными. Вы можете создать свой тип данных в Doctrine для таких вещей. И вам повезло, что кто-то уже это сделал. Я пробовал пакет creof/doctrine2-spatial. Он позволяет использовать тип POINT в анотации:
<?php
use CrEOF\Spatial\PHP\Types\Geometry\Point;
use Doctrine\ORM\Mapping as ORM;

/**
 * @ORM\Table(name="important_locations")
 * @ORM\Entity
 */
class ImportantLocation
{
    /**
     * @var integer
     *
     * @ORM\Column(name="id", type="integer")
     * @ORM\Id
     * @ORM\GeneratedValue(strategy="IDENTITY")
     */
    private $id;

    /**
     * @var Point
     *
     * @ORM\Column(name="location", type="point", nullable=true)
     */
    private $location;

    /**
     * @param Point $location
     */
    public function setLocation(Point $location)
    {
        $this->location = $location;
    }
}
Это позволяет добавлять местоположение еще проще:
$importantLocation = new ImportantLocation()
$importantLocation->setLocation(new Point(51.8939035, 4.5231352));


Настраиваем тестовое окружение

В этой статье я использовал песочнику от Vagrant на Ubuntu 14.04. Мой Vagrantfile:
Vagrant.configure(2) do |config|

  config.vm.box = "ubuntu/trusty64"

end
Потом ставил MariaDB и ElasticSearch:
sudo apt-get install software-properties-common -y
sudo apt-key adv --recv-keys --keyserver hkp://keyserver.ubuntu.com:80 0xcbcb082a1bb943db
sudo add-apt-repository 'deb http://ams2.mirrors.digitalocean.com/mariadb/repo/10.0/ubuntu trusty main'
sudo apt-get update
sudo apt-get install mariadb-server -y

sudo apt-get install openjdk-7-jre-headless -y
wget -qO - http://packages.elasticsearch.org/GPG-KEY-elasticsearch | sudo apt-key add -
echo "deb http://packages.elasticsearch.org/elasticsearch/1.3/debian stable main" | sudo tee -a /etc/apt/sources.list
sudo apt-get update
sudo apt-get install elasticsearch
sudo service elasticsearch start

Оригинал статьи на английском языке: http://labs.qandidate.com/blog/2014/09/09/having-fun-with-geometry-data-in-mariadb-and-elasticsearch/

Легковесная аналитика с битовыми картами Redis и Lua

Каждый день в Belly мы собираем около 3гб данных и обычно используем  MapReduce в Hadoop, который иногда занимает по несколько минут. Это быстро, тем не менее не приемлемо при разработке клиентского приложения, которое такие данные использует. Скорость в таком случае становится решающим фактором. 

В одном из наших последних проектов, мы делали панель, которая выводит аналитику по каждой торговой витрине в нашей сети.

Мы выделили следующие требования:
  • Выводить все показатели (например, количество уникальных клиентов в данном месте) как за диапазон дат так и за конкретную дату или месяц.
  • Уметь просматривать эти показатели за произвольный период рекламной кампании. Т.е. не заранее установленный диапазон "За неделю" или "Прошедшие 30 дней", а "28 октября 2013 - 17 ноября 2013".
  • Уметь масштабироваться до нескольких десяткой тысяч уникальных клиентов для одной витрины.  
  • Метрики должны работать очень быстро.
Достаточно быстры мы пришли к выводу, что традиционные решения в виде отложенных заданий или предварительно агрегированных
результатов не подходят, если необходимо поддерживать произвольные временные периоды для таких показателей. Каждый запрос должен выполняться "на лету". Оказалось, что выполнять подобные запросы на MySQL оказалось слишком дорогим даже при текущем количестве данных. Запрос одной метрики доходил иногда до нескольких секунд.

Redis

В Redis 2.6, были введены две дополнительные и довольно мощные функции: Битовые карты (Bitmaps) и поддержка Lua скриптов. 

Битовые карты

Битовые карты - это массив битов (нулей и единиц). В Redis можно установить и прочитать значение бита по заданному индексу в обычном ключе с помощью команд SETBIT и GETBIT. Например, в нашем случае, если клиенты с id = 2 и id = 6 зарегистрировались 12 ноября 2013. в витрине c id = 5 то это выглядело бы так:
Redis.setbit('business:5:customers:2013-11-12', 2, 1)
Redis.setbit('business:5:customers:2013-11-12', 6, 1)
Эти команды выставят биты с индексами 2 и 6 в единицу для ключа “business:5:customers:2013-11-12”. Символически значеним этого ключа станет последовательность "0010001".

Теперь, если мы хотим узнать сколько уникальных пользователей было в выбранной ветрине в указанный день мы можем просто выполнить
Redis.bitcount('business:5:customers:2013-11-12')
Команда BITCOUNT выполнить очень быстрый подсчет количества единиц в этой битовой строке. В нашем примере это будет 2.

В Redis мы может не только подсчитывать количество единиц с bitcount, но и выполнять битовые операции “AND”, “OR”, “XOR”, и “NOT”.

Вернёмся к нашим рекламным запросам. Чтобы  найти количество уникальных клиентов за указанный промежуток времени мы можем выполнить:
# Все ключи (даты) для которых вычисляем результат
keys = ['business:5:customers:2013-11-12', 'business:5:customers:2013-11-13', … to any date]
# Вычисляем пересечение всех указанных bitmaps и сохраняем в "business:5:customers:total"
Redis.bitop('OR', 'business:5:customers:total',  keys)
# Вычисляем количество
Redis.bitcount('business:5:customers:total')
Этот запрос даст нам количество уникальных клиентов за выбранный период.

Далее, если мы хотим взять этот результат и посчитать сколько мужчин было среди этих клиентов, мы можем выполнить битовое "И" полученной битовой карты с картой, которая отражает идентификаторы клиентов в мужской пол:
# Ключи для которых нужно провести расчёт
keys = ['business:5:customers:total', 'users:males']
# Посчитать пересечение ключе и сохранить результат в "business:5:males:total"
Redis.bitop('AND', 'business:5:males:total', keys)
# Посчитать количество
Redis.bitcount('business:5:males:total')
Резюмируя - битовые маски это чертовски крутая вещь.

Однако, не все, что нам нужно подсчитывать требует битовые маски. Такие штука, как "Чисто визитов" не требует уникальности для каждого пользователи и чтобы экономить память мы можем использовать обычный счётчик в Redis. Например инкриментировать счетчик визитов
Redis.incr('business:5:visits:2013-11-12')
Вот как это было изначально при расчете общего числа за отрезок времени в Ruby:
(start_date...end_date).each do |date|
  sum += Redis.get('business:5:visits:#{date}')
end
Это оказалось довольно медленно при подсчете за большое количество дней, и привело к появлению большого числа запросов к Redis для одной метрики.

На помощь приходит LUA 

Redis 2.6+ позволяет писать Lua скрипты, которые могут быть выполнены на Redis сервере. Внутри такого скрипты можно вызывать любые Redis команды. Это позволяет создавать аналоги хранимых процедур SQL. Таким образом, наша сумма из примеры выше может быть заменена следующим:

(выполняется в Redis) sum.lua:
local sum = 0
# для каждого ключа, который мы хотим суммировать
for index, key in ipairs(KEYS) do
  # Выполним команду Redis.get(key) чтобы получить значение ключа
  local value = tonumber(redis.call('GET', key))
  if value then
    sum = sum + value
  end
end
return sum
И вызов из Ruby
keys = []
(start_date...end_date).each do |date|
  keys << 'businesses:5:visits:#{date}''
end
#В продакшен окружении мы воспользуемся уже загруженным скриптом через evalsha, вместо eval
Redis.eval(`cat sum.lua`, keys)
Это небольшое изменение даёт вам возможность сильно увеличить скорость выполнения запроса и выполнить только 1 запрос к Redis вместо 365, если вы запрашиваете данные за год.

Плюсы и минусы


Как и всегда при использования такого подхода есть плюсы и минусы:

Плюсы:
  • Redis хранит все данные в памяти как ключ-значение и это очень быстро.
  • Используя битовые карты можно хранить большие объемы данные о пользователях в очень небольшом объеме памяти. И выполнять расчеты с ними ОЧЕНЬ быстро. Парни из Spool говорят "В тесте с 128 миллионами пользователей получение типичной метрики вида `уникальные пользователи за сутки` займет менее 50 мс на MacBook Pro, при этом займет всего 16 мб оперативной памяти". Очень крутая штука.
  • Lua скрипты позволяют сохранить присущую Redis скорость на сложных запросах.
  • Очень просто делать метрики в "реальном времени". События, которые мы хотим подсчитывать просто увеличивают счётчики или выставляют биты.
Минусы (примечание переводчика - как по мне, очень надуманные минусы):
  • Память стоит дороже, чем диск.
  • Redis это хранилище ключ-значение, тут нет зависимостей и типичного для ORM хранения данных из коробки. Нужно самому заботится об организации и именовании ключей, чтобы не запутаться.
  • Так как Redis - это хранилище в оперативной памяти для кейсов как у нас (не простой кеш, а скорее постоянное хранилище) сохранение данных на диск имеет решающее значение, а это порой не тривиально (см. http://redis.io/topics/persistence)
Оригинал на английском языке http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/


воскресенье, сентября 07, 2014

Redis: Удаление атрибутов hash по маске

Проблема:
Удалить поля HSET используя маску. Например
HMSET myhset f1 "v1" f2 "v2" x "v3" y "v4"
Хочется написать, что-то вида
HDEL myhset f*
Можно использовать HSCAN и несколько батчей, для удаления, однако он не гарантирует атомарность. Если последнее вам важно, на помощь приходит LUA:
-- ARGV[1] - hash key
-- ARGV[1] - lua pattern 
local fields = redis.call("HKEYS", ARGV[1]);
local retVal = {};
for key, value in pairs(fields) do
    if (string.match(value, ARGV[2])) then
        table.insert(retVal, value);
        redis.call("HDEL", ARGV[1], value);
    end
end

return retVal;
Скрипт имеет сложность O(n). Скрипт вернёт список полей, которые были удалены из HSET. Обратите внимание на string.match в LUA, чтобы понять что вам доступно помимо * в образце.

Вот как может выглядеть использование, если вы используете php и phpredis:
$r = new Redis();
$r->connect('127.0.0.1');

for ($i = 1; $i < 1000; $i++) {
    $r->hSet('myhash', 'aaa' . mt_rand(0, PHP_INT_MAX), 1);
}
$r->hSet('myhash', 'bad', 1);

$script = <<< SCR
    local fields = redis.call("HKEYS", ARGV[1]);
    local retVal = {};
    for key, value in pairs(fields) do
        if (string.match(value, ARGV[2])) then
            table.insert(retVal, value);
            redis.call("HDEL", ARGV[1], value);
        end
    end

    return retVal;
SCR;
var_dump($r->eval($script, ['myhash', '^b.+']));