Close

27.10.2016

Key-Value не раскрытые возможности, которые мы раскроем

Давно я не писал. И вот тема достойная внимания имеется.
Мы скоро запустим очень интересный сервис: «распределенную Key-Value систему». Да, да, не смейтесь. Это будет действительно интересно, и я поясню, почему.

Но еще я давно хочу для наших разработчиков описать некоторые «паттерны» работы с KV (Key-Value), ведь немногие знают, как этими системами пользоваться, и думают, что KV очень примитивны.

Я опишу построение списков данных и массивов в рамках KV, или хеш таблиц, а также опишу схему хранения распределенного B-Tree в KV.

К слову, гигантский Распределенный B-Tree сервис мы тоже запустим. Раскажу и о нём тоже.

А еще я расскажу о планах развития этого сервиса и вы все поймёте, что

а) я не шутил, когда сказал, что «у KV есть нераскрытые возможности»
б) у Вас появится желание пользоваться  нашим сервисом 😉  я постараюсь

Что может KV

В принципе, KV может, казалось бы немногое- это сохранить по ключу одно значение и получить его обратно. И в правду не много. Часто есть возможность сделать cas операцию с одним ключом, но не с несколькими.

И полное отсутствие транзакций в понимании класических RDBMS.

На http://nosql-database.org/  огромный раздел No-Sql систем и в разделе «Key Value/Tuple Store» их больше всего — самых разных.

Они имеют много общего, но в них не достаёт того, что я ищу в таких системах.

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

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

Все знают о теореме CAP «якобы доказанной» (на словах и логических размышлениях.)  Прочитайте это, вряд — ли Вы найдёте эту ссылку сами) в MIT. Пока не доказано иное, с ней приходится считаться (ещё мне нравится такое её толкование).

Есть проблемы ACID. Проблемы маршрутизации, быстрого сетевого транспорта на уровне физики и уровне ОС итд. Может, позже об этом напишу.

Какую NoSql я хочу и почему. (motivation)

Классификация nosql систем с сайта http://nosql-database.org/ ,в принципе, не плохая. И я с ней согласен в бОльшей степени, однако, не стоит рассматривать эти системы, как только хранилища данных.

Важно не то, как хранятся данные, а важно, что Вы с данными можете делать.

Способ хранения и доступа — это средство. Цель получить накие новые свойства/качества при обработке.

На верхнем уровне таких систем мы обычно имеем систему k-v с адресацией по точному совпадению ключа, у которой:

  • по ключу хранятся просто скаляры или документы (составные структуры);
  • есть транзакции для нескольких ключей или нет;
  • объект транзакции доступен программисту, либо не доступен, либо не нужен;
  • они отличаются скоростью;
  • отличаются наличием или отсутсвием реплик;
  • у них есть порядок ключей или нет, и если есть, то  свою функцию сравнения установить либо можно, либо нельзя;
  • если есть порядок, то должна быть и навигация по ключам — она может быть различной;
  • иногда можно получить range ключей по некому «запросу»;
  • ключи могут быть организованы в корзины или коллекции или это flat scalar key space;
  • возможно удаление корзины или коллекции целиком или невозможно. Если да, то атомарное они или нет;
  • можно ли консистентно вносить изменения в ключ или нет (cas);
  • можно ли делать блокировки или нельзя;
  • где хранятся данные : persistent или memory;
  • можно ли подписаться на изменения или такой возможности нет;
  • какой вид выборок возможно осуществлять по всему множеству сохраненных данных, за счёт какого алгоритма делаются выборки, сколько проходов требуется для этого, какова производительность этого процесса;
  • итд.

Конечно, NoSql  может хранить гораздо больше данных, чем, скажем, Postgres, например. Хотя бы за счёт распределенной природы. И это в мире с растущим объёмом данных очень много значит.

Я проектирую системы для параллельной обработки петабайтов, и обработка файлов в распределенных FS — это, конечно, пока неизбежность, но будущее видится мне совершенно не так.

Сами по себе распределенные FS сегодня многие строятся поверх блочных устройств, как локальных, так и сетевых (Ceph). Можно рассматривать распределенную K-V как блочное устройство для слоя сервисов управления блоками файловой системы (Fuse). Так, давно уже можно монтировать себе S3, например,  чтобы в облаке лежали не сами файлы, а блоки данных, и выгружались на хост и кешировались локально.

Слабо раскрыт потенциал MapReduce в самих стораджах. Можете спорить, но я считаю, что слабо.

Мне очень понравился вариант реализации map-reduce в couchDB. И я у себя в продукте сделаю подобным образом.

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

Кроме самого map-reduce алгоритма нужно предложить автоматическое распараллеливание алгоритмов и безопасное взаимодействие с «вычислительным облаком» (тут я имею наш продукт acapella.ru).

Я «ходил вокруг компа кругами с радиусом в 10 колометров и думал, как реализовать всё лучшее в каждом пункте и нигде не проиграть» 🙂 .

И вот решение найдено.

О нашем Key-Value «хранилище»

Здесь я словами просто опишу ключевые  характеристики, и кратко, что это даёт.

API — http + jsonP + WebSocket

Это позволяет начать использовать систему прямо сейчас в любом вашем web или мобильном приложении.

Объект транзакции для програмиста — no. 

Мы не даём транзакцию, как таковую, она будет попросту даже не нужна :

  1. Тут важно понять часть идеологии CPVM: внутри уже есть иерархические транзакции и она через слой io_service связана с хранилищем. Пользователям cpvm не нужно вообще беспокоится.
  2. Если Вы не пользуетесь cpvm, для Вас есть multy_cas, о котором ниже (он покрывает очень много потребностей)

NRW из коробки

Мне понравилась идея Riak, когда мы смещаем CAP в требуемую нам зону для каждого вида данных в нашем прикладном решении и наращиваем либо A(+P) — Availability, либо C — Consistency, либо все сразу, проигрывая в скорости итд. Это даёт возможность использовать одну систему для данных «разной природы».

KV — обращение по точному совпадению ключа. Если не совпал, ты не угадал и значение не получишь. Тут нет никакого порядка.

DT — Distributed Tree (распределеннное дерево) с логарифмической скоростью доступа. Обеспечивает ключам порядок. И можно спросить следующий или предыдущий. Возможен доступ по приблизительному ключу — получишь или его, или его окружение, того места где он мог бы находиться.

Порядок ключей — у KV — no, у DT — yes

Мы даём две абстракции: hash и  sequence. Обе полностью распределенные.

DT позволяет строить быстрые распределенные индексы — это такие очень большие  индексы, которые не влезают ни на одну машину. Также это позволяет строить очень много других хитрых структур, о которых я ещё напишу. Например, распределенные множества, или дешево раздвигаемые списки списков и множество других алгоритмов , которые плохо ложаться на голый KV (такие распределенные множества мы используем внутри грида для работы с ЯПФ).

Установка функции сравнения — в будущем будет.

Навигация : next, prev — есть

У нас есть даже два способа ходить: один быстрее, другой универсальнее.

Уровни, корзины ключей — есть, даже лучше, у нас многоуровневое вложение.

Наш ключ KV- это список типа вида : [k1,k2,k3,k4], где  k1 и k2 могут быть разного типа.  Это один ключ.  Разработчику можно теперь не мудрить  с формированием ключа и его кодированием.

Удаление целиком корзины ключей: 

1) DT destroy whole Tree
2) ~KV cursor range delete~

Вносить изменеия по очереди, корректность, блокировки.

В KV есть  cas, и в KV есть multicas. В DT тоже есть  cas.

Это позволяет, не имея транзакции, делать консистентные изменения сразу нескольких ключей в большой  распределенной системе. Получаешь поведение, как в RDBMS. Будет меньше скорость, но если тебе это надо, ты это получаешь.

Persistent — yes or inmemory

Мы храним данные на диске, но не в ущерб производительности. Было время я замахивался на эффективный дисковый сторадж , но не хватило пока хватки — мы используем ardb, совместимый с redis по протоколу и мы используем в нём только простые и самые быстрые команды. В 95% это set, get. В  итоге, наш дисковый сторадж один из лучших.

Notifications — yes, by prefix and by key

Если вам надо получить уведомление, что ключ изменился, можно подписаться и получить уведомления. Получаешь про все ключи, которые начинаются одинаково, например [«myapp», «cars»]. Если дальше в ключе зарыто много всего,  будешь уведомлён, когда, что угодно случается с твоими машинами.

теперь о killer futures

R-Tree — ждите, он грядёт

Я давно люблю этот метод организации данных. «Пару лет» назад я попробовал упихивать в R-Tree объекты, проиндексированные по нескольким полям, чтобы построить «супериндекс». Чтобы сделать фильтрацию объектов по сразу нескольким условиям и нескольким полям, требуется всего один проход.  И никакого nesting loop не надо, не надо сортировать потоки PK и, выравнивая, сливать их по условиям, как этого требует работа с несколькими быстрыми бинарными ключами…

Я упёрся тогда в:

  • «неудобное отображение» блоков дерева в позиции в файле
  • индексировать можно только численные и перечислимые поля, но обычные скаляры, а особенно строки, не поддавались хорошей кластеризации, т.к. отсутсвует нормальная метрика расстояния между ними

Эти проблемы преодолены и у нас скоро будет нормальный глобальный индекс, который в большинстве случаев выбросит за нендобностью  map-reduce.

Наш облачный RTree сможет хранить/индексировать объекты не только с числовыми полями.

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

Чтобы что-то найти, не нужно запускать map-reduce (map в основном) по всем хранимым объектам,и не нужно тратить на это неимоверное кол-во ресурсов, достаточно просто обойти индекс  и получить все, что надо. У этой штуки масса применений.

Выгоды:

  • экономия CPU (не надо выислять map функции на всех объектах)
  • экономия IO (не надо вычитывать все имеющиеся объекты для map)
  • Производительность —  следствие этих пунктов.
  • Производительность2. Т.к. RT это дерево — для локации подходящих по условиям объектов  требуется O(log(N)) операций
  1. Этот метод вытеснит map-reduce в случаях, когда требуется фильтрация объектов — это очень большая зона применения.
  2. Скорость выше, экономия ресурсов — выше.

Как структура, RT — очень строптив, только когда речь идёт о работе с ним, как с локальным дисковым индексом. НО, реализованный поверх большого распределенного KV, он убирает проблему отображения блоков RT в позиции файлов, и планирования IO операций уходит на низкий уровень.

Когда мы работаем с большими данными в удалённом облаке — становятся важны просто другие свойства. Тут RT удобен и как интерфейс, и как эффективная структура.

distance mertic — wtf

Это будет публичный сервис. Вы просто по http api спрашиваете «расстояние» между любыми текстами:

str_mertic(«abracadabra» , «lorem ipsum…..», «1234567890»)  и получаете например [100 , 12345, 12] ,это числа, которые уже отлично поддаются кластеризации.

Эта штука используется у нас в R-Tree. Мы просто её открываем.

Сравним себя с другими

Я провёл сравнение с другими системами и вижу явное наше превосходство. Вот на что я смотрел :

  • terrastore
  • AmisaDB
  • HyperDex
  • Hibary
  • LIghtCloud
  • YA Eliptics
  • Riak
  • Scalaris
  • memcached
  • KyotoTycoon
  • Aerospike
  • Couchbase
  • Apache CouchDB

Дополнительно оказывается, что многие системы job management сродни системам организации взаимодействий типа etcd или ZooKeeper, т.к.  основаны на распределенном KV. Они используют в себе разные алгоритмы координации и выбора лидера для разных задач, например, Raft или Paxos всяких модификаций (мы, кстати,придумали свою ужасно эффекивную версию, вообще без таймаутов и проблем типа этой, когда приходится изобретать «виды консистентности»).

Я решил добавить некоторые возможности в наш KV, которые выведут нас ещё на один рынок «cluster coordination systems».

Координация работ в кластере — это тема отдельной статьи, тут не хочется «мусорить». Я планирую позже расказать о Serf, ZooKeeper, doozerd, etcd, eureka, coreos, consul. Про их datamodel, API, и странности.

Расскажу, что в них  важного, общего, не общего, и что мы можем тут предложить, как сделать мир лучше 😉 с помощью нашей системы

Наши преимущества  по сравнению с титанами, именно так

Можно сначала перечислить важные futures:

  • K-V NRW
  • CAS for KV, + CAS for several keys
  • ordered keys (DT)
  • no limit for ordered sequence (vs cassandra etc)
  • string distance for clasterization
  • fastest persistent storage OR in memory storage
  • Single smart index for all fields of any objects (docs) — rtree
  • listen / notify for key prefix
  • нет мастера ~ все узлы равны
  • установка функции сравнения
  • map reduce возможность
  • http api
  • поддерживать ли mamcached протокол ? proxy service ? — в будущем
  • directory service ~ -wait delete key when disconnect
  • system keys subspace
  • listeners

Если коротко :

Мы как Riak + Couch  + Couchbase, плюс обладаем свойствами HyperDex

Мы лучше Riak, т.к.:

  • у нас есть не только k-v by hash, но и DT, и RT;
  • можно разворачивать гораздо больше узлов в кластере;
  • у нас есть CAS — у Riak нет;
  • listen / notify;
  • memcached протокол.

Мы лучше Couch, т.к.:

  • cas | multy cas — выше консистентность по CAP ~ лучше подходит для надёжных решений;
  • лучше масштабируемость ~ можно делать много узлов;
  • установка функции сравнения;
  • memcached протокол.

Мы лучше Couchbase, т.к.:

  • не только hash KV, но и структуры DT + RT;
  • не только CAS, но и multy cas;
  • установка функции сравнения;
  • порядок ключей;
  • возможность map reduce;
  • http api;
  • хоршая масштабируемость, нет точек отказа (нет master node).

Мы лучше HyperDex, т.к.:

  • выбор количества серверов в топологии кластера и их идентификации не зависит от структур данных в предметной области — это упрощает развёртывание, ослабляет требования к числу машин;
  • один большой индекс за один параллельный его обход позволяет найти все нужные объекты без tree nestring loop;
  • потенциально можно работать с гораздо большими объёмами данных, т.к. не возможна ситуация, когда индекс партиции не влезает на машину.

Давайте рассмотрим, какие  базовые структуры можно строить в самом обычном KV.

Обычный KV — это get, set, cas  по одному ключу, и только. 

У нас система гораздо шире по возможностям, но в основе всего простой KV. Вот его и рассмотрим, просто для прояснения неясностей.

Даже KV, безо всяких DT, RT и прочих надстроек, позволяет строить массу всего.

Храним объект с полями или словарь

Можно хранить просто в одном ключе весь объект

[objid] --- '{"myfield1":"value", "summ":123}'

В значении хранися строка, json.dumps, например, поможет.

Можно разложить по полям в разные ключи

[objid, "myfield1"] --- "value" 
[objid, "summ"] --- 123

Это зависит от «обстановки» — как удобнее обрабатывать, так и делаете.

Менять поля или весь объект целиком можно по set или cas, во втором случае, чтобы одномоментно поменять два поля сразу, нужны спец. техники — о них в следующих статьях.

Храним список , точнее  массив

В массиве мы будем адресоваться по индексу — тут все просто

[array_id, 1] --- "value in index 1"
[array_id, 2] --- "value in index 2"

Если надо хранить еще и длинну, её надо выделить в отдельный ключ и логикой за ней следить через (cas)

Храним список next, prev

Вы уже догадались , что если можно хранить объект в  json виде (или иной стандартной сериализованной форме), то и делать из этих блоков можно любые структуры,  как в любом языке программирования учат на втором курсе, связывая всё ссылками.

[lists, listid] --- "{'head': 'axna', 'tail':'fwfwefr'}"
[blocks, axna] --- "{'data':'r123','prev':null,'next':'eret' }"
[blocks, eret] --- "{'data':'4533','prev':'axna','next':'fwfwefr' }"
[blocks, fwfwefr] --- "{'data':'hjkl','prev':'eret','next':null }"

Здесь видим двусвязный список , в значениях закодированы данные и ссылки. Сами блоки помещены в спец места, а ссылки только на их хвосты для экономии места.

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

Однонаправленный список, конечно,  более прост и потому более надёжен.

Удаление из списка — аналогично.

Такой список может искать O(n) только с хвоста или головы.

Наш DT сервис обладает бОльшими возможностями при организации последовательностей, поиск O(log(n)) , базовая навигация в обе стороны «из коробки» и может стать revers index для Ваших данных, а RT  структуре можно задать много условий  и она найдёт нужные объекты за один проход.

И DT, и RT сделаны поверх KV. Это позволяет, выбирая  реализацию KV, управлять и ими тоже:

  • с одной репликой — выигрываешь по скорости
  • несколько реплик с NRW — управлешь CAP балансом индивидуально для разных данных , например, проиграв по скорости, зато получив больше доступности и надёжности
  • дисковый storage или в памяти — на это же самое влияет

И самое главное, при работе с этим хранилищем из CPVM получаешь от CPVM автомаическое масштабирование алгоритма и параллелизм, а от хранилища возможность работать с огромными объёмами данных без потери консистентности и с высокой доступностью и надёжностью.

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *