Приветствую !

Обращаюсь с просьбой помочь. Я устраиваюсь на новую работу. А там тестовое задание. 

Сразу разделяю Ваше негодование. Тестовое - значит сам должен сделать. Но я ни в коем случае не прошу его за меня решать или что-либо подобное.

Просто не могу просечь "фишку" задания.  То есть что же хочет проверить работодатель. Может хотят увидеть развитую систему классов ? А может грамотную алгоритмизацию ? А может еще что ? Надеюсь кто-то из более опытных людей сможет что-либо подсказать.

Вот, собственно, и само задание:



Самая большая сложноcть: как это сделать в файловой системе. memcached - это по сути дела большая распределенная хэш-табличка. Где есть 2 основных метода: get(key) и set(key, value). В случае файлов, у меня всё утыкается в изменение/удаление данных. Допустим мы создали три записи:

set('key1', '1000');
set('key2', '1000');
set('key3', '1000');

Это все хранится в файле. Допустим теперь нам надо изменить значение для ключа 'key2' и новое значение будет длиннее старого. Например сделать:

set('key2', '99999999');

Т.к. мы работаем с файлами, то мы не можем просто "раздвинуть" границы для хранения нового значения. Или я ошибаюсь ?

По сути дела тут единственный выход - взять из файла всё, что находится до 'key2', скопировать в tmp-файл, дописать в него новое значение 'key2', затем дописать остаток из исходного файла и заменить исходный файл. Ну и стереть tmp-файл. 

Только с учетом объемов ("миллионы штук"), у нас могут появиться довольно-таки здоровенные файлы в несколько сотен метров, с которыми будут проблемы. Не думаю, что разумно двигать сотни мегабайт, ради того, чтобы вставить лишние сто килобайт в середину файла. Это не хорошо с точки зрения производительности. Или я ошибаюсь ? 

Кроме того, если у нас под кеш выделен допустим 1 гиг. Мы его забили на 1000 метров. Теперь нам надо в эти 1000 метров запихать 100КБ куда-нибудь в середину. Как мы создадим tmp-файл на 1000 метров ? 1000+1000 = 2000, а это уже явно больше выделенного 1 гигабайта.

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

Вариант "создавать по 1 файлу на каждое значение кеша" - тоже не вариант. Несколько миллионов файлов ради кеша - явно не дело.

Если считать, что я тут нигде не ошибся и все верно. Тогда по заданию вообще придется писать что-то вроде своего file-based DB-engine (типа sqlite). С грамотным разделением записей по файлам и всевозможными оптимизациями. Но это ж как-то слишком мастабно. Может я слишком сильно заморачиваюсь ?

Спасибо за то, что дочитали до конца и за любую помощь.

Вы таки ошибаетесь. 

Я конечно понимаю что кушать хочется всем... 
Но почему бы эти вопросы не задать работодателю?  (если уж не хотите посмотреть мануал)
Если им требуется "специфичный" специалист, то даже "обойдя" с помощью форума тестовое задание в процессе работы станет вполне очевидно что вы не подходите им. И вас уволят. Зачем доводить до конфликта?

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

Просто поймите  - это не диктант в школе 

P.S. Безотносительно возможности "раздвигать" содержимое файла 
Я бы каждый ключ(или некоторую небольшую группу ключей) хранил в своем файле. Это проще в реализации.


Открою секрет. У меня без всякого кеша 350к файлов на почти голой домашней машине.

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

Simpliest, спасибо за такой развернутый ответ.

 Если можно - чуть конкретнее, что вы тут подразумеваете. Есть способы просто "раздвинуть" файл ? Без таскания кусков ?

 Подозреваю что ответ работодателя будет: "делайте как понимаете". Про мануал: много чего уже перечитал, и по теме memcached и по файловым системам. Вы какой мануал имеете ввиду ?


Вот точно чего не хочется - это "обходить" тестовое задание и потом вылетать с должности с конфликтом и по незнанию. Просто стараюсь найти верное направление.


Очень надеюсь на такое адекватное отношение =) Но как предугадать кто будет проверять задание и какой у него подход   

 
Безусловно проще. Вообще уже несколько голосов именно за такой подход. Просто пока не хватало опыта это понять. Нужен был свежий незамыленный взгляд со стороны =)


350k не 100 млн.


А что поделаешь, если в задании "Кoличecтвo хрaнимых зaписeй, миллиoны штук." и механизм "пригoдный для иcпoльзoвaния нa выcoкoнaгружeнных прoeктaх".

Просто раздвинуть нельзя. Придется перезаписывать ВЕСЬ файл в любом случае.

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

Файл должен быть небольшим, читаем файл целиком 
$data = file()
меняем/добавляем/удаляем - и перезаписываем файл.
поэтому в таком случае мы можем вставлять строки произвольного размера

Миллионы файлов тянут максимум на намек об ограничениях числа файлов в одном каталоге. 
Поэтому нужно просто предусмотреть 3 уровня вложенности для самих файлов
Даже при ограничении в всего 2000 файлов на каталог мы будем иметь максимальную емкость 36^3 * 2000 = 93млн
ключ 5e8ff9bf55ba3508199d22e984129be6
будет хранится в
/5/e/8/ff9bf55ba3508199d22e984129be6


Сдается мне что относится это не к методике хранения.
А к самой работе. Т.е. нужен демон что ли. Или я опять все усложняю и твой работодатель просто путает memcache и memcachedb
Хм. Хотя быть может просто не знает о key-value хранилищах...

Добавлено через 48 секунд
Фу, короче, ты меня запутал. Проще всего уточнить у работодателя, чем гадать на кофейной гуще. Слишком много вариантов.

Simpliest, спасибо, что тоже заморочился над проблемой    Что-то для себя я почерпнул.

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

Структура директорий должна быть такой, как привел Simpliest, т.е. несколько уровней (не обязательно 3, можно и больше, но для миллиона записей хватит и 3х) основанных на MD5 ключа. При получении значения, по ключу будет определятся полный путь к файлу, а затем проверяться на его актуальность. Если mtime файла + 1 час меньше текущего времени, то удаляем файл и возвращаем null (можно так же по крону раз в несколько часов удалять "протухшие" файлы, в *nix это можно сделать одной командой)

Что-же касается highload проектов.  При наличии N-ого количества шустрых винтов, подмонтированных в различные директории хранилища, и достаточного количества оперативной памяти на сервере - данная схема будет даже быстрее memcache. Т.ч. работодатель вас не обманул, такой механизм еще как может быть пригоден на высоконагруженных проектах   

PS Вы случайно не к нам устраиваетесь на работу?  

UPD. Что бы не было недопониманий в будущем. Я ни в коем случае не утверждаю, что файловый кеш - замена кешу в памяти. Основная мысль в том, что файловое кеширование совсем не такое медленное, как думают многие (а при определенных условиях оно может быть даже быстрее memcache (см. тест ниже)), плюс оно предельно простое и стабильное, а значит более чем применимо в highload. 

Это сообщение отредактировал(а) sTa1kEr - 4.12.2009, 11:25

Я может что-то путаю. Но RAM быстрее чем чтение с диска. Memcache хранит все в памяти.

Каким образом N-e количество шустрых винтов обгонят RAM?

Добавлено через 3 минуты и 48 секунд

Есть нюанс - возможно есть смысл хранить данные все же небольшими блоками.

Часто бывает требуются подряд несколько значений и пакетное чтение несколько ускорит работу.

в swap'e?

В каком свапе? В свап оно не должно попадать ни в коем случае иначе толку от него будет ноль целых шиш десятых.

Добавлено через 2 минуты и 50 секунд
Я так понял посыл  sTa1kEr, что 100Gb RAM выделенные под memcache будут медленее, чем скажем 4x20Gb SAS HDD + 20GB RAM

Нет, я не имел ввиду SAS. Собственно жесткие диски тут большой роли не играют, основная суть в другом.


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

Собственно можешь провести простой тестик:




Добавлено через 3 минуты и 22 секунды

Тогда придется хранить значения в каком-либо структурированном вместе с информацией об expire и каждый раз парсить файл. Кроме того как ты узнаешь какие именно значения надо поместить в один блок, а какие нет?

Добавлено через 7 минут и 39 секунд
Только сейчас заметил, что во втором тесте 10 запросов не прошло... Ну да это не должно сильно влиять на результаты.
Вероятно просто в memcache был достигнут лимит коннектов (что, кстати, в случае с чтением из файла полностью исключено)

В тетсте с memcache настолько ужасные результаты из-за того, что сеть не слишком шустрая у меня... На продакшене, конечно-же, разница будет значительно меньше. 

Попробовал поднять memcache на locаlhost

Теперь результаты практически идентичны, но на продакшене обычно не бывает, что бы memcahce висел на www серверах - это бессмысленно. 

Тю.

Во-первых, насколько я знаю, loopback быстрее, чем коннект к удаленному серверу. Что собственно и показали твои тесты.

Во-вторых, ты и сам сказал

И, насколько я знаю, это делается по причине наличия фермы с единым кешем.

Кеш на файлах - будет работать только для одного сервера. Который будет заведомо медленнее фермы из таких же серверов.

И еще меня смущает вот это

Я не настолько хорошо знаком с *nix, поэтому не могу сказать есть ли какие-то ограничения памяти под дисковый кеш.

P.S. Если речь идет об одной машине, вместо memcache можно попробовать задействовать apc/eaccelerator
они вроде имеют базовый функционал для key-value хранилища.

Вся соль мемкеша в распределенном доступе к его хранилищу, на localhost'е его держать большого смысла нету. На localhost'е даже eaccelerator не нужен, можно просто тупо все в shared memory на прямую пихать


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


Да можно все что угодно, но у ТС в задании речь про файловое хранилище и его применение в высоконагруженных проектах.

Добавлено @ 18:09

Я полагаю, что есть, но в *nix практически все настраиваемо. 

Это сообщение отредактировал(а) sTa1kEr - 3.12.2009, 18:10

Вот, а Баба-Яга всеравно против 

Если памяти достаточно, то как справедливо ты заметил почему не использовать shared memory?
Зачем эти танцы с бубном в виде файлового кеша?

А если памяти недостаточно... то скорость оного(файлового хранилища) будет не такой радужной.

Или я что-то не понимаю? 

Как раз с shared memory будут танцы с бубном (нужно выделять сегменты, следить что бы данные поместились в сегмент, etc. кроме того лимит на shared memory жестко ограничен настройками ядра), а файловый кеш прост, как два пальца ...   fread(id), fwrite(id, val), filemtime(id) - вот и вся любовь  

Ты думаешь почему PHP  сессии по дефолту в файлах хранит (кстати, с точно такой же многоуровневой структурой директорий и точно так так же с ключем в качестве имени файла), а не в shared memory или еще каком-нить хитром хранилище?

По твоему nginx предназначен для высоконагруженных проектов? А как ты думаешь какой способом кеширования fcgi он использует для достижения производительности 50000 запросов в секунду?