Всем привет.

slowpoke это key/value хранилище данных, написанное на стандартной библиотеке golang. Slowpoke обладает минималистичным, удобным апи и подходит для решения довольно широкого круга задач.

Записать значение в slowpoke можно при помощи команды Set:

slowpoke.Set("db/some.db", []byte("foo"), []byte("bar"))

Единицей хранения данных в slowpoke является файл. В данном примере — будет создана директория «db», с файлом «some.db», в который будет помещено три байта («bar»).

Строго говоря каждый файл в slowpoke — является независимой базой данных. Каждая база данных обслуживается в отдельной goroutine. Открытие/чтение файла осуществляется автоматически. Т.е. если данная база данных существует — она будет открыта и прочитана. Если нет — создана. Данная особенность позволяет не думать о состоянии базы при работе с ней и использовать например в обработчиках http запросов или в других goroutine.

В качестве ключа и значения slowpoke принимает массив байт. В примере выше в качестве ключа и значения по сути использованы строки. Запишем в slowpoke числа:

for i := 0; i < 40; i++ {
    id := make([]byte, 4)
    binary.BigEndian.PutUint32(id, uint32(i))
    slowpoke.Set("numeric.db", id, nil)
}

Мы конвертировали числа в формат BigEndian, что позволит корректно учитывать сортировку ключей при дальнейшей работе. Значение в данном примере не заданно, и будет создан только массив ключей (размер «numeric.db» будет 0 байт). Кстати о ключах, ключи в slowpoke — хранятся в памяти, но сохраняются на диск.

Это позволяет быстро оперировать с ключами с одной стороны, и закрывать таблицу в случае нехватки оперативной памяти с другой стороны. По этой причине, не рекомендуется использовать ключи большого размера. Предполагаю что оптимальным суммарным размером всех ключей для одной таблицы будет 10 Мегабайт. При превышении данного размера — лучше разбить на несколько таблиц базу данных. Значения же в памяти не хранятся и могут быть любого размера (картинки, фильмы). Суммарный размер таблицы значений не может превышать uint32. Некоторые преимущества данного подхода (раздельное хранение ключей и значений) описаны в статье www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf (в данной статье есть акцент на ssd диски Lsm tree и прочие архитектурные изыски не использованные в slowpoke)

Вернемся к slowpoke. Помимо чисел, строк, файлов и тп, можно сохранять и объекты, сериализуя их одним из методов. Пример сериализации в json:


        binary, _ := json.Marshal(post)
        slowpoke.Set("json",key,binary)

Или использовать встроенный в golang пакет gob: golang.org/pkg/encoding/gob

Все команды записи в slowpoke атомарны, и завершаются командой sync (синхронизация данных). Дело в том, что современные файловые системы при записи в файл, пишут по сути в буфер. И в случае падения операционной системы буфер будет потерян. Большинство баз данных имеет режим nosync (может называться по разному, но суть в том, что операция синхронизации очень медленная, особенно это заметно на старых винчестерах и для победы в бенчмарках и для ускорения записи используется данный режим). Хороший обзор на тему Crash Vulnerability.

В slowpoke нет режима «nosync», поэтому:

Для вставки нескольких записей в slowpoke используется команда Sets.

Данная команда рекомендуется для записи пакета ключей/значений. В этом случае данные будут записаны в файловый буфер и синхронизированы только один раз, по окончании записи. Что драматически увеличивает скорость записи с одной стороны, позволяет не жертвовать сохранностью данных в целом, с другой стороны. Пример использования команы Sets:

        var pairs [][]byte
	for i := 0; i < 40; i++ {
		id := make([]byte, 4)
		binary.BigEndian.PutUint32(id, uint32(i))
		post := &Post{Id: i, Content: "Content:" + strconv.Itoa(i), Category: "Category:" + strconv.Itoa(i/10)}
		b, _ := json.Marshal(post)
		pairs = append(pairs, id)
		pairs = append(pairs, b)
	}
	//store posts fast
        slowpoke.Sets(posts, pairs)

В примере выше, сначала формируется массив пар ключ/значение, затем осуществляется его запись.

Мы научились сохранять данные в slowpoke при помощи команд set и sets. Но прежде чем перейти к командам чтения, расмотрим команду для выборки ключей из slowpoke.

Для работы с ключами в slowpoke встроена команда Keys.

Ключи могут быть извлечены из slowpoke:

  • В прямом порядке
  • В обратном порядке
  • Со смещением
  • От определенного значения
  • Выбраны по префиксу

Пример команды:

//get last 2 post key with offset 2
	limit := uint32(2)
	offset := uint32(2)
	order := false //descending
	keys, _ := slowpoke.Keys(posts, nil, limit, offset, order)

Для команды Keys действует ряд правил:

Если limit не задан будут возвращены все ключи.

Если задано поле from (не равно nil), будут возвращены ключи после данного значения (само значение включено не будет).

Если подходящих под условия ключей нет, будет возвращен пустой массив.

Ключи внутри представлены в виде массива байтов. Соответственно, для получения корректно отсортированных чисел, например, необходимо конвертировать их в BigEndian.

Команда Keys манипулирует данными в памяти, и не обращается к диску. Внутри, в slowpoke, ключи продублированы в массивах (slice), каждый slice создается под таблицу и сортируется в момент вызова Keys (если необходимо). При выборке по префиксу/значению используется бинарный поиск (если возможно). Команда Keys предпочтительна по сравнению с Get/Gets по причинам изложенным выше.

Помимо возможностей паджинации, выборки следующего значения, команда Keys позволяет выбирать ключи по заданному префиксу. Например, в базе могут храниться теги tag:id или email:username ключи. В данном случае необходимо передать в поле from значение с символом * на конце, например []byte(«sex:*»). Также напомню о возможности создания ключей без значений, что может быть удобно для хранения индексов в памяти (даже если ключи без значений, они будут сохраняться на диске, для возможности восстановления в случае сбоя или закрытия таблицы).

Для выборки значений, в паре с командой Keys — удобно использовать команду Gets.

Команда Gets получает на вход массив ключей (т.е. результат команды Keys). Пример:

	keys, _ := slowpoke.Keys(posts, nil, limit, offset, order)

	//get key/ values
	res := slowpoke.Gets(posts, keys)

Результатом команды Gets будет массив пар ключ/значение. Обратите внимание, Gets:

— единственная команда не возвращающая ошибки
— если одного из ключей нет, он будет пропущен
— если нет ни одного из ключей — будет возвращен пустой массив

Также команда Sets — принимает на вход пары ключ/значение. Что может быть использовано для сохранения данных в другой таблице, например.

Keys — возвращает массив ключей
Gets — принимает массив ключей, возвращает массив пар
Sets — принимает массив пар

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

Для выборки одного значения — используется команда Get.

	res, err := slowpoke.Get(file, key)

В случае отсутствия значения Get вернет nil и ошибку ключ не найден.

Команда CloseAll() — закрывает все активные базы данных и должна быть вызвана по окончании работы, пример:

		sigchan := make(chan os.Signal, 10)
		signal.Notify(sigchan, os.Interrupt)
		<-sigchan
		//закрытие всех баз данных в случае прерывания работы
		slowpoke.CloseAll()

Любо так: defer slowpoke.CloseAll()

Мы рассмотрели основные команды slowpoke, но есть еще продвинутые команды.

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

Команда Close — закрывает базу данных и выгружает ключи из памяти.

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

Пример 1: вы храните логи

Лог за интервал времени собирается в массив пар и вставляется при помощи команды Sets
И записывается, например в файл, соответствующий дате логов, например «logs/20170101.db»
По окончании работы с данным интервалом — база данных «logs/20170101.db» — может быть закрыта, и выгружена из памяти при помощи команды Сlose. При любом запросе к данной БД — она будет автоматически открыта и считана.

Пример 2: цепочка блокчейн-транзакций

Допустим, каждая транзакция имеет номер. Возможно будет уместно хранить каждый пул транзаций в отдельном файле, например 1000.db — соответствует транзакциям с 1 по 1000, и выгружать из памяти, по окончании записи, если обращение к данному блоку сравнительно редкое.

Пример 3: хостинг сайтов

можно хранить данные каждого сайта в отдельной папке, например sites/mysite.com.db
и выгружать из памяти после обновлений, если чтение из них сравнительно редкое. Так как ключи в slowpoke хранятся отдельно от значений, чтение в память выгруженных ключей из файла — быстрая операция.

также есть команда удаления базы данных DeleteFile()

Архитектура

slowpoke написана на стандартной библиотеке golang. Для хранения ключей используются map и slice. Масштабирование достигается запуском каждой базы данных в отдельной goroutine.

Значения хранятся как есть, без оверхеда и только на диске, ссылки на адреса значений хранятся в памяти. В проекте не использованы ни BTree, ни LSM Tree. Также не используется технология mmap (и не планируется). Как показывает практика — чем более сложна архитектура базы данных, тем с бОльшим количеством проблем предстоит столкнуться с ростом базы. Так как ничего на бывает бесплатно.

Обратной стороной простоты архитектуры является более низкое быстродействие slowpoke по сравнению с лидерами рынка, во всяком случае на типовых замерах:

//macbook 2017 slowpoke vs boltdb
//The 100 Set took 19.440075ms to run./19.272079ms
//The 100 Sets took 1.139579ms to run./?
//The 100 Get took 671.343µs to run./211.878µs
//The 100 Gets took 206.775µs to run./?
//The 100 Keys took 36.214µs to run./?
//The second 100 Keys took 5.632µs to run./?

Например, в базах данных использующих LSM Tree (rocksdb,leveldb,cassandra,badger) запись будет более быстрой.

В базах данных использующих mmap — (LMDB, Boltdb, SophiaDb) чтение значений будет более быстрым (slowpoke не кеширует значения)

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

Для использования slowpoke на языках программирования отличных от golang написан пример небольшого сервера баз данных на http. Также потихоньку пилю более масштабный проект на этом движке.

GRPC-сервер с бэкдором в виде REST API

На данный момент slowpoke молода и мало распространена, используют в основном друзья, на своих личных пет — проектах (типа телеграм бота, сайта tggram.com, местами), как апи для сайта snatchnews.com (в мобильном приложении, через rest api). Теоретически она хорошо вписалась бы в проекты предполагающие хранение больших объемов данных — ipfs.io или Ethereum как альтернатива более комплексным базам данных типа leveldb/badger.

Буду рад пул реквестам.

Комментарии (30)


  1. achekalin
    24.04.2018 23:29

    Смайлики на Хабре запрещены, сами знаете.


    1. recompileme Автор
      24.04.2018 23:40

      Не знал, спасибо


      1. lostpassword
        25.04.2018 08:29
        +1

        Это всё неправда. Я постоянно их использую, и НЛО меня только один раз отправило на специальную страницу, где надо было проклинать где-то 20 или 30 чекбоксов с лейблами "Я больше не буду злоупотреблять смайликами", причём активировались они по очереди, с интервалом около 10 или 30 секунд после прощёлкивания предыдущего.
        В общем, интересная штука, рекомендую попробовать!


        1. achekalin
          25.04.2018 10:58

          Я уже натыкался, спасибо, кликал потом. С тех пор стараюсь не использовать. Потому что есть при создании аккаунта каждый хабраюзер подписывается следовать правилам сайта, а в них про смайлы и запрет на них написано. Увы. НЛО работает на поиск смайлов только по большим праздникам (или не знаю еще по какому расписанию), но большой радости еще раз кликать по чекбоксам не вижу.
          А если правилам (на которые сам же и подписался), не следовать, то ресурс вразнос пойдет, как ни крути.


    1. KodyWiremane
      25.04.2018 10:54

      В заголовке отлично смотрелось )


  1. webwork
    25.04.2018 09:12

    А она потокобезопасна? т.е. если из разных потоков одновременно писать в одну таблицу (в один файл) и читать с таблицы — данные не будут корректно обработаны?


    1. recompileme Автор
      25.04.2018 09:13

      Да, потокобезопасна, конечно. В тестах есть множество примеров


      1. anjensan
        25.04.2018 16:39

        А что насчет процессобезопасности?

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


        1. recompileme Автор
          25.04.2018 18:41

          До тех пор, пока Вы работаете с базой через интерфейс slowpoke — это безопасно. Но нельзя менять что то в файле напрямую, или к примеру запустить другую слоупоке, в другом процессе и натравить на тот же файл. Если я правильно понял задачу — Вам нужен сервер над slowpoke. Например, github.com/recoilme/okdb
          Сервер будет обеспечивать доступ к базе из различных процессов, код будет чуть сложнее:

          	var conn *grpc.ClientConn
          	var err error
          	var f = "db/1.db"
          
          	conn, err = grpc.Dial(":7777", grpc.WithInsecure())
          	if err != nil {
          		log.Fatalf("did not connect: %s", err)
          	}
          	defer conn.Close()
          
          	c := api.NewOkdbClient(conn)
          
          	// Set
          	_, err = c.Set(context.Background(), &api.CmdSet{File: f, Key: []byte("1"), Val: []byte("1")})
          
          	// Get
          	b, err := c.Get(context.Background(), &api.CmdGet{File: f, Key: []byte("1")})
          }
          


  1. datacompboy
    25.04.2018 15:15

    Чет дважды перечитал, не могу найти, так где же на диске ключи хранятся-то?


    1. recompileme Автор
      25.04.2018 15:29

      Для каждой таблицы значений, создается файл с постфиксом .idx, в который персистятся ключи.


      1. datacompboy
        25.04.2018 18:54

        а если креш?


        1. recompileme Автор
          25.04.2018 19:06

          Ну, slowpoke делает sync (fsync) на каждую операцию записи, не отложенный, по таймеру как сейчас стало модно, и не перед закрытием, например, а честный sync на каждый set/sets. Это самый дорогой и надежный способ синхронизации. Но конечно и он не дает 100% гарантии: danluu.com/file-consistency


          1. legolegs
            25.04.2018 23:08

            >а честный sync на каждый set/sets. Это самый дорогой и надежный способ синхронизации.
            Это ужасно.
            Аналогичный подход исповедует команда проекта Sia, так одно время их продукт приходилось пускать с tmpfs, потому что даже на SSD было медленно, а на шпинделе вообще часы! И это на БД меньше гигабайта! Естественно костыли уровня cp db /tmp; dosmth /tmp/db ; cp /tmp/db ./ надёжности не добавляли.


            1. recompileme Автор
              25.04.2018 23:45

              Наверно эта Sia — sia.tech
              Там вроде boltdb внутри — github.com/NebulousLabs/Sia/blob/master/persist/boltdb.go
              У болта есть режим DB.NoSync, он, естественно опасный — github.com/boltdb/bolt/issues/612
              Бэкапы, реплики.

              В slowpoke нет NoSync, но есть пакетная запись, sets — с одним sync на пакет, он быстрее:
              //macbook 2017 slowpoke vs boltdb
              //The 100 Set took 19.440075ms to run./19.272079ms
              //The 100 Sets took 1.139579ms to run./?

              Это тесты на ssd — sync занимает около 1 ms. Это оч медленно (примерно 99% времени от set уходит на sync) На «шпинделе» — еще медленней раз в 100 или даже 1000. Секунда запросто уйдет — и с размером базы это не связано никак.
              Вобщем можно юзать sets для быстрой вставки, но есть риск потерять весь пакет при креше.


          1. datacompboy
            26.04.2018 00:44

            но ведь не на ключи, а на данные? или ключи тоже кидаются на диск после каждого изменения?


            1. recompileme Автор
              26.04.2018 07:57

              Тоже


              1. datacompboy
                26.04.2018 11:05

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


                1. anjensan
                  26.04.2018 12:11
                  +1

                  Перебрасывается только обновленный ключ (переазписывается) + в конец файла с индексами аппендится запись со спец маркером для удаления (отчего уж не сделать также поверху не ясно). Как я понимаю реального удаления ключеей никогда не происходит (судя по коду compact нету). Все записи в файлы считаются атомарными всегда и без вариантов (ну а че, отчего бы и нет).


  1. random1st
    25.04.2018 16:20
    +1

    Можно добавить информацию, зачем понадобилось пилить свой велосипед, а не взяли готовые?


    1. recompileme Автор
      25.04.2018 17:07
      +2

      Я не стал выливать эту боль в посте. Проблема состоит в том, что недостатки раскрываются с ростом базы данных, в процессе эксплуатации. Остается либо лупоглазить в код либо читать описания/отзывы и прикидывать во что это выльется. Мне же не нужна была скорость, мне нужен был движок который будет предсказуемо и стабильно вести себя по мере роста. А сейчас так не пишут. Всем нужна скорость, возникли проблемы? Так купите SSD, добавьте память.

      Коротко, на примере boltdb, через примерно полгода эксплуатации:
      — нагрузка на винт под 100% (перестало работать всё остальное)
      — деградация производительности в десятки — сотни раз
      — необходимость покупки дорогостоящего SSD
      — необходимость поднятия кеширующего слоя с redis над болтом
      При этом boltdb — не самая плохая база данных, пока целиком помещалась в память — всё было прекрасно.

      До этого обжигался на хранении бинарных данных (именно бинарных) в РСУБД + был не самый удачный опыт эксплуатации Касандры.

      С другой стороны есть позитивный опыт эксплуатации sophia в хайлоаде, но она на C и замечания тоже есть. С leveldb сталкивался больше как пользователь, субъективно — мне показалась что она вобрала в себя все возможные недостатки) Проверять не стал. Архитектурно понравился badger, но оттолкнула модель хранения данных (Lsm Tree) и некоторые посты от их команды разработки. Банально не хотелось проверять на себе. Ну и задача разработки простенького движка — казалось проще чем оказалось)


      1. anjensan
        25.04.2018 17:25
        +1

        Скажие, а на каких объемах данных сейчас используется slowpoke.


        1. recompileme Автор
          25.04.2018 17:36
          +1

          К моему стыду внедрена в продакшен она относительно недавно и опыта эксплуатации на миллиардах записей пока банально нет. Максимальный размер базы — несколько гигабайт. Надеюсь в ближайшее время перевести на нее более крупный проект, для которого первоначально и писал, но там нужна не встроенная база, а сразу grpc-сервер, который пока не закончен(


          1. anjensan
            25.04.2018 17:39
            +1

            Максимальный размер базы — несколько гигабайт.
            Это, как я понимаю, суммарный размер Values.
            Меня больше интересует размер и количество Keys.


            1. recompileme Автор
              25.04.2018 17:44
              +2

              Примерно 17000 md5 хешей


  1. anjensan
    25.04.2018 16:56

    Как показывает практика — чем более сложна архитектура базы данных, тем с бОльшим количеством проблем предстоит столкнуться с ростом базы. Так как ничего на бывает бесплатно.
    Как показывает практика, чем проще архитектура, чем с худшей производительностью предстоит столкнуться с ростом базы… Например, у вас на каждый вызов Keys делается вызов sort.SliceIsSorted, у которого, на минуточку, линейная сложность. Ладно, пофиксите… А после каждого Sot лениво вызываете sort.SortSlice… Даже в лучшем случае это тоже как минимум линейно… Зато архитектура простая!


    1. recompileme Автор
      25.04.2018 17:28

      Это во многом справедливое замечание, спасибо. Метод Keys может быть написан получше. Но тесты показали что перестроение/хранение отсортированного дерева ключей (LLRB BTree) тоже не бесплатно. Версия на деревьях сохранилась в истории если интересно (https://github.com/recoilme/slowpoke/blob/ver.0.2/slowpoke.go) Просто в какой то момент я устал дебажить откуда и почему почему в дереве появился фантом( А если по скорости примерно тоже самое, зачем за него платить?


    1. recompileme Автор
      25.04.2018 18:03
      -1

      Метод сортировки в гоу, несмотря на название функции quickSort_func, под капотом содержит и сортировку вставкой, что должно привести к очень быстрой вставке новых ключей в отсортированный массив. И при Set — не вызывается (хотя такая идея была).


      1. anjensan
        25.04.2018 18:38

        сортировку вставкой, что должно привести к очень быстрой вставке новых ключей в отсортированный массив
        Да хоть сортировку пупыркой =)
        Все равно минимум O(N) сравнений будет (алгоритм то не знает, что только последний элемент не на своем месте). Да и сортировка вставками включается только как последний шаг qsort для оптимизации. Но вообще я придираюсь, это да.


  1. anjensan
    25.04.2018 18:38