татко Крокодил

Около разни разговори за една нова система при нас и какви бази данни трябва да ползваме (и викове от някакви хора “ама то трябва да е задължително nosql” с идеята, че nosql == магически бързо) и обяснения, подкрепени с малко тухли, реших да драсна това – какви основни неща ползват базите данни, защо (и какво можем да очакваме с промените по хардуера), заедно с разни други наблюдения.

На всички, които това им е интересно препоръчвам “Transaction Processing” на Jim Gray като едно много добро начало.
(за хората, които предпочитат да четат код, двете малки и съвсем истински бази са BDB и SQLite (който е и пример за истински добре написан софтуер))

По принцип под “база данни” се разбира ACID база данни, вероятно с някакъв SQL интерфейс. В по-модерни времена се разбира някакъв вариант на това, без SQL, понякога просто бърз начин човек да съхранява (и губи) данни.

ACID значи следното:
Atomicity (атомарност) – всяко действие или се изпълнява изцяло, или не се изпълнява изобщо (т.е. ако кажем “искам да увелича с единица на тия две места”, или ще се увеличат и двете, или ще получите грешка, но никога няма да се промени само едното).
Consistency (консистентност) – има вътрешни правила, които винаги са в сила, (например ако сме казали, че стойностите в дадена колона са уникални, базата не трябва да ни позволи да вкараме две еднакви такива).
Isolation (изолираност) – никой няма да ни подмени данните, докато работим с тях.
Durability (издръжливост) – ако сме записали нещо в базата и тя е казала, че е записано – то няма да изчезне, т.е. записано е на физическия носител, който не се влияе от спиране на тока.

Като цяло това са свойства, произлезли от нуждите на счетоводството/банкирането. Една ACID база данни е перфектна за всякакви такива нужди, понеже позволява да се опишат всякакви сложни структури от данни и тя да се грижи за това да не се омазват и да може да се работи с тях.

Всички тези свойства имат негативно влияние в/у performance. Най-зле се отразява D-то, понеже в повечето случаи това значи по поне един fsync() на транзакция, което от своя страна води до поне една физическа дискова операция, а поне преди SSD-тата те бяха най-голямото ограничение. I (и донякъде зависещото от него A) пък започва да се проявява при достатъчно бързи дискови масиви и големи паралелни натоварвания, когато се налага да се взимат и изчакват много (и сложни) lock-ове.

Изобщо, ако искате да запомните нещо съвсем просто от цялото ми писание, TL;DR-то е: писането в базата ви е ограничено от това колко транзакции може да ви направи дискът, четенето (ако базата ви не се събира в паметта) – също. Ако не са ограничени от това, ще загубите данни.

Други бавещи неща в стандартните бази данни са огромните възможности на SQL-а – всякакви join-ове и други сложни заявки, които в един момент няма как да се оптимизират – и неща като trigger-и, foreign key-ове, views, които усложняват и вкарват навсякъде нови lock-ове, сметки и забавяния. Например може да е възможно една база да пише в transaction log-а си по 2000 транзакции в секунда, но голяма част от времето ѝ да отива да проверява дали данните отговарят на консистентността, да чака read lock-ове или просто да parse-ва сложния SQL, който ѝ се подава.

Структурите, които базите данни използват са ориентирани към това да може да се работи ефективно и сравнително бързо с бавни, но сигурно-записващи устройства (дискове), т.е. основното предположение на повечето бази данни е, че имаме процесор с много бързи регистри/кеш, 10тина пъти по-бавна памет, и около милион пъти по-бавен диск, от който може да се чете само на блокове (т.е. парчета с размер от 512 или 4096 байта, align-нати на такава граница), като линейните действия (с няколко предни блока) са по-бързи от random действията.

Основната структура, която базите използват се нарича B+ дърво. В “Transaction Processing” има страхотно описание и си личи колко гениална структура е, аз тук ще се спра само на основните неща от нея:
– представлява нормално дърво, с корен и листа на няколко нива;
– всеки node от дървото съдържа ключ, данни и масив от указатели, който казва за кой range от данни към кой друг node да се ходи;
– размерът на всеки един node се гледа да е колкото една страница, константен за дървото, кратен на block size на устройството, на което се записва. Варира от 512B (за много много отдавна), 4KiB (сравнително отдавна) до всякакви други стойности (веднъж като гледах кода на postgresql беше 64KiB);
– в B+ дървото (и каквото по принцип се използва) всеки node има указатели към левия и десния си такъв, за да направи лесно търсенията по интервал (range).

Така търсенето в дървото е в общи линии логаритмично при основа размерът на масива от указатели във всеки node, което много ускорява работата при блоково устройство.

(почти) всяка таблица в съществуващите бази данни е B+ дърво, подредено по primary key-а си. Допълнителните индекси са често B+ дърво или подобна структура по колоната, която индексират и със стойност primary key на търсения ред. Това води до следните няколко неща:

– Търсенето по primary key винаги е по-бързо от търсенето по вторичен индекс (освен в един специфичен случай по-долу);
– Индексирането не е магия. Виждал съм хора да слагат в заявка търсене по функция от дадено поле, и ако индексът не е построен по същата функция, базата няма как да го използва;
– Като цяло за блокови устройства няма по-ефективна структура – прави малко четения (които са бавни) за сметка на сравненията (които са сравнително бързи).
– Някои бази имат допълнителни типове индекси, които вършат работа в по-странни случаи. Примери са full-text индексите (GIN на някои места), R-дървета (за многомерни данни) и hash-овете.

Тук има един интересен hack, който се поддържа от повечето по-нови версии на базите данни. Ако имаме следната таблица:

create table pesho (
pesho_sid serial not null PRIMARY KEY,
field_a int not null,
field_b int not null,
field_t varchar(16) not null
);

и имаме да търсим по field_a и field_b, за да прочетем field_t (SELECT field_t FROM pesho WHERE field_a=1 AND field_b=2), по принцип бихме създали индекс по field_a и field_b. Тогава заявката ще прави първо търсене в индекса, ще намери pesho_sid за нужния ред, и ще потърси после в самото B+ дърво. По-хитро (ако базата го поддържа) е да направим индекса по field_a, field_b и field_t, като тогава базата ще намери стойността в индекса и ще има и нужните данни, за да върне директно отговор на заявката само с първото търсене.
(още по-подобрен вариант за конкретния случай е да се махне pesho_sid и да се направи primary key по field_a и field_b, доста хора се притесняват по принцип от композитните primary key-ове, а не трябва)

Другият компонент, който би трябвало да има във всяка база е т.нар. transaction log (или write-ahead log, binary log, journal или всякакви други имена). Идеята му е, че всяка транзакция/действие за писане се записва в него, след което той се sync-ва до диска (така се гарантира онова Durability), и чак като се напълни се насипва в/у реалните данни по диска. Всяко действие се записва така, че да е идемпотентно, т.е. да може логът да се приложи няколко пъти, без да повреди данните (което е нужно за спасяване от момента, в който ни спре тока докато flush-ваме log-а).Това помага за доста неща:

– Писането по диска е през повечето време линейно, което доста забързва действията по базата;
– Заявките естествено се сериализират и при спиране на тока или нещо такова после могат да се replay-нат от лога;
– Същия log може да се използва за репликиране на базата, или за възстановяване от backup заедно с dump от дадена дата, или дори за връщане назад.

Идеята всъщност не е ограничена до базите данни, и в един или друг вид се използва на много места (например файлови системи).

Този вид log се използва във всички бази данни и в почти всичко, което съхранява данни (изключение са in-memory storage-ите като memcache, на които не им трябва да се синхронизират с някои и не им пука за спирането на тока).

Ако човек се загледа какво ползват nosql базите, ще открие все същите неща. По-долу съм изброил няколко и причините да са по-бързи (за някои неща):

Apache Cassandra в общи линии използва in-memory transaction log-ове, които синхронизира с другите сървъри в клъстера (т.е. губят се данни, ако на всички им спре тока). Решава си проблемите със скоростта, като не поддържа нищо сложно (като join-ове) и като пише по диска само на големи burst-ове, когато напълни някоя таблица.

Apache CouchDB комбинира по хитър начин B+ дървото и transaction log-а, като винаги само добавя във файла. За да си помогне още малко, прави fsync() не на съвсем всеки документ, а гледа да batch-ва по някакви писания и да sync-ва веднъж в секунда, което пак може да доведе до загуба на данни.

MongoDB ползва transaction log, ползва B дървета за индекси, и се справя с многото писане като просто mmap-ва файловете от базата в паметта. Единственото, което fsync()-ва, е transaction log-а, на 100ms (pdf с презентация за mongodb internals).

Както и много други знайни и незнайни нещица. Голяма част от тях не биха се справили със стандартния ми тест за сериозна база данни ( да се пуснат транзакции спрямо нея и да и се рита тока, и да не загуби нито една от потвърдените), но пък имат приложение в много области, където или данните не са чак толкова важни, или има начин да се заобиколи загубването им. Един хубав пример има в Beautiful data, гл. 5, където facebook описват как, за да си съхраняват clickstream-а, са минали през Oracle, MySQL и са стигнали до cassandra, която просто може да се scale-ва ужасно много (и на тях изобщо не им пука за няколко изгубени click-а).

Ако събера сили, ще напиша приложение за дистрибутирането на базите данни, CAP теоремата (или защо господ ни мрази) и какво правят разни хора по въпроса.

Tags: работа

This entry was posted on Sunday, May 29th, 2016 at 19:56 and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.