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

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

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

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

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



Самая большая сложно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 запросов в секунду?  

Используй ту конкретную реализацию key-value которая не будет вызывать у тебя танцев 

Как только поработаю с этим на практике так сразу смогу тебе ответить более конкретно  Пока таких задач не было и в обозримом будущем не предвидится.


Не-не-не. Тут все не так просто. сессия - это небольшой кусочек данных. Поэтому пару тысяч сессий легко умещаются в файловые кеши (блин, ну не работал я с *nix плотно в качестве админа, но откуда-то висит в памяти цифра в пару мегабайт именно в ассоциации с кешем файловой структуры (не путать с файловым кешем))
Когда речь идет о кешировании гигабайтов.... Чуйка говорит что не все так просто и память должна быть лучше. А чуйке я верю 

А вот со сложностью реализации - понятия не имею. 

Дай пруфлинки (что файловый кеш лучше по скорости чем хранение в памяти при сопоставимой сложности реализации), раз ты с этим сталкивался и работал 

Снова-здорово!  Обновил свой первый пост  


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

Пара пруфлинков в подтверждение применимости файлового кеша:
http://sysoev.ru/nginx/docs/http/ngx_http_...l#fastcgi_cache - используется файловый кеш для fcgi запросов. Замечу, что nginx считается одним из самых быстрых www-серверов.
http://httpd.apache.org/docs/2.2/mod/mod_file_cache.html - в реальных проектах не встречал, но думаю, этот модуль вполне может использоваться и на относительно нагруженных проектах
http://ie2.php.net/manual/en/intro.session.php - дефолтный механизм так же способен работать на высоко нагруженных проектах, но в highload проектах обычно используется memcache, это связано не столько с производительностью, сколько с необходимостью распределенного доступа к ним.

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

В том-то и дело  что распределенность обычно возникает как ответ на требования производителности 

Ладно. И на том спасибо 



Да нет у меня такой конкретной задачи  Я обычно работаю  с сложными (в плане множества функций и внутренних связей) задачами, но к хайлоаду отнести их никак нельзя.
Была бы задача, я давно бы уже нашел решение. А так.... 

Как в анекдоте

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

А как же без индекса быстро удалять устаревшие записи ? Понятно что часть таких записей удалиться при get(). А если идет set() и закончилось свободное место ? Ходить по всем папкам и искать expired-файлы ? ИМХО индекс существенно ускорит удаление устаревших записей.

Запуск раз в час по крону

практически никакой нагрузки не создаст.

И потом, что для вас важнее: быстрая и эффективная работа кеша или быстрое удаление устаревших записей? Скорость второго, по моему, вообще не имеет никакого значения.

Это сообщение отредактировал(а) sTa1kEr - 6.12.2009, 15:08

Тогда и для винды надо команду не забыть.


Важнее конечно скорость. Но место под кеш может закончится раньше, чем через час. Допустим через пол часа. Получается остальные полчаса ничего записывать не будем ? Или принудительно запускать очистку ? По сути дела, при куче файлов (например 20 млн.) это займет значительное время. Лучше удалить несколько самых старых файлов, освободив только необходимое свободное место. А тут без индекса не обойдешься.

Вообще, в принципе я согласен, что это все какие-то заморочки. Лучше проследить сколько кэша набирается в час пик. Задать под кэш в 1,5 раза больше места и не париться с индексами. Это все же ближе к жизни.

Пфф. Зачем? Запомните: в highload проектах универсальность совершенно не нужна, в highload систему настраивают под проект, а не проект под систему(ы). 

Все вышесказанное мной в этой теме про файловый кеш относится к *nix, насколько будет эффективен файловый кеш в Windows я понятия не иммею.


Не может.
Во первых, перед тем как вести разработку механизма кеширование, вы должны проанализировать какого примерно объема в нем будут храниться данные и сколько нужно выделить памяти.
Во вторых. Идеология кеша такова, что он не может гарантировать 100% сохранность данных. Любые данные из кеша могут быть удалены в любой момент времени.
В третьих. Если у вас вообще возникает проблема нехватки памяти, то скорее всего принудительная очистка кеша от старых записей даст лишь кратковременный результат. Тут уже надо думать об увеличении памяти или создании дополнительного хранилища.


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

Это сообщение отредактировал(а) sTa1kEr - 6.12.2009, 16:01

sTa1kEr, да не кому вопросы уточняющие по заданию задавать, вот и мудрю.   

Это сообщение отредактировал(а) webtech - 6.12.2009, 16:18

webtech, 
я все понимаю, но на мой взгляд это задание надо было закончить еще 4-6 дней назад.

Не думаю что от тебя хотели получить вылизанное решение - готовое к применению "искаропки" в промышленных масштабах.

Simpliest, да не, ты что, я не все это время только этим и занимаюсь  Думаю суммарное время не превысит 2-3 рабочих дней.

ага самый простой и самый бестолковый, про размер кластера забываете господа, в *nix не знаю, в винде по умолчанию кластер = 4 кб, 
т.е. у вас может быть записано одно число в файлик (количество юзеров онлайн например)  - а занимать он будет все равно 4 килобайт. 
Даже при заполнении файлов 70% в среднем на миллионе файлов потери будут астрономические. 
Вот эта строка для наглядности:
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 
120 байт весит, т.е. в стандартный кластер можно еще 34 таких куска запихнуть.
Не уверен, но сдается, что на серверах кластер еще больше для ускорения обращения к файлам.

они не имеют значения для кеша.

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

      

1кБ не использованный * 1 000 000 файликов =  грубо 1 ГБ
 меня бы убили 

MyDarkSide, знаете такую поговорку "промолчи, глядишь за умного сойдешь"?

Во первых, если мы возьмем reiserfs, то в ней более гибкая структура позволяющая размещать в одном блоке части различных фалов. Более того в ней очень маленькие файлы хранятся в своем inode, что означает значительное увеличение производительности при чтении маленьких файлов(т.к. вовсе не придется читать ни одного блока, сам файл будет получен вместе с ее метаданными) и еще более эффективное использование дискового пространства.
А во вторых


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

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

Вы не путайте, всякие "интернет магазины" и highload проекты - это два совершенно разных уровня задач.

Добавлено через 3 минуты и 57 секунд
Пруфлинк по reiserfs http://www.citforum.ru/operating_systems/l...bins/fs01.shtml

человек спрашивает про тестовое задание напомню.
Представляю диалог:
- Вы сделали кэш?
- Да я предлагаю писать каждую переменную  в свой файлик
- А как насчет эффективности использования и дефрагментированности диска ? 
- А не х.й! мы вам другую ось на сервер поставим! 

просто нет слов


Это сообщение отредактировал(а) MoLeX - 8.12.2009, 13:01

MyDarkSide, 
еще раз повторяю. для работы в качестве кеша объем неэффективноиспользуемого диска не имеет решающего значения.

Пусть там теряется хоть 3.7кб(90%) места на каждом файле.

Все эти файлы временные - нам важно насколько быстро мы сможем прочитать нужный файл,а не как много информации мы сохраним.

 

Цитата(MyDarkSide )

пните репутацию, а то 1,5 года уже новичок

пнули уже   

Добавлено через 1 минуту и 30 секунд

!  MoLeX

Модератор: MyDarkSide, не наглеем и не грубим

Это сообщение отредактировал(а) MoLeX - 8.12.2009, 13:02

MoLeX, грубить начал не я ! а мне на простое и вполне корректное замечание!

Добавлено через 1 минуту и 40 секунд


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

Добавлено через 9 минут и 37 секунд
MoLeX, 
ты не прав,  
более опытный пользователь форума начал хамить, вместо того чтобы показывать пример уважительного отношения к чужому мнению, а карму снизили новичку.  

  какие в задницу затраты?

Парень, месяц работы неплохого специалиста стоит примерно как 2-4 дешевых пролианта.
А хорошего вдвое больше.

Простейший кеш на файлах делается за пару дней.
Оптимизация займет пару недель.

винт 1Тб (не SAS) = от 100 у.е.
недорогой сервер 1000-2000 у.е.
2 недели времени 1500-2000 .у.е 

Вот считай сколько мы сэкономили, а сколько ты просрал на спичках.

Простой кеш
200 у.е работы даст нам фактически + 1 сервер (1000 у.е.)

Оптимизация кеша (с 10% эффективности винта до 100%)
еще 2000 у.е. работы дадут нам 100*0,9 = 90 у.е прибыли.... на каждый винт
Чтобы это хотя бы окупилось нужно чтобы мы использовали 22 жестких диска.
Чтобы получить такое же соотношение прибыль/затраты надо 110 жестких дисков (110 ТБ)

Для справки, у facebook, как мне помнится, под мемкеш было выделено около 1ТБ.

Simpliest, обращаемкя снова к топикстартеру - у него тестовое задание программиста. В реальной ситуации, конечно ваши аргументы убедительны. 
Но человек будет проходить собеседование на должность программиста, а вы упорно предлагаете ему использовать простейшее с т.зр. программирования решение - а всю оптимизацию переложить на админов.
Вот вы кадровик или вас позвали на собеседование потестить кандидата в программисты - а кандидат принес простейшениее решение ( file_get_contents()  / file_put_contents() )  а самые трудные проблемы свалил  на админа, вы возьмете такого на работу ? как вообще будете оценивать его программерские способности. Не будет подмывать спросить "А сами можете реализовать по-интереснее ?"

Топикстартеру советую, продумать решение все-таки по-сложнее по-интереснее, которое показало бы что у вас есть алгоритимические способности и идти на собеседование с ним. А в голове держать решения попроще например от Simpliest.  

У ТС абсолютно реальная ситуация, где его берут на реальную работу, для разработки реального(ых) высоконагруженного(ых) проекта(ов).


Конструктор понимает, что достиг совершенства не в тот момент, когда к конструкции уже нечего добавить, а когда из нее уже нечего убрать (с) Антуан де Сент-Экзюпери


Это полная ерунда. Реализации "по-интересные" работодателя совершенно не интересуют. Его интересуют решения эффективные, стабильные и легкие в сопровождении и доработке. 

Запомните одну вещь: Хороший программист - это вовсе не тот кто умеет быстро набивать тысячи строк всякого "интересного" кода. А тот, кто умеет думать и четко понимает смысл каждой написанной им строчки кода.

PS На сисадмина ничего не взваливается. Когда сисадмин и программист работают над задачей вместе, то это называется "работа в команде". И потом, что бы выполнить mkreiserfs /dev/sdx не нужно иметь семи пядей во лбу  

Добавлено @ 00:02

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

Это сообщение отредактировал(а) sTa1kEr - 10.12.2009, 09:30

sTa1kEr, предлагаю прекратить оффтопик, чтобы мне не занали карму в минус бесконечность