Базы данных: введение, часть четвертая

Илья Тетерин
2011-10-12

(use arrow keys or PgUp/PgDown to move slides)

Новости мира баз данных

Redis и числа Фибоначчи - issue #116

The calculation of the Fibonacci value for a number is a serious issue.
I request as a feature the command FIB.
Use of the command: redis-cli > FIB 10
55
Oracle and NoSQL
May 2011 - Debunking the NoSQL hype
хорошая, подробная бумага почему NoSQL плохо - рекомендую
2 Oct 2011 - Focus On Oracle NoSQL Database
конференция в Сан-Франциско - презентация новой базы
Oct 2011 - Oracle NoSQL Database
на сайте появились страницы, но
"The Oracle NoSQL Database documentation link is coming soon."
- Key-value pair data structure, keys are composed of Major & Minor keys
- Easy-to-use Java API with simple Put, Delete and Get operations
- Automatic, hash-function based data partitioning and distribution
- ACID transactions, configurable globally and per operation

Oct 10, 2011 - Сбой в работе mail.ru

ИТАР ТАСС: В работе российского почтового интернет-сервиса "Мейл.ру" произошел сбой

МОСКВА, 10 октября. /ИТАР-ТАСС/. Пользователи крупнейшего российского почтового сервиса "Мейл.ру" ... испытывают трудности с доступом к своим почтовым ящикам. При попытке проверить почту или открыть письмо на экране появляются сообщения то об ошибке сервера, то о перегрузке базы данных.

Проблемы с доступом к почтовому сервису начались примерно в полдень, при этом остальные сервисы портала "Мейл.ру" работают нормально.

roem.ru 11.10.2011: В результате внедрения новой более оптимальной системы хранения данных произошел программно-аппаратный сбой. Наши специалисты устранили проблему в течении 2-х часов. Сбой состоял в недоступности почты для примерно 8-10% пользователей. Никаких потерь или утечей данных не было.

wikipedia:mail.ru ... почта (22,7 млн человек ежемесячно) ...

pulser: 22.7м в месяц ... 756k в день ... 30 000 человек в час ... 10% - это 3 000 человек в течение часа

это не много, не мало - это проблемы availability в кластере ... но они заметны на уровне ИТАР-ТАСС ...

SQL vs NoSQL

Relational Database Management System + SQL

Oracle / MySQL / PostgreSQL / HSQLDB

NoSQL (Not Only SQL) - nosql-database.org

Key Value - Memcached, Redis

Document Store - MongoDB, CouchDB

Graph DB - Neo4j, HyperGraphDB, FlockDB

... etc ...

wikipedia:NoSQL ( рус )

Flashback:

бумажная телефонная книга, как база данных
CRUD операции
UI к нашей базе (console / http / socket)
partition/sharding / master-slave replication
key-value store / document oriented db
транзакции / journal операций
ACID / CAP / BASE

Почему долго работает мой запрос?

На примере: дайте седьмую запись

Мы точно знаем что мы хотим получить и хотим получить одну единственную запись.

Запрос

"наша база":
```
http://host:port/select?id=7
```
memcached / redis:
```
get 7\r\n
```
SQL:
```
select * from users where id = 7
```

SQL Select:

-- ключевое слово - команда
select 
-- какие поля ( * )
  fio, phone 
-- ключевое слово - разделитель
from 
-- имя коллекции
  phones 
-- ключевое слово - ограничения
where 
-- ограничения через AND / OR 
  id = 7

Сценарий исполнения запроса

клиент формирует запрос
соединяемся с базой
передаем запрос
сервер парсит запрос
находит коллекцию
получает данные
преобразует в формат для ответа
отправляет по сети
на клиенте восстанавливаем данные
закрываем соединение

формирует запрос

собрать строчку руками (Query by Language)
```
String sql = "select * from persons where id = " + id
```

query by example (Query by Example)

Person p = new Person(); // всё остальное null
p.setLastName("Smith");
ObjectCollection oc = QueryExecutor.execute(p);

построители запросов (Query by API)

Query q = new Query();
q.From("PERSON").Where(new EqCriteria("PERSON.LAST_NAME", "Smith"));
ObjectCollection oc = QueryExecutor.execute(q);

ORM (object - relation mapping)

соединяется с базой

Class.forName("com.mysql.jdbc.Driver");
String myDatabaseURL = "jdbc:mysql://mydomain.com/database?user=" 
    + myUsername + "&password=" + myPassword;
java.sql.Connection con = DriverManager.getConnection(myDatabaseURL);

а какой shard? ( f(x)->shard )
dns запрос / cache / timeout
открыть socket
подготовить буфера

передаем запрос

простая форма - строка
QBE/QBA - обойти объекты,
построить структуру запроса
сериализация (структура - поток байт)
на сервере - (поток байт - структура)
блок памяти для запроса на сервере

сервер парсит запрос

а какая команда будет?
валидность пришедших данных
к какой коллекции обращение
с какими параметрами

Пример кода

public interface Command {
  void process(Processor p, String cmd) throws IOException;
  boolean isApplicable(String cmd); }

public abstract class AbstractDump implements Command {
  public boolean isApplicable(String cmd) {
    return "/dump".equals(cmd) || "Dump".equals(cmd); }}

public class MasterDump extends AbstractDump {
  public void process(Processor p, String cmd) throws IOException {
    boolean result = PhoneBook.getPhoneBook().dump();
    p.writeResponse(result ? "OK" : "ERROR"); }}

COMMANDS = new ArrayList();
COMMANDS.add(new MasterCommit());
COMMANDS.add(new MasterDump());

for (MasterCommand cmd : COMMANDS) {
  if (cmd.isApplicable(string)) {
    cmd.process(this, string);
    break; }}

by Ксения Мамич

Generated in IntelliJ IDEA by yFiles

находит хранилище / коллекцию

внутренний словарь данных
коллекция существует?
где находится коллекция?

получает данные из коллекции

формат коллекции (память/файл)?
открыть файл (какой, где, filehandle etc)
найти запись:
random access - а как узнать позицию?
scan - а как фильтровать? только в десериализованом
позиционирование / фрагментация файла
транзакция - undo logs - фрагментация
cache - в базе, в OS
зачитать данные в буфер
преобразовать буфер в memory structure

преобразует в данные для ответа

формат в коллекции ( * - все поля как есть )
формат в запросе ( f1, f2 - спрячь лишнее при начитке)
десериализация
фильтрация

отправляет по сети

сериализация
буфер на стороне сервера
особождение ресурсов на сервере

восстановление на клиенте

буфер для сериализованных данных
десериализация (строка - структура)

by hand

Person p = new Person();
p.setName(request.getParameter("name"))
p.setPhone(request.getParameter("phone"));

ORM (подробнее - не сегодня)

закрытие соединения

finally - вернуть в пул
таймауты

Оптимизации

Что можно сделать, дабы было быстрее

Клиент и соединения

connection pool (Apache DBCP)
"горячий" connection

пул соединений
prepared statement
batch операции
кеширование ключ -> shard
wikipedia: Bloom фильтр(по русски)

All you ever wanted to know about writing bloom filters
Bloom Filters - the math
m - колво битов, k - колво hash функций, n - колво ключей ... интересно при k > 2 и m/n > 10 ...

Сервер и соединения

кеширование распаршенных запросов

prepared statement + cache

PreparedStatement ps = connection.prepareStatement(
  "select * from person where id = ?");
ps.setLong(1,7L);
final ResultSet rs = ps.executeQuery();

"горячие" инстансы
формат сериализации - binary, закрытый

Словарь базы

кеширование
изменения в словаре и транзакции

Получение данных

file cache для файлов с данными
количество свободной памяти vs file cache
memory mapped files / file page miss
упакованные данные / gzip / io speed vs cpu speed
распаковка с произвольного места / !gzip / lzo / bzip2
сортированный data file / binary search

Получение данных - индексы

индекс - дополнительная структура для быстрого позиционирования
индексы vs словарь vs парсер
селективность (cardinality) + статистика
индекс и позиционирование в data file
два раза ищем (сначала в индексе, потом в файле)
... а не всегда (если данных в индексе достаточно для ответа)

Преобразование формата data file - response

Отказ от фильтрации - меньше нагрузка на CPU
Отдавать как есть - копия данных
key-value vs document vs table row
формат vs объем данных

Форматы сериализации

XML - парсеры, валидация, читаем, достаточно одного файла
json - xml + компактнее и напрямую можно использовать в браузере
Protocol Buffers - Google, жесткий, рекомпиляция
Thrift - Facebook - жесткий, рекомпиляция
bson - MongoDB, компактный, нечитаем
... etc ...

JVM-serializers - бенчмарки

Protocol Buffers, Etch, Hadoop and Thrift Comparison

Protocol buffers

http://code.google.com/apis/protocolbuffers/docs/overview.html

Why not just use XML?

Protocol buffers:

are simpler
are 3 to 10 times smaller
are 20 to 100 times faster
are less ambiguous
generate data access classes that are easier to use programmatically