System Design
Search Systems
Зачем нужен поисковый движок
**Почему SQL LIKE недостаточно?**
Проблемы: 1. **Full table scan** - O(n), нет индекса 2. **Нет ранжирования** - все результаты равноценны 3. **Точное совпадение** - "headphone" не найдёт "headphones" 4. **Нет typo tolerance** - "headphons" → ничего 5. **Нет synonyms** - "earbuds" не найдёт "headphones"
**Возможности Search Engine:** | Feature
| **Full-text search** | Поиск по словам, не подстрокам | | **Relevance ranking** | Лучшие результаты сверху | | **Fuzzy matching** | Tolerance к опечаткам | | **Synonyms** | "laptop" = "notebook" | | **Stemming** | "running" → "run" | | **Faceted search** | Фильтры по категориям | | **Autocomplete** | Suggestions при вводе | | **Highlighting** | Подсветка найденных слов |
Что вы узнали о Зачем нужен поисковый движок?
Inverted Index
**Inverted Index - основа полнотекстового поиска** Обычный индекс: document → words Inverted index: word → documents Это как алфавитный указатель в книге: - Слово "algorithm" → страницы 15, 42, 89 - Слово "database" → страницы 23, 45, 67
**Text Analysis Pipeline:**
**N-grams для autocomplete и fuzzy:**
Что вы узнали о Inverted Index?
Elasticsearch Architecture
**Elasticsearch - distributed search engine** Основа: Apache Lucene (Java библиотека для полнотекстового поиска) Компоненты: - **Cluster** - группа nodes - **Node** - один сервер ES - **Index** - аналог database - **Shard** - partition индекса - **Document** - JSON запись (аналог row)
**Sharding Strategy:**
**Важно:** число primary shards фиксируется при создании индекса! Изменение требует reindex.
**Node Roles:** | Role
| **Master** | Управление cluster state, create/delete indices | | **Data** | Хранение данных, выполнение search/index | | **Ingest** | Pre-processing documents (pipelines) | | **Coordinating** | Routing requests (default for all nodes) | | **ML** | Machine learning jobs |
Что вы узнали о Elasticsearch Architecture?
Ranking и Relevance
**Как определить релевантность?** Основные факторы: 1. **TF (Term Frequency)** - частота слова в документе 2. **IDF (Inverse Document Frequency)** - редкость слова в коллекции 3. **Field length** - короткие поля важнее 4. **Boost** - ручное усиление полей
**BM25 - улучшенная версия TF-IDF** Проблема TF-IDF: TF растёт линейно (10 повторений = 10× score) BM25 добавляет: - **Saturation** - TF насыщается (после 5 повторений почти нет роста) - **Field length normalization** - короткие titles важнее длинных descriptions
Elasticsearch использует BM25 по умолчанию с версии 5.0.
**Function Score - custom ranking:**
Это позволяет учитывать: популярность, свежесть, цену, геолокацию.
Что вы узнали о Ranking и Relevance?
Advanced Search Features
**Autocomplete (Search-as-you-type)** Три подхода: 1. **Edge N-grams** - индексируем префиксы 2. **Completion Suggester** - специальная структура 3. **Search-as-you-type field** - готовый тип поля
**Fuzzy Search - tolerance к опечаткам**
**Levenshtein Distance:** - "headphons" → "headphones" (distance = 1, insert 'e') - AUTO: 0 edits for 1-2 chars, 1 for 3-5, 2 for >5
**Highlighting - подсветка результатов:**
Что вы узнали о Advanced Search Features?