@pro100tak15 сен 2011 в 09:51

Lock-free memcache API

5 мин

PHP *

+41

Комментарии 69

@evilbloodydemon 15 сен 2011 в 10:05

Dog pile effect эта ситуация называется.

@pro100tak 15 сен 2011 в 10:08

Не знал, спасибо. То что не Race condition — это точно. Думал — как назвать, плюнул и никак не назвал.

@pro100tak 15 сен 2011 в 10:11

Обновил топик.

@akzhan 15 сен 2011 в 10:39

И вправду, код не очень читабелен.

Каким способом вы устраняете этот эффект? Не вижу, где инкремент тестируется на то, что не было выполнено одновременное увеличение двумя процессами.

@akzhan 15 сен 2011 в 10:47

На всякий случай приведу рабочий код. Не факт, что оптимальный, но работает.

  # Использование
  v = DataCache.get_or_evaluate("key", 10.seconds) do
    5 + 5 # evaluation block
  end 

  # берет значение из кэша.
  # возвращает его, если оно актуально, или если новое значение кем-то вычисляется.
  # иначе устанавливает признак вычисления, вычисляет, пишет в кэш и возвращает.
  def get_or_evaluate(key, expiry = 0)
    return yield if @impl.nil?
    key_in_eval = "#{key}:in_eval"
    key_expiry_at = "#{key}:expiry_at"
    @impl.add(key_in_eval, 0, 0, true) rescue nil
    loop do
      val = get(key)
      in_eval = ((@impl.get(key_in_eval, true) || 0) rescue 0).to_i
      expiry_at = ((@impl.get(key_expiry_at, true) || 0) rescue 0).to_i
      logger.debug("In eval: #{in_eval}, Expiry at: #{expiry_at}, Now: #{Time.now.to_i}")
      return val if val && (in_eval > 0 || expiry_at >= Time.now.to_i)
      begin
        break if @impl.incr(key_in_eval, 1) == 1
        return val if @impl.decr(key_in_eval, 1) == 1
      rescue
        return val
      end
      sleep 0.1
    end
    delete(key_expiry_at)
    begin
      val = yield
      set(key, val)
      @impl.set(key_expiry_at, Time.now.to_i + expiry, 0, true)
    ensure
      @impl.decr(key_in_eval, 1)
    end
    val
  end

@pro100tak 15 сен 2011 в 10:54

Весь инкремент даден на откуп мемкешу. Если в 2-х процессах одновременно произойдёт инкремент — отлично. В нативном ключе ..._increment будет лежать значение, которое наинкрементил мемкеш. А в надстроенном массиве — просто бекап на случай, если кто-то захочет взять значение инкрементируемого ключа через обычный MC::get().

@pro100tak 15 сен 2011 в 10:58

Разбил код на 2 части. Вторая часть немного больше, но там всего 6 небольших методов.
Самая большая рутина — в каждом методе распознавать инкрементные ключи и удалять нативный инкрементирующися ключ. значение

@romka777 15 сен 2011 в 13:12

Первую часть можно вообще убрать.
По методу — способ оригинальный, но всё равно может запуститься несколько процессов на генерацию контента из бд.

@romka777 15 сен 2011 в 13:18

Кстати лок можно поставить только на процедуру проверки валидности кеша.

@Wonderful 15 сен 2011 в 10:42

Подскажите, разъясните нубу, может я чего-то не понимаю, а чем плох (неправилен) такой подход, как ключ-backup для memcache — просто с увеличенным значением времени *жизни* ключа? Т.е. когда время жизни кончилось, отдаём ключ-backup (который старше на 5 секунд, скажем). Соответственно генерируем новые.

@akzhan 15 сен 2011 в 10:44

как вы будете контролировать, что вычисление идет строго в одном процессе?

@kibizoidus 15 сен 2011 в 11:06

По идее, для этого процесс ставит лок и дальше свободно занимается «математикой».

@pro100tak 15 сен 2011 в 10:51

Также, где гарантия что генерация вложится в 5 секунд?

@pro100tak 15 сен 2011 в 10:59

При этом, количество хранимых данных вырастет в ~2 раза (данные + backup)

@kibizoidus 15 сен 2011 в 10:57

Простите, но, возможно, вы иначе переизобрели CAS.

@Darivush 15 сен 2011 в 10:59

Это избавит только от повторного set по ключу, а не от повторных вычислений сохраняемых данных.

@kibizoidus 15 сен 2011 в 11:05

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

@pro100tak 15 сен 2011 в 11:07

Это в основную ветку комментарий? Всё равно — добавлю секцию «Примеры использования».

@kibizoidus 15 сен 2011 в 11:11

Оу, таки да, ошибся ^_^. Вообщем, это к вам.

@pro100tak 15 сен 2011 в 11:19

Добавил

@akzhan 15 сен 2011 в 11:16

Не совсем так, но за пруфлинк спасибо. В моей реализации CAS заменит incr/decr.

@kibizoidus 15 сен 2011 в 11:28

Попробуйте в 10 потоков запустить следующий код на холодном кеше:

$data = MC::get('some_key');

if ($data === FALSE)

{

 sleep(60);

 $data = "test string";

 MC::set('some_key', $data, FALSE, 3600);

}

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

@pro100tak 15 сен 2011 в 11:37

За слив кеша у нас бъют по разным частям тела. И без этой логики это будет равносильно его ооочень скрипучей работе.
Локи — медленно и надо привязывать к этой надстройке, а не к голому мемкешу. Плюс — в каком виде хранить генераторы данных и организовывать очередь выполнения — тоже вопрос. Иначе сервера лягут, но уже от РНР :)

@kibizoidus 15 сен 2011 в 11:41

Сайт-то хоть живой? Можно в личку url? Интересно, что вы там такое монструозное обрабатываете на нескольких серверах.

@pro100tak 15 сен 2011 в 11:56

Отправил. Живее всех живых :) Просто огромный траффик + всякие примочки типа счётчиков, статистика и т.д. 0,5 секунд — бесконечно долгое время, за которое не одна сотня запросов может прийти.

@kibizoidus 15 сен 2011 в 11:44

Ну и в догонку — как вы обновляете кеш при изменении структуры хранения данных?

@pro100tak 15 сен 2011 в 14:07

Сбрасываем нужные ключикию Если данные важны — генерируем данные и просто заменяем.

@Lestat 15 сен 2011 в 14:54

а для тех кто с php не знаком можете плизз пояснить,
вот если 10 потоков запросили данные и их нет в кэше.
первый поток кто дорвался ставит флаг что вычисление идет,
остальные 9 видя этот флаг ждут типа sleep?
когда флаг пропадает, то опять запускается функция получения данных, так?

@pro100tak 15 сен 2011 в 15:22

Сорри, ответил не туда: habrahabr.ru/blogs/php/128275/#comment_4249840

@pro100tak 15 сен 2011 в 15:22

Это очень и очень приблизительный сценарий. В идеале код должен понять, что есть лок и показать пользователю что-то типа «обновление...» на месте, где должно быть значение из мемкеша.
В это время, первый дорвавшийся выставляет лок и обновляет данные. Либо ставит задачу в очередь на обновление и тоже умирает.

@karellen 15 сен 2011 в 16:08

Советую использовать Redis + команду WATCH.

@pro100tak 15 сен 2011 в 16:43

Это уже в ToDo листе. Redis или Mongo — нужен будет файловый кеш, чтобы при падении кеш-сервера/гибели мира/Чаке в датацентре и т.д. случаях кеш поднимался из файла сначала, а потом уже дёргал приложение.

@karellen 15 сен 2011 в 18:07

Так Redis и как низколатентный кэш подходит. При наличии append-only режима и bgrewriteaof он вполне себе заменяет тот же персистентный memcacheDB. А ставите maxmemory-policy allkeys-lru — и у вас получается чистейшей воды memcached, только гораздо функциональнее.

@kashey 15 сен 2011 в 17:45

habrahabr.ru/blogs/webdev/43540/
30 сентября 2008 года.

@pro100tak 15 сен 2011 в 18:45

Я тогда ещё не знал про Хабр :)
Да и у меня пример кода имеется.

@akalend 15 сен 2011 в 17:47

очень похожая тема goo.gl/dStVz

@akalend 15 сен 2011 в 17:53

а знаем ли мы про магию CAS?

@pro100tak 15 сен 2011 в 18:51

Магия CAS тут совершенно ни при чём.
Как справедливо заметил Darivush тут:
Это избавит только от повторного set по ключу, а не от повторных вычислений сохраняемых данных.

@RiderSx 15 сен 2011 в 18:20

Хм, а если перед генерацией данных ставить этот ключ в определенное значение например «in_progress» и проверять при выборке на это значение, если получили это значение значит зацикливаем проверку с шагом в определенное время перепроверяем? Хотя что-то не айс вариант чувствую :)

@VolCh 15 сен 2011 в 18:26

2 (10, 100, ...) процессов одновременно поставят in_progress и начнут генерировать данные одновременно.

@RiderSx 15 сен 2011 в 18:36

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

@pro100tak 15 сен 2011 в 18:53

karellen привёл толковую альтернативу:
Советую использовать Redis + команду WATCH.

@RiderSx 15 сен 2011 в 20:14

Еще из адекватных альтернатив вижу: не устанавливать expires время, а делать все данные бесконечно живущими, а при поступлении инфы, которая должна обновить данные, просто обновлять кэш, причем так, что бы если один процесс, который и принял инфу (он же ее и будет обновлять в кэше), не блокировал доступ к кэшу, а оставлял там старые данные чтоб остальные их могли получить беспрепятственно %) Вобщем нужно что-то вроде транзакций реализовать, тогда воркеры будут получать старые данные до тех пор пока один из них не обновит всю нужную инфу в кэше по требованию так сказать, причем обновить надо сразу и все что затронется, а не постепенно, целостность не нарушится так %)

@VolCh 15 сен 2011 в 20:20

А два процесса, одновременно обновляющие данные под одним ключом? :) Вроде механизм типа транзакций только внешними блокировками с memcache можно реализовать.

@pro100tak 15 сен 2011 в 20:43

Охохо, ежели ничего не удалять — ужасающе быстро закончится место. В моём коде так и делается: один начинает генерацию, а остальные — «кто не успел :)» — получают старые данные.

@VolCh 15 сен 2011 в 20:17

Хотя, наверное, можно намутить что-то вроде

while(1) {
  $res = $mc->add($key . '_in_progress', getmypid());
  if ($res !== FALSE) {
    $value = someHardFunction(); // TODO: DI
    $mc->set($key, $value);
    $mc->delete($key . '_in_progress');
    return $value;
  }
  while($mc->get($key . '_in_progress') !== FALSE) {
    usleep(100);
  }
  $value = $mc->get($key);
  if ($value !== FALSE) {
    return $value;
  }
}

Но, имхо, во-первых, гарантий не даёт, что только один процесс будет обрабатывать ($key. '_in_progress' может удалиться, пока обработка ещё не завершена), во-вторых, не надежно (ситуация «ключ уже существует», «ключ не найден» и, например, «сервер не отвечает» Memcache не позволяет различить вроде как), в-третьих, если someHardFunction() зависнет, то все остальные будут ждать (это кодом можно решить, в принципе). Да и вообще как-то некрасиво :)

@pro100tak 15 сен 2011 в 20:44

Совсем не хочется иметь N висящих потоков. Не к добру это.
P.S. цитата коммента ниже

@VolCh 15 сен 2011 в 21:13

Ну тогда не ожидать удаления $key. '_in_progress', если не получилось его добавить, а возвращать ошибку. Для веба 409-ю (прежде всего для POST, PUT, DELETE) с просьбой повторить запрос позже. Или (для GET-запросов) возвращать текущее состояние кэша со статусом 203.

Или на асинхронное программирование переходить — вроде для него это типичная задача :)

@Lestat 15 сен 2011 в 19:49

> 2 (10, 100, ...) процессов одновременно поставят in_progress и начнут генерировать данные одновременно.

не поставят.
какой первый поток доберется, тот и успеет поставить флаг.
остальные его не получат и просто будут в sleep и проверять каждые N мс,
как только данные сгенерятся, то флаг первый поток снимет, и остальные тут же получат все данные.

@VolCh 15 сен 2011 в 20:21

В memcache cas нет, он только в memcached

@Lestat 16 сен 2011 в 04:52

тут можно без cas, через add.
code.google.com/p/memcached/wiki/FAQ#Emulating_locking_with_the_add_command

@RiderSx 15 сен 2011 в 18:29

и с шагом*

@pro100tak 15 сен 2011 в 18:54

Совсем не хочется иметь N висящих потоков. Не к добру это.

@el777 15 сен 2011 в 19:15

Да, но они хотя бы могут сидеть в sleep не нагружая ни процессоры ни базу.
Альтернатива — отдать ошибку, но лучше ли это?

@remal 15 сен 2011 в 21:02

Они будут жрать оперативу. Так что для высоких нагрузок не очень вариант…

@VolCh 15 сен 2011 в 21:19

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

@pro100tak 15 сен 2011 в 21:32

300 МБ исходников, часть которых завязана на мемкеш и логику работы с ним. Не получится без конфликтов никак — это нормальное поведение. Запрос — нет данных — генерация — в промежутке ещё 100 запросов. Для того и делалось :)

@VolCh 15 сен 2011 в 22:23

А собственно как поведёт себя приложение, когда сразу после старта получит 100 одинаковых запросов? Первый начнёт генерацию, а остальные 99 что вернут? Данных ещё нет же.

P.S.

 return (is_array($value) &&
            isset($value['_dc_life_end']) && isset($value['_dc_cache_time']) &&
            !empty($value['_dc_life_end']) && !empty($value['_dc_cache_time'])
        ) ? TRUE : FALSE;

не слишком избыточно?

 return !empty($value['_dc_life_end']) &&  !empty($value['_dc_cache_time'];

не достаточно будет? Или это отточенная на реальных данных оптимизация?

@pro100tak 15 сен 2011 в 23:00

1. Сценарий запуска пока кеш не разогреется — апокалиптичен по определению. У нас бъют сильно-сильно по всяким выступающим частям тела за слив мемкеша (либо админа за рестарт и т.п. — за что что недоглядел).
2. Максимальная оптимизация, которую тут можно провести:

return (is_array($value) &&
    isset($value['_dc_life_end']) && isset($value['_dc_cache_time']) &&
    !empty($value['_dc_life_end']) && !empty($value['_dc_cache_time'])
);

Ибо должна произвестись ошибка уровня E_NOTICE при использовании одних только empty(). Даже если они по-умолчанию отключены — не значит что их нет :) Да и isset() и empty() — функции, предназначенные совершенно для разных вещей и какбе логично сначала проверить существование элемента массива (если нет — ветка просто обломается и дальше считаться не будет), а потом уже — его пустоту.

@VolCh 15 сен 2011 в 23:04

Упс, забыл, что нотайсы по дефолту выключены, когда тестил — недавно систему переставлял, php.ini ещё не трогал. Без is_array() нотайсы даст и isset()?

@pro100tak 15 сен 2011 в 23:20

Даст, но не во всех случаях.
1. НЕ даст при обращении к строке как к массиву, если индекс меньше длины строки или индекс не цифровой. Изучите вывод, но не забудьте включить E_NOTICE.

error_reporting(2147483647);
$a = 'qwerty';
var_dump(isset($a[2]), $a[2], isset($a[9]), $a[9], isset($a['some_key']), $a['some_key']);

2. НЕ даст при обращении к объекту, который реализует ArrayAccess интерфейс
3. НЕ даст при обращении к числу (в т.ч. и флоату) как к массиву

error_reporting(2147483647);
$a = 5.7;
var_dump(isset($a[2]), $a[2], isset($a[9]), $a[9], isset($a['some_key']), $a['some_key']);

4. НЕ даст при обращении к булевой переменной как к массиву. (Пример поменять самому);
5. ДАСТ ошибку уровня E_USER_ERROR (Fatal в простонародье) обращение к объекту, который не реализует интерфейс ArrayAccess. В пример добавить

$a = new stdClass;

Фууух

@pro100tak 15 сен 2011 в 23:23

6. ДАСТ такую же ошибку как в п. 5 при касте массива в объект

$a = array('a' => 111);
$a = (object)$a;
var_dump(isset($a[0]), $a[0], isset($a[9]), $a[9], isset($a['some_key']), $a['some_key']);

@pro100tak 15 сен 2011 в 18:54

Промах.
Совсем не хочется иметь N висящих потоков. Не к добру это.

@pro100tak 15 сен 2011 в 18:55

Бляяя, извините. Не посчитал точечки — монитор большой.

@f3ath 15 сен 2011 в 19:01

> В документации сказано, что наибольшее время хранения ключа — 30 дней.

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

@alekciy 15 сен 2011 в 22:30

Смирнов еще в 2008 изложил отличный подход к этому велосипеду. "Кэширование и memcached".

@pro100tak 15 сен 2011 в 23:05

Почитал статью по ссылке. Ничего сверхъестественного не нашёл. Почитал вдумчиво. Опять не нашёл. Ткните носом в отличные подходы пожалуйста.

@alekciy 16 сен 2011 в 09:33

Именно, что их как раз и нет. Я к тому и веду, что все уже описанно до нас как минимум с 2008 года.

@pro100tak 16 сен 2011 в 10:59

И да — с 2008 года ничего в софтверном мире не появилось.
Я предложил конкретное решение конкретной проблемы. Решение работающее.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий