Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 95
очень интересно :) жду версии для osx
«севера кеша»
что ты имеешь против кифира?! Оо :D
Как хорошо. Будет что посмотреть в процессе вашей работы. Давно хотел понаблюдать за процессом разработки подобного проекта.
Не совсем понятно, зачем явно вводить длину ключа (и данных), если их можно получить из самой строки?
Что происходит, если введена неверная длина?
Что происходит, если введена неверная длина?
Эм… «Извините, был напуган» — забыл про сетевую составляющую :)
Если пишем/читаем данные по сети, то имеет смысл. Но вопрос «что будет, если передана неверная длина» остаётся открытым :)
Если пишем/читаем данные по сети, то имеет смысл. Но вопрос «что будет, если передана неверная длина» остаётся открытым :)
Если передана слишком большая длина, то сервер будет ждать пока не придет достаточное число байт. Если слишком маленькая — то прочитает не все, а остаток интерпретирует как следующий запрос.
\n же есть для этого — жди символа и не дергайся.
А если этот символ в данных попался?
Для этого существует ограничение, что можно класть в данные — экранируйте.
Есть отличная идея – можно передавать заранее длину передаваемых байт, сразу меньше работы серверу – не надо каждый приходящий символ проверять.
Хорошо, а когда вы передаете команду, которая заканчивается \n? Ведь сервер от ваc в этом случае ловит именно строку, неизвестной длины, оканчивающуюся \n. Я ведь не настаиваю, что это верное решение, просто оно используется.
Понятно, что бинарный протокол вообще эффективнее — команду одним байтом, длину ключа, длину данных, все отлично работает в tyrrant и многих других. И в этом вот случае серверу еще меньше работы: )
Понятно, что бинарный протокол вообще эффективнее — команду одним байтом, длину ключа, длину данных, все отлично работает в tyrrant и многих других. И в этом вот случае серверу еще меньше работы: )
Экранирование — это порядочный оверхед. Если ты проверяешь, не экранирован ли \n — это неплохая работа для сервера. А ожидание \n однократное — не такая уж и морока.
Ну в общем хз, я не вижу проблем с этим вообще. В редисе точно такое же решение используется, и мне кажется вполне разумным.
Ну в общем хз, я не вижу проблем с этим вообще. В редисе точно такое же решение используется, и мне кажется вполне разумным.
Классное начинание, здорово. Все-таки я сторонник комментированного кода, особенно если этот код предполагается на чтение публике.
А почему не просто хэшом, а деревом? Создать, например, таблицу на 4М и более элементов. В большинстве случаев будет работать значительно быстрее чем дерево. Когда элементов будет меньше чем в хэш-таблице и при относительно равном распределении ключей, вставка и выборка будет происходить за O(1) а не за O(log(n)). Как способ для блокировок, можно все пространство ключей разбить на n частей и лочить только соответствующую часть, а не все.
Такая таблица очень маленькая на мой взгляд, будет много колизий и оттуда много цепочек. При 10млн элементов максимальная глубина дерева была 52, md5 очень крутой.
А при чем тут md5? Чтоб считать индекс от строки? Можно взять проще, да хоть тупо остаток от деления суммы всех символов в ключе на размер таблицы. А в дереве вы сравниваете строки просто или как? Ну можно сделать на 10М и на 20М таблицу — разницы нет, такого размера, чтобы коллизий не было. А при добавлении/удаленнии в дерево, разве не происходит его перебалансировки?
То есть тут какая штука. Либо создавать огромную таблицу, тратить память на нее и иметь мало колизий, либо мелкую таблицу, скорость которой в итоге может быть меньше бинарного дерева.
И еще как вариант не изобретать своего протокола, а взять HTTP или добавить его поддержку. Если считывание и запись в сокеты происходит в отдельных потоках, зачем тогда неблокирующие? Или у вас там очереди на отправку, примем и обработку в каждом потоке и при неудачном чтении/записи происходит переход к poll-у?
HTTP избыточен, его разбор займет время. А тут важна скорость.
Каждый поток имеет свою очередь сообщений и может корректно выключиться как только его попросит менеджер потоков.
Каждый поток имеет свою очередь сообщений и может корректно выключиться как только его попросит менеджер потоков.
HTTP это запрос, ответ, закрыли сокет. Это время — лучше протокол с постоянным соединением, как и поступают с memcache зачастую. Ну а уж разбор строк это действительно медленная операция.
Хорошая идея, добавил таск github.com/mdevils/encached/issues/#issue/3
Resolved.
А как память считать можно обертку тупо написать вокруг malloc и free, ну или как там оно в паскале называется. И в некоторый счетчик добавлять/вычитать чиселки через mutex, конечно. И в некоторых точках его выводить. Это самый простой вариант.
Прочитал mutex, там 0, пишущий поток решил что ему можно писать) Сразу после того как первый прочитал, второй поток тоже прочитал 0, тоже решил что ему можно писать. Оба стали писать, поставив единичку)
А так, не только в этом проблема. Непонятно что лочить при удалении, например. В бинарном дереве удаление не очень-то и простая команда.
А так, не только в этом проблема. Непонятно что лочить при удалении, например. В бинарном дереве удаление не очень-то и простая команда.
mutex на то и mutual exclusion, что пока один из него не выйдет — никто другой не войдет.
В деревьях можно не удалять, а помечать на удаление. А удалять отдельно, в idle.
В деревьях можно не удалять, а помечать на удаление. А удалять отдельно, в idle.
Вот про то что не войдет — это плохо. Представь сервер кеша на посещаемом сайте. Сонти запросов в секунду для популярных ключей. Все потоки должны иметь возможность читать одновременно данные.
Как вариант сделать массив из n деревьев, каждое со своим rwlock-ом. То есть при запроси put считаем индекс в этом от ключа массиве, лочим на запись все дерево, записываем элемент, олочиваем. А при чтении сответственно лочим на чтение. уменьшение столкновений в n-раз практически.
> Буду благодарен если подскажете хороший способ организации потоко-безопасной хеш-таблицы.
Запись в хеш-таблицы обычно атомарна (пишется сразу машинное слово) и блокировка не требуется.
Запись в хеш-таблицы обычно атомарна (пишется сразу машинное слово) и блокировка не требуется.
Не совсем. Во-первых колизии (и связанный список из-за них). Во-вторых команды APPEND, INC.
Тогда получается, проблема не в хеш-таблице, а в связанном списке. И вариантов немного — либо приводить все к атомарности, либо классические блокировки (весь список или отдельную запись).
Проблема с APPEND/INC актуальна так же и для хештаблицы. Лочить надо. Я выбрал пока бинарное дерево для хэштаблицы (минимум памяти при приемлемой скорости). Непонятно что лочить при удалении, например. В бинарном дереве удаление не очень-то и простая команда.
Откуда в хеш-таблице APPEND/INC? Это же не динамический массив. А если делать динамические хеш-таблицы, то придется каждый раз все дерево перестраивать.
Я имею ввиду, что помимо операции присвоения значения по ключу, нужна еще операция добавления к значению. Она должна выглядеть как атомарная для сервера.
Там не так все просто. У процессоров имеется кеш, и изменения могут быть не залиты в основную память, что создаст проблемы при наличии нескольких процессоров.
Собственно, не вижу смысла усложнять/добавлять проблем заданием длины ключа/данных.
Достаточно кешировать полученные из сокета данные, и парсить по концам строк, т.е.:
PUT\r\n
hello\r\n
Hello world!\r\n
Или, если есть уговор, что строка ключа не может содержать пробелов, так поместить в одну строку:
PUT hello Hello, world!\r\n
Или, если с пробелами:
PUT hello with space\r\n
Hello, world!
Так и парсить совсем несложно (читаем первую строку из буфера путем поиска \r\n, далее парсим ее — выделяем первую команду (элемент до первого пробела), выделяем ключ(до второго пробела/до \r\n), и далее — данные.
Но собственно я так и не понял. Зачем это все нужно :)?
Достаточно кешировать полученные из сокета данные, и парсить по концам строк, т.е.:
PUT\r\n
hello\r\n
Hello world!\r\n
Или, если есть уговор, что строка ключа не может содержать пробелов, так поместить в одну строку:
PUT hello Hello, world!\r\n
Или, если с пробелами:
PUT hello with space\r\n
Hello, world!
Так и парсить совсем несложно (читаем первую строку из буфера путем поиска \r\n, далее парсим ее — выделяем первую команду (элемент до первого пробела), выделяем ключ(до второго пробела/до \r\n), и далее — данные.
Но собственно я так и не понял. Зачем это все нужно :)?
Ключ может содержать в себе любые символы, в том числе и \r\n. Точно также и значение.
Зачем нужны кеширующие серверы можно почитать здесь: ru.wikipedia.org/wiki/Memcached
Зачем нужны кеширующие серверы можно почитать здесь: ru.wikipedia.org/wiki/Memcached
Ололо. А нафига? Есть memcached который профессионально написан на С++, а не на языке студентов (Paskal).
К memcached есть куча драйверов, middleware, и все знают как с ним работать. Фактически это уже стандарт.
Что вы можете противопоставить ему? Текстовый протокол бинарному?
Какие функции вы хотите добавлять? CAS там и так есть.
К memcached есть куча драйверов, middleware, и все знают как с ним работать. Фактически это уже стандарт.
Что вы можете противопоставить ему? Текстовый протокол бинарному?
Какие функции вы хотите добавлять? CAS там и так есть.
Трололо. А нафига вообще жить? Ведь всем известно, чем это закончится.
В топике специально подчеркнута цель мероприятия. Есть такое выражение — копал картошку, а выкопал клад.
В топике специально подчеркнута цель мероприятия. Есть такое выражение — копал картошку, а выкопал клад.
memcached написан на С, а не на С++. Ну еще один велосипед. Автор получит много скилла в разработке сетевых многопоточных приложений.
s/Paskal/Pascal/
Если внутри хэш и O(1), то многопоточность становится невыгодной — на мьютексах теряется _очень_ много времени, просто у вас не было такой нагрузки, чтобы это прочувствовать. Корректное написание (а потом отладка) многопоточных приложений — это отдельный скилл. Поэтому я бы предложил делать однопоточный сервер, а если его производительности не хватает — просто запускать n копий, как это все делают с мемкэшем.
Тут уже высказывались, что это велосипед :) Я бы предложил хотя бы сделать протокол мемкэш-совместимым, чтобы было возможно использовать существующие клиентские библиотеки.
Тут уже высказывались, что это велосипед :) Я бы предложил хотя бы сделать протокол мемкэш-совместимым, чтобы было возможно использовать существующие клиентские библиотеки.
Это уже не круто: ) — habrahabr.ru/blogs/python/78114/
Про потоки вы очень верно заметили, интересно было бы на эрланг реализацию посмотреть — memcache кластер малой кровью.
Про потоки вы очень верно заметили, интересно было бы на эрланг реализацию посмотреть — memcache кластер малой кровью.
Если хеш таблица реализована правильно, то ничего не теряется. Есть техники, которые позволяют делать многопоточную хеш таблицу без потери в производительности. Погуглите lock free data structures.
О, это замечательная идея — предложить человеку, пишушему на паскале спуститься на asm-уровень. Из всех lock-free алгоритмов для понимания прост разве что single producer/multy consumer queue, а все остальные как алгоритмически сложны, так и не имеют хорошей переносимой реализации. Не говоря уже о не-С реализации.
И потери идут не от качества реализации хеша, а от того, насколько fine-granted locks используется. А простейший вариант — один лок на всю таблицу (которых, правда, может быть несколько) — по вашему нисколько не скажется на производительности?)
И потери идут не от качества реализации хеша, а от того, насколько fine-granted locks используется. А простейший вариант — один лок на всю таблицу (которых, правда, может быть несколько) — по вашему нисколько не скажется на производительности?)
Есть неплохие lock-free лагоритмы основанные на CAS. Я как раз сейчас исследую это направление.
И, между прочим, в FreePascal есть инструкцияя asm, которой не так уж и сложно пользоваться. И результат вполне кроссплатформенен (используется особый диалект ASM).
CAS (compare and set) есть практически на любом процессоре. Надо просто инкапсулировать ее куда-нибудь и будет все работать на той платформе, которая вам нужна. С таким же успехом можно было бы говорить о том, что программа, использующая блокировки не переносима, тк API для блокировок отличаются на разных платформах.
Кстати, lock free hashmap есть для Java: www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf А Java переносима.
Кстати, lock free hashmap есть для Java: www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf А Java переносима.
Да, я тоже думал о совместимости протоколов. Надо будет запланировать для одной из версий. Сейчас в этом пока еще мало смысла. Нужен простой текстовый для отладки в telnet и он есть.
>Для реализации хеш-таблицы я выбрал бинарное дерево (возможно, не лучший способ) с разрешением коллизий на основе цепочек.
Хеш таблица это структура данных, как и бинарное дерево. Как одно может быть реализовано через другое, я не понимаю. Как в бинарном дереве коллизии разрешаются через цепочки, там их просто нет.
Хеш таблица это структура данных, как и бинарное дерево. Как одно может быть реализовано через другое, я не понимаю. Как в бинарном дереве коллизии разрешаются через цепочки, там их просто нет.
Как я понял, автор имеет ввиду, что для реализации ассоциативного массива используется бинарное дерево, а коллизии возникают, опять же по моим догадкам, код я не смотрел, некоторые ключи видимо имеют одинаковый результат хэш-функции, который используется для доступа к элементам в дереве и поэтому возникают коллизии.
Бинарное дерево используется как реализация разреженного массива для экономии памяти для хеш-таблицы. В итоге я получаю меньшую производительность, но и гораздо меньшие затраты в памяти. Размер ключа у меня 8, выделить 2^256 ячеек памяти по 4 байт (длина указателя) для такой таблицы нереально. Возможно есть более интересные реализации разреженного массива, было бы интересно ознакомиться.
А зачем вам иметь размер хеш таблицы таким же как и результат хеш функции? Почему бы не брать hashValue % tableSize в качестве номера ячейки, как обычно делают при реализации хеш таблицы.
Вы как-то странно проектируете… Вы хотите максимальной масштабируемости, но в каком месте Вы это закладываете?
Вы прекрасно заметили, что хэш или дерево могут работать только внутри одного потока и?..
Если б я был на Вашем месте, то, например, разбил бы диапазон ключей.
Например, берем ключ и быстро считаем его XOR сумму. Получаем число от 0 до 255, которое является индексом к массиву 256 деревьев.
Таким образом, кол-во блокирований деревьев сразу уменьшается в 256 раз.
Далее вам нужен не обычный мьютекс, а более продвинутый — который работает по принципу многие-читают — один-пишет.
Потому что дерево можно безопасно читать многим.
Можно и еще придумать разные идеи. Например, взять Б-дерево и попробовать сделать его блокируемым частично в момент обновления, а не полностью. Б-дерево хорошо тем, что состоит из крупных блоков.
Если подумать, я бы все же остановился на первом решении… Взять ключ и быстро выделить из него индекс дерева. Наверное даже можно побольше взять диапазон — например 65536. И дальше уже переходить к конкретному дереву и работать с ним. А хэш-таблицы: нафик. Фигня это для больших размеров.
Вот еще надо подумать как с потоками быть при такой схеме…
Вы прекрасно заметили, что хэш или дерево могут работать только внутри одного потока и?..
Если б я был на Вашем месте, то, например, разбил бы диапазон ключей.
Например, берем ключ и быстро считаем его XOR сумму. Получаем число от 0 до 255, которое является индексом к массиву 256 деревьев.
Таким образом, кол-во блокирований деревьев сразу уменьшается в 256 раз.
Далее вам нужен не обычный мьютекс, а более продвинутый — который работает по принципу многие-читают — один-пишет.
Потому что дерево можно безопасно читать многим.
Можно и еще придумать разные идеи. Например, взять Б-дерево и попробовать сделать его блокируемым частично в момент обновления, а не полностью. Б-дерево хорошо тем, что состоит из крупных блоков.
Если подумать, я бы все же остановился на первом решении… Взять ключ и быстро выделить из него индекс дерева. Наверное даже можно побольше взять диапазон — например 65536. И дальше уже переходить к конкретному дереву и работать с ним. А хэш-таблицы: нафик. Фигня это для больших размеров.
Вот еще надо подумать как с потоками быть при такой схеме…
Спасибо, я как раз сейчас переделываю локинг именно на такой вариант. Данные для чтения всегда доступны. А писать может только один.
А при удалении есть идея класть данные в сборщик мусора, который далее сам их очищает не ранее чем через определенный промежуток. Таким образом те, кто уже читали эти данные, могут продолжать это делать.
Интересно, а как это можно монетизировать?
Продавать наверное мало смысла.
А вот как консалтинг — вариант. Но тогда консалтинг это как фриланс — средние века, не фабрично.
Как это монетизировать поточно? Вот что гораздо интереснее.
Продавать наверное мало смысла.
А вот как консалтинг — вариант. Но тогда консалтинг это как фриланс — средние века, не фабрично.
Как это монетизировать поточно? Вот что гораздо интереснее.
Бтв, на тему протокола можно посмотреть на Redis. У него довольно вменяемый, как мне кажется — очень похож на реализованный здесь, но с чуть большим количеством возможностей.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
encached: кеширующий сервер