• Структуры данных, используемые в Redis

    • Перевод
    От переводчика:
    Хочу представить вашему вниманию перевод ответа одного из разработчиков Redis, на вопрос о том, какие структуры данных используются внутри Redis. Оригинальную дискуссию вы можете найти на stackoverflow.


    Я попробую ответить на вопрос, но начну с того, что на первый взгляд может показаться странным: если вы не интересуетесь внутренностями Redis, вы не должны заботиться о том, как реализованы структуры данных изнутри. Причина этому проста — сложность каждой команды Redis вы можете найти в документации, и если у вас есть набор операций и их вычислительная сложность, то единственное, что вам нужно, это некоторое представление об использовании памяти (и потому, что мы делаем много оптимизаций, в зависимости от данных, лучший способ получить эти последние цифры это тесты в реальных условиях)

    Но поскольку вы спросили, вот внутренние реализации каждой структуры данных Redis:

    • Строки реализованы с использованием библиотеки динамических строк C, так что мы не платим (говоря асимптотически) за выделение памяти в операциях добавления. Таким образом мы получаем сложность добавления O(N), вместо, например, квадратичной.
    • Списки реализованы как связные списки.
    • Множества и Хэши реализованы как хэш-таблицы.
    • Упорядоченные множества реализованы как списки с пропусками (особый тип сбалансированных деревьев)
    Читать дальше →
    • +29
    • 22,2k
    • 5
  • Легковесные веб-приложения на Ruby

      Быстрая разработка


      Вдохновленный постами на западных блогах вроде «Clone TinyURL with 40 lines of Ruby» или «Clone Pastie in 15 Minutes with Sinatra & DataMapper» я решил попробовать пройти и заодно описать весь процесс реализации легковесного веб-приложения на руби, от проектирования до деплоймента.

      Читать дальше
    • Делаем gem для RubyGems

        Собираем камешки для Ruby


        Зачастую бывает так, что таскаешь из проекта в проект какие-то куски кода. Такие куски очень удобно выносить во внешние файлы, модули. Для этого в Ruby существует RubyGems — менеджер приложений и библиотек, оформленных в один файл-пакет — gem. И собрать такой гем, а главное, сделать его доступным для любой машины, подключенной к интернету, оказалось очень просто.

        Итак, gem за пол-часа