Курс высокие нагрузки и надежность: отрывок
3 likes26,623 views
Разработка надёжных высоконагруженных систем Москва, 24, 25 и 26 мая http://smira.highload.ru/ Трехдневный мастер-класс с практическими заданиями
More Related Content
What's hot (19)
Similar to Курс высокие нагрузки и надежность: отрывок (19)
More from Andrey Smirnov (10)
Курс высокие нагрузки и надежность: отрывок
- 1. © Copyright 2014 Andrey Smirnov Как работают системы хранения данных? • Хранение - на диске. • Давайте напишем свою!
- 2. © Copyright 2014 Andrey Smirnov Файловая система • Почему не система хранения данных? • В плюсах: • почти ничего не надо писать • конкурентный доступ из разных приложений❔ • переносимость • инструменты • производительность • Почему тогда не используется?
- 3. © Copyright 2014 Andrey Smirnov Простая плоская структура key: len + chars value: len + chars key: len + chars value: len + chars key: len + chars value: len + chars ….
- 4. © Copyright 2014 Andrey Smirnov Как это работает? • Как будут добавляться записи? • Как удаляться? • Как изменить значение? • Как прочитать значение по ключу?
- 5. ? © Copyright 2014 Andrey Smirnov Что можно изменить, чтобы структура работала лучше?
- 6. © Copyright 2014 Andrey Smirnov Улучшения • Отсортировать записи • Флаг удаленности • Индекс в отдельном файле • Хэш-структура на диске
- 7. © Copyright 2014 Andrey Smirnov Проблемы ввода-вывода • random IO • block size/alignment • буферы ОС/sync
- 8. © Copyright 2014 Andrey Smirnov
- 9. © Copyright 2014 Andrey Smirnov Что делать? • Страничный ввод-вывод • Последовательный ввод-вывод (append-only)
- 10. © Copyright 2014 Andrey Smirnov Log-Structured Merge-Tree С0 С1 merge
- 11. © Copyright 2014 Andrey Smirnov LevelDB memtable Log Level 0 SST SSTSST Level 1 Level 2 SST SST SST SSTSST SST SST SST … Level 3 … …
- 12. © Copyright 2014 Andrey Smirnov LevelDB • memtable - в памяти, только последние операции, ограничено в размере • Log - для восстановления memtable • SST - отсортированные ключ-значения, неизменяемый • Level-0 - возможно пересечение
- 13. © Copyright 2014 Andrey Smirnov LevelDB • Level1-LevelN: 10^L MB • Level1-LevelN: непересекающие ключи • Маркеры удаления • Level0 ⇛ N: “молодые” ключи ⇛ “старые” ключи • Сжатие: Snappy
- 14. © Copyright 2014 Andrey Smirnov Compaction: Level-0 Level 0 SST SSTSST Level 1 Level 2 SST SST SST SSTSST SST SST SST Level 3 … …
- 15. © Copyright 2014 Andrey Smirnov Compaction: Level-0 Level 0 SST SSTSST Level 1 Level 2 SST SST SST SSTSST SST SST SST Level 3 … … SST
- 16. © Copyright 2014 Andrey Smirnov Compaction: Level-1+ Level 0 SST SSTSST Level 1 Level 2 SST SST SST SSTSST SST SST SST Level 3 … … SST
- 17. ? © Copyright 2014 Andrey Smirnov Как выполнить слияние эффективно? ! Чем ограничен объем данных при слиянии?
- 18. © Copyright 2014 Andrey Smirnov Типовые операции • Поиск • Вставка • Удаление
- 19. © Copyright 2014 Andrey Smirnov SST data block 0 data block 1 … data block N index block 0 index block 1 … index block N key value key value bloom filter last_key offset last_key offset
- 20. © Copyright 2014 Andrey Smirnov Кто использует LevelDB • Google BigTable (родоначальник) • WebKit: LocalStorage • Riak: LevelDB • HyperDex: HyperLevelDB • …
- 21. © Copyright 2014 Andrey Smirnov Ввод-вывод • Только последовательная запись • Можем записать одно значение несколько раз в процессе слияний • Чтение - потенциальный поиск по уровням
- 22. © Copyright 2014 Andrey Smirnov Bloom Filter
- 23. ? © Copyright 2014 Andrey Smirnov Для чего еще может пригодиться bloom filter?
- 24. © Copyright 2014 Andrey Smirnov Страничный ввод-вывод • Страница - основная единица ввода-вывода • Размер страницы - несколько килобайт • Оптимизация ввода-вывода за счет более крупных блоков • Страница содержит данные (или индексы)
- 25. © Copyright 2014 Andrey Smirnov Buffer Pool 0 1 11 12 2 3 13 14 4 5 15 16 6 7 17 18 8 9 19 20 10 21 Диск Память dirty dirty
- 26. © Copyright 2014 Andrey Smirnov Buffer Pool • Кеш диска (уменьшает чтение) • Кеш записи (уменьшает запись) • Свойство локальности/Working set • Что если отказ?
- 27. © Copyright 2014 Andrey Smirnov Write Ahead Log 0 1 8 9 2 3 10 11 4 5 12 13 6 7 14 15 dirty dirty buffer pool WAL Операция записи Диск 1 2
- 28. ? © Copyright 2014 Andrey Smirnov Почему в WAL запись идет в первую очередь?
- 29. © Copyright 2014 Andrey Smirnov Crash Recovery 0 1 8 9 2 3 10 11 4 5 12 13 6 7 14 15 WAL Диск replay
- 30. © Copyright 2014 Andrey Smirnov Snapshot 0 1 8 9 2 3 10 11 4 5 12 13 6 7 14 15 buffer pool WAL Диск Snapshot
- 31. © Copyright 2014 Andrey Smirnov Buffer Flusher 0 1 8 9 2 3 10 11 4 5 12 13 6 7 14 15 dirty dirty buffer pool Диск buffer flusher ≤50% dirty
- 32. ? © Copyright 2014 Andrey Smirnov Какие dirty страницы следует сбросить в первую очередь? ! А какие не-dirty страницы?
- 33. © Copyright 2014 Andrey Smirnov Примеры использования • BerkleyDB
- 34. © Copyright 2014 Andrey Smirnov HDD vs. SSD
- 35. © Copyright 2014 Andrey Smirnov HDD • Seek time (3-15ms) • Rotational delay (3-4ms) • Transfer • 70-200 random IOPS
- 36. © Copyright 2014 Andrey Smirnov SSD • Read-Erase-Write • Blocks, pages • Over-provisioning • Write amplification • > 5000 IOPS