Методы использования СУБД в интернет-приложениях. Лекция 3. Кеширование. Осипов Константин

Осипов Константин рассказывает о кешировании.

1. Случай в квадрате 36-80
2. BitCask: архитектура AOF
3. BitCask: архитектура keydir
4. Sophia архитектура
5. Links
6. Алгоритм Least Recently Used
7. Простой LRU: контрпримеры
8. Midpoint insertion strategy
9. Ski rental problem
10. Ski rental problem – online algorithm
11. Best online algorithm for sri-rental
12. Идея
13. Понятие c-competitive
14. Paging: идеальный offline алгоритм
15. Худший случай LFD
16. LFD: доказательство идеальности
17. Аппроксимируем LFD: FIFO
18. FIFO: эффективность
19. Другие алгоритмы и их оценки
20. FIFO: парадокс Belady
21. Зачем нужно понятие conservative
22. Понятие консервативного алгоритма
23. Консервативный алгоритм: оценка
24. Рандомизированный алгоритм: MARK
25. MARK: стоимость
26. MARK и LRU: сравнение