encached: кеширующий сервер

очень интересно :) жду версии для osx

«севера кеша»

что ты имеешь против кифира?! Оо :D

Как хорошо. Будет что посмотреть в процессе вашей работы. Давно хотел понаблюдать за процессом разработки подобного проекта.

Не совсем понятно, зачем явно вводить длину ключа (и данных), если их можно получить из самой строки?
Что происходит, если введена неверная длина?

Классное начинание, здорово. Все-таки я сторонник комментированного кода, особенно если этот код предполагается на чтение публике.

А почему не просто хэшом, а деревом? Создать, например, таблицу на 4М и более элементов. В большинстве случаев будет работать значительно быстрее чем дерево. Когда элементов будет меньше чем в хэш-таблице и при относительно равном распределении ключей, вставка и выборка будет происходить за O(1) а не за O(log(n)). Как способ для блокировок, можно все пространство ключей разбить на n частей и лочить только соответствующую часть, а не все.

И еще как вариант не изобретать своего протокола, а взять HTTP или добавить его поддержку. Если считывание и запись в сокеты происходит в отдельных потоках, зачем тогда неблокирующие? Или у вас там очереди на отправку, примем и обработку в каждом потоке и при неудачном чтении/записи происходит переход к poll-у?

А как память считать можно обертку тупо написать вокруг malloc и free, ну или как там оно в паскале называется. И в некоторый счетчик добавлять/вычитать чиселки через mutex, конечно. И в некоторых точках его выводить. Это самый простой вариант.

Собственно, не вижу смысла усложнять/добавлять проблем заданием длины ключа/данных.
Достаточно кешировать полученные из сокета данные, и парсить по концам строк, т.е.:
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), и далее — данные.

Но собственно я так и не понял. Зачем это все нужно :)?

Если внутри хэш и O(1), то многопоточность становится невыгодной — на мьютексах теряется _очень_ много времени, просто у вас не было такой нагрузки, чтобы это прочувствовать. Корректное написание (а потом отладка) многопоточных приложений — это отдельный скилл. Поэтому я бы предложил делать однопоточный сервер, а если его производительности не хватает — просто запускать n копий, как это все делают с мемкэшем.

Тут уже высказывались, что это велосипед :) Я бы предложил хотя бы сделать протокол мемкэш-совместимым, чтобы было возможно использовать существующие клиентские библиотеки.

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

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

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

Если б я был на Вашем месте, то, например, разбил бы диапазон ключей.

Например, берем ключ и быстро считаем его XOR сумму. Получаем число от 0 до 255, которое является индексом к массиву 256 деревьев.

Таким образом, кол-во блокирований деревьев сразу уменьшается в 256 раз.

Далее вам нужен не обычный мьютекс, а более продвинутый — который работает по принципу многие-читают — один-пишет.

Потому что дерево можно безопасно читать многим.

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

Если подумать, я бы все же остановился на первом решении… Взять ключ и быстро выделить из него индекс дерева. Наверное даже можно побольше взять диапазон — например 65536. И дальше уже переходить к конкретному дереву и работать с ним. А хэш-таблицы: нафик. Фигня это для больших размеров.

Вот еще надо подумать как с потоками быть при такой схеме…

Интересно, а как это можно монетизировать?

Продавать наверное мало смысла.

А вот как консалтинг — вариант. Но тогда консалтинг это как фриланс — средние века, не фабрично.

Как это монетизировать поточно? Вот что гораздо интереснее.

Бтв, на тему протокола можно посмотреть на Redis. У него довольно вменяемый, как мне кажется — очень похож на реализованный здесь, но с чуть большим количеством возможностей.