Обращаюсь с просьбой помочь. Я устраиваюсь на новую работу. А там тестовое задание.
Сразу разделяю Ваше негодование. Тестовое — значит сам должен сделать. Но я ни в коем случае не прошу его за меня решать или что-либо подобное.
Просто не могу просечь "фишку" задания. То есть что же хочет проверить работодатель. Может хотят увидеть развитую систему классов ? А может грамотную алгоритмизацию ? А может еще что ? Надеюсь кто-то из более опытных людей сможет что-либо подсказать.
Вот, собственно, и само задание:
Напишитe клаcc (клaccы) нa php, рeaлизующий мeхaнизм хрaнeния дaнных в cтилe memcached, пригoдный для иcпoльзoвaния нa выcoкoнaгружeнных прoeктaх. Ключ, для прocтoты, цeлoчислeнный. Кoличecтвo хрaнимых зaписeй, миллиoны штук. Рeaлизуйтe хрaнeниe дaнных в фaйлoвoй систeмe. Рeaлизуйтe хрaнeниe дaнных в sql бaзe. Рeaлизуйтe мeхaнизм oчистки кeшa от уcтaрeвших зaпиceй. Тoчнocть уcтaрeвaния 1 чаc.
Самая большая сложноcть: как это сделать в файловой системе. memcached — это по сути дела большая распределенная хэш-табличка. Где есть 2 основных метода: get(key) и set(key, value). В случае файлов, у меня всё утыкается в изменение/удаление данных. Допустим мы создали три записи:
Это все хранится в файле. Допустим теперь нам надо изменить значение для ключа 'key2' и новое значение будет длиннее старого. Например сделать:
set('key2', '99999999');
Т.к. мы работаем с файлами, то мы не можем просто "раздвинуть" границы для хранения нового значения. Или я ошибаюсь ?
По сути дела тут единственный выход — взять из файла всё, что находится до 'key2', скопировать в tmp-файл, дописать в него новое значение 'key2', затем дописать остаток из исходного файла и заменить исходный файл. Ну и стереть tmp-файл.
Только с учетом объемов ("миллионы штук"), у нас могут появиться довольно-таки здоровенные файлы в несколько сотен метров, с которыми будут проблемы. Не думаю, что разумно двигать сотни мегабайт, ради того, чтобы вставить лишние сто килобайт в середину файла. Это не хорошо с точки зрения производительности. Или я ошибаюсь ?
Кроме того, если у нас под кеш выделен допустим 1 гиг. Мы его забили на 1000 метров. Теперь нам надо в эти 1000 метров запихать 100КБ куда-нибудь в середину. Как мы создадим tmp-файл на 1000 метров ? 1000+1000 = 2000, а это уже явно больше выделенного 1 гигабайта.
С удалением та же беда. Нельзя же просто выкинуть кусок из файла. Опять таки придется пересохранять.
Вариант "создавать по 1 файлу на каждое значение кеша" — тоже не вариант. Несколько миллионов файлов ради кеша — явно не дело.
Если считать, что я тут нигде не ошибся и все верно. Тогда по заданию вообще придется писать что-то вроде своего file-based DB-engine (типа sqlite). С грамотным разделением записей по файлам и всевозможными оптимизациями. Но это ж как-то слишком мастабно. Может я слишком сильно заморачиваюсь ?
Спасибо за то, что дочитали до конца и за любую помощь.
Здравствуйте, Holms, Вы писали:
H>Вам же ясно сказали, "Рeaлизуйтe хрaнeниe дaнных в sql бaзe", для чего вам нужны файлы???
H>Видно работодателя интересует знаете ли вы что такое индексы для БД, как правильно подключатся к БД и вытаскивать результаты.
H>Удачи.
Как сделать на основе БД — это еще понятно. Просто необходимо реализовать и на файлах, и на БД:
W>
Напишитe клаcc (клaccы) нa php, рeaлизующий мeхaнизм хрaнeния дaнных в cтилe memcached, пригoдный для иcпoльзoвaния нa выcoкoнaгружeнных прoeктaх. Ключ, для прocтoты, цeлoчислeнный. Кoличecтвo хрaнимых зaписeй, миллиoны штук. Рeaлизуйтe хрaнeниe дaнных в фaйлoвoй систeмe. Рeaлизуйтe хрaнeниe дaнных в sql бaзe. Рeaлизуйтe мeхaнизм oчистки кeшa от уcтaрeвших зaпиceй. Тoчнocть уcтaрeвaния 1 чаc.
Здравствуйте, Mikhail Polykovsky, Вы писали:
W>>Вариант "создавать по 1 файлу на каждое значение кеша" — тоже не вариант. Несколько миллионов файлов ради кеша — явно не дело.
MP>Почему нет? Если их раскладывать по вложенным каталогам, может не все так фатально будет. Проведите эксперимент.
Хм, уже 3 голоса (с разных форумов) за такую систему. =) Сейчас буду ставить эксперимент. Спасибо
Здравствуйте, webtech, Вы писали:
W>Здравствуйте, gandjustas, Вы писали:
G>>Вероятнее всего да.
G>>Я бы предложил по файлу на запись, в качестве имени файла — ключ.
W>Хм, уже 3 голоса (с разных форумов) за такую систему. =) Сейчас буду ставить эксперимент. Спасибо
Если время поиска файла по имени в каталоге довольно длительное, то можно понаделать подкаталоги с именами от хеша ключа, например остаток от деления на степень двойки для числового ключа.
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, webtech, Вы писали:
W>>Здравствуйте, gandjustas, Вы писали:
G>>>Вероятнее всего да.
G>>>Я бы предложил по файлу на запись, в качестве имени файла — ключ.
W>>Хм, уже 3 голоса (с разных форумов) за такую систему. =) Сейчас буду ставить эксперимент. Спасибо
G>Если время поиска файла по имени в каталоге довольно длительное, то можно понаделать подкаталоги с именами от хеша ключа, например остаток от деления на степень двойки для числового ключа.
Здесь лучше сделать несколько вложенных каталогов, чтобы не получить слишком большое кол-во каталогов в одном месте, что тоже вредно.
Но все равно, миллион мелких файлов = в лучшем случае 4 гига при Allocation unit size в 4кб.
Re[3]: memcached на файлах
От:
Аноним
Дата:
30.11.09 14:24
Оценка:
Здравствуйте, webtech, Вы писали:
W>Хм, уже 3 голоса (с разных форумов) за такую систему. =) Сейчас буду ставить эксперимент. Спасибо
Прибавлю свой, четвёртый
Пусть путь к записи c id = 4395623781 выглядит так: 4/3/9/5/6/2/3/7/8/1.bin или так: 43/95/62/37/81.bin.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, webtech, Вы писали:
W>>Хм, уже 3 голоса (с разных форумов) за такую систему. =) Сейчас буду ставить эксперимент. Спасибо
А>Прибавлю свой, четвёртый А>Пусть путь к записи c id = 4395623781 выглядит так: 4/3/9/5/6/2/3/7/8/1.bin или так: 43/95/62/37/81.bin.
Здравствуйте, webtech, Вы писали:
w> Спасибо за то, что дочитали до конца и за любую помощь.
Про вложенные директории уже сказали. Хочется добавить, что увлекаться тоже не стоит — двух уровней вложенности будет более чем достаточно. Например, первый уровень 0..F, второй 00..FF — при 1 млн ключей и их равномерном распределении получаем ~245 файлов в директории — с этим файловая система справится левой пяткой. Равномерности распределения можно попробовать достичь вычисляя директорию в "обратную" сторону для ключа. Например, ключ 1000 = 0x000003E8 = /8/E3/00000.tmp. Так же, эти параметры можно сделать задаваемыми в конфигурации.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, webtech, Вы писали:
W>>Оказывается самый оптимальный путь может быть другим: http://forum.sources.ru/index.php?showtopic=174102
А>Совсем оптимальный путь зависит от файловой системы.
В идеале: прогнать бы серию тестов на самое оптимальное распределение файлов/папок и выяснить самое подходящее для каждой FS. Но это как-то слишком
Здравствуйте, Anton Batenev, Вы писали:
AB>Здравствуйте, webtech, Вы писали:
w>> Спасибо за то, что дочитали до конца и за любую помощь.
AB>Про вложенные директории уже сказали. Хочется добавить, что увлекаться тоже не стоит — двух уровней вложенности будет более чем достаточно. Например, первый уровень 0..F, второй 00..FF — при 1 млн ключей и их равномерном распределении получаем ~245 файлов в директории — с этим файловая система справится левой пяткой. Равномерности распределения можно попробовать достичь вычисляя директорию в "обратную" сторону для ключа. Например, ключ 1000 = 0x000003E8 = /8/E3/00000.tmp. Так же, эти параметры можно сделать задаваемыми в конфигурации.
Постараюсь по разному попробовать и потом запостить здесь результаты. Хотя это и малообъективно.
Re[7]: memcached на файлах
От:
Аноним
Дата:
30.11.09 17:09
Оценка:
Здравствуйте, webtech, Вы писали:
W>В идеале: прогнать бы серию тестов на самое оптимальное распределение файлов/папок и выяснить самое подходящее для каждой FS. Но это как-то слишком
