Стендап Сьогодні

Що я зробив, що я хочу зробити, і що це все значить.
Повсякденні здобутки в форматі стендапу.
Детальніше в статті

Підписатись на RSS
📢 Канал в Telegram @stendap_sogodni
🦣 @stendap_sogodni@shevtsov.me в Федиверсі

04.09.2023

Пригоди з живленням через USB-C

Напередодні випуску iPhone 15, який, за всією логікою, буде мати порт USB-C, хотілося б проговорити пару нюансів з використанням USB-C для зарядки. ʼ

Бо в USB-C не тільки безліч протоколів та режимів для даних, але й з живленням теж не все просто. Якщо коротко, то в кабелі USB-C є пара жил, по якій пристрій повідомляє зарядці, яку напругу він очікує.


03.09.2023

Для чого гарний ElasticSearch?

Нарешті, з цими новими знаннями, можу відповісти на питання — що (окрім повнотекстового пошуку) доцільно робити на ElasticSearch.


02.09.2023

Чим пошук в ElasticSearch відрізняється від PostgreSQL

Наступне для мене питання — в PostgreSQL теж є індекси. Чим тоді ElasticSearch краще?

Взагалі, якщо почитати документацію про PostgreSQL, або подивитись це гарне відео, то можна помітити, що аналоги індексам ElasticSearch тут теж є. Індекси GIN то є інвертований словник, який теж зберігає групу документів, в яких є те чи інше слово. Індекси GiST то більш-менш те саме дерево пошуку, як ElasticSearch використовує для чисел та геолокацій.

Щоправда, я не бачив, щоб GIN/GiST використовували для простих значень — рядків або чисел — так, як це робить ElasticSearch. Ну, може я чогось не знаю. Але річ не в тім. Як я розумію, справжня перевага ElasticSearch у швидкому поєднанні багатьох індексів.

Як я вже писав, ElasticSearch для кожного ключового слова зберігає бітову мапу документів, які йому відповідають. Це значить, результати роботи всіх умов пошуку мають форму бітових мап. Бітові мапи можна надзвичайно швидко обʼєднувати бітовими (тобто логічними) операціями — щоб отримати остаточну множину документів, які відповідають всім умовам — результат пошуку.

Бітові мапи настільки ефективні, що PostgreSQL їх теж використовує. Мабуть, доводилось в EXPLAIN бачити назву bitmap scan? Щоб поєднати два індекси (а точніше, дві умови, що їх використають), PostgreSQL будує бітові мапи для рядків, які відповідають кожній умові та поєднує їх бітовими операціями.

Тільки різниця в тому, що в ElasticSearch бітові мапи завжди готові до використання, а PostgreSQL ще має їх побудувати з індексу. Та також, в PostgreSQL дані нормалізовані, тому їх доведеться зводити до купи з різних таблиць, де будуть використані різні індекси, які вже так просто не поєднаєш.

До того ж PostgreSQL підтримує транзакції, а це значить, що для кожного рядка він має також перевірити, чи рядок видимий поточній транзакції (в тому числі чи не видалений він.) В ElasticSearch такий крок не потрібний, а перевірка на видалення робиться ще одною бітовою мапою. (До речі, в обох базах оновлення запису відбувається через видалення старої та додавання нової версії.)

Отже, зорієнтованість на швидкий пошук за багатьма умовами, денормалізація та відсутність транзакцій робить ElasticSearch швидше за PostgreSQL.


01.09.2023

Як OpenSearch індексує числа

Вчора я написав трохи застарілу інформацію: насправді десь з 2016 року Lucene вже не зберігає числа у вигляді рядків. Тобто, така можливість залишилась, але тепер є інший спосіб індексування: k-d дерево. Я не пишу “кращий”, бо все залежить від того, що з ним робити.

K-d дерево це дерево множин точок у K-вимірному просторі. Кожен рівень дерева ділить множину навпіл за одним з вимірів. Таким чином, дерево є збалансованим, тобто має рівну кількість точок в кожній гілці — а значить, мінімальну кількість розгалужень.

Але ми хотіли індексувати числа. До чого тут якісь простори? Так, технічно число задає точку в 1-вимірному просторі, а узагальнення на багато вимірів дозволяє використати ту саму структуру даних також для географічних координат, діапазонів та інших застосувань, де важливо порівнювати одночасно декілька показників. У випадку чисел, дерево просто ділить діапазон навпіл, поки не досягне зазначеного розміру множини, що залишається.

В Lucene K-d дерева зберігаються окремо від інвертованого індексу (словника, про який я писав вчора.) Тобто заради ефективності пошуку архітектори впровадили цілу нову структуру даних та формат файлу. З цього боку зрозуміло, чому обрали саме k-d дерева, які покривають багато потреб, а не тільки пошук чисел.

Пошук в K-d дереві відбувається завжди за діапазоном. Кожний вузол дерева визначає діапазон значень всередині. Він може бути або цілком всередині, або цілком ззовні, або перетинати діапазон пошуку. Ті вузли, що всередині, додаються до результату, ззовні — відкидаються, та тільки в ті, що перетинають, доведеться спускатись на наступний рівень та дивитись на менші підмножини. Таким чином ми маємо справу з найбільшими можливими множинами, та відповідно — з найменшою їх кількістю.

Тепер, про доцільність такого індексу в контексті чисел. Якщо вам потрібно шукати числа за діапазоном, то він ефективний, питань нема. А якщо числа — це ідентифікатори, а шукати потрібно тільки по рівності, то алгоритм залишиться такий самий — хоч для діапазону з одного значення. Ба більше, оскільки множини в k-d дереві не доходять до такої деталізації, то наприкінці пошуку відбувається перебір — не дуже великий, але все ж зайвий.

Тому для індексації чисельних ідентифікаторів краще брати тип keyword. Тоді для них буде використаний звичайний інвертований індекс, оптимізований саме для пошуку конкретного значення.


31.08.2023

Основа архітектури ElasticSearch, або: чому він такий спритний?

Вирішив для себе зрозуміти, в чому ж така перевага ElasticSearch (та OpenSearch, який є його відгалуженням) по швидкості індексування та пошуку. Розповім про головне.

ElasticSearch побудований на рушії пошуку Lucene. Дуже цікаво, що базова можливість в Lucene вузька: це словник документів за ключовими словами. Як пишуть в цій статті, інші типи пошуку реалізовані через той самий словник — через пошук ключових слів або їх префіксів. (Тут хотілося б ще дорозслідувати.)

Ну, добре, пошук в словнику — операція добре вивчена, двійковий пошук в університеті проходять. Але типовий запит потребує пошуку не за одним, а за декількома словами. Тобто множини документів від кожного слова ще потрібно буде поєднати. Щоб робити це ефективно, Lucene, як пишуть тут використовує для множин… добре мені знайомі бітові мапи. Ось він, секрет швидкості!

Якщо підсумувати:ElasticSearch будує інвертований індекс, тобто словник ключових слів та до кожного слова — множину документів, які його містять. Кожна множина документів має форму бітової мапи, тому їх можна дуже швидко поєднувати між собою різними операціями. Я багато спростив, але базова ідея така.


30.08.2023

Ruby - не найкраща скриптова мова, якщо працюєш з великими файлами

Невеликий сюжет з сьогоднішньої практики. Потрібно було загнати близько 5 мільйонів рядків JSON з файлу в OpenSearch… тільки не по одному — бо зовсім довго — а пачками. Файл займає 2 ГБ, відповідно рядки десь по 400 байтів кожний, але довжина змінна (в кожному рядку — обʼєкт JSON.) До речі, в GZip цей же ж файл займає тільки 70 МБ. Стискайте ваш JSON!

Почав робити це на Ruby - бо простіше за все. Відкрив файл, читаєш собі методом each_line, збираєш пакет та відправляєш. От тільки чомусь працювало це дуже повільно. Пакет з 10 Мб збирався близько хвилини.

Подумав, що може each_line повільно читає, бо йому треба шукати на перенесення рядка. Спробував прочитати весь файл — методом readlines, а потім вже спокійно їх обробляти. Це ситуацію не покращило. Моя підозра лягла на виділення памʼяті при наборі пакета.

Тоді, думаю, скрипт дуже простий — перепишу його на Go. Тут теж є bufio#ReadLine. А головне, що в Go можна виділити памʼять для всього буфера одноразово, а потім потроху його наповнювати. Для цього є третій аргумент функції make: зарезервована місткість.

Далі все пішло добре та після декількох експериментів документи були імпортовані. Для мене висновком стало те, що, якщо вже потрібно обробити такий великий файл, то можна відразу писати скрипт на Go та уникнути проблем з памʼяттю.

(До речі. На Ruby моєю помилкою було те, що я відразу збирав пакет в один рядок. Це й призводить до зайвого виділення памʼяті. Вирішити можна так: збирати рядки в масив, а потім єднати операцією join. Але, на мою думку, урок залишається.)


29.08.2023

Типи клавіш механічних клавіатур

В доповнення до попереднього поста, хотів пройтися по типах клавіш. Бо все ж клавіші це не менший компонент досвіду, ніж перемикачі. Та, при виборі клавіш треба в першу чергу дивитись не на колір та шрифт, а на форму, тобто профіль.

Особливо важливо дивитись на профіль, коли хочеш замінити клавіші частково — наприклад, встановити модні стрілочки. Незлагода не буде ані зручною, ані красивою.

Також, коли шукаєш заміну на свою клавіатуру, вкрай важливо знати, що “широкі” кнопки (наприклад, Shift) можуть бути різної ширини, та перевіряти, що набір на заміну міститиме ті, що потрібні. З останньою заміною я вже перевіряв-перевіряв, і все одно проґавив правий Cmd, який на Keychron Q1 має одинарну ширину, а в наборі такого не було. Але це ще не так погано, як відсутній Shift чи Backspace.


28.08.2023

Модифікація Markdown зі збереженням оригінального синтаксису

Окрім того, щоб парсити, мені ж ще потрібно вносити в документ зміни. Плани поки прості: коли задача створюється, додати їй поточну дату як дату початку: ➕ 2023-08-28. Коли задача є завершеною (має маркер), то дату завершення: ✅ 2023-08-28. Логіка зрозуміла, але як це реалізувати на практиці?

Швидко зрозумів, що підхід “розібрати текст на AST, поміняти та зібрати наново” не працює. Парсер Remark не зберігає повну інформацію про розмітку: як приклад, заголовки можна вказувати або # решітками, або рядком === під заголовком. І те, і те стає в AST просто “заголовком”. Потім при відтворенні Markdown отримуємо заголовки в форматі, який було задано опціями. Одним словом, користувач отримає стандартизований варіант свого файлу. Що буде дивно, бо ми тільки хотіли додати дату в єдиний рядок з задачею.

…Проте дещо Remark зберігає. А саме, кожен вузол дерева посилається на діапазон символів у вхідному тексті, з яких він був утворений. Тобто хоч відтворити оригінал ми не можемо, але можемо просто скопіювати ті фрагменти оригіналу, які лишились без змін. На практиці це означає всі фрагменти, крім задачі, до якої ми додаємо дату.

Таке рішення дуже нагадує віртуальну DOM, знайому по React та інших бібліотеках. Там ми теж хочемо зберігати якнайбільше документу без змін.


27.08.2023

Розширення парсера Remark

Останній раз я писав про Remark з точки зору споживача. Проте, довелося також його й дописувати. Документації тут бракує, а екосистема складна, тому не так вже воно й легко.

Мені, власне, потрібно впровадити підтримку знайомого по GitHub синтаксису задач - [ ] To do. Для такого вже є рішення. Проте є нюанс: в Obsidian дозволено ставити статусом задачі не тільки хрестик, але й інші символи (наприклад, - для скасованих задач.) А всі плагіни, що існують, мають семантику “пробіл або хрестик”. Тому взяв за основу gfm-task-list-item та модифікував його так, щоб інші символи теж були дозволені.

Перший сюрприз - Remark використовує парсер micromark. Нестандартний синтаксис майже напевно потребує особливої обробки токенів, тому доведеться робити розширення для Micromark, що мене здивувало, бо це ціла окрема бібліотека (збирався робити на Remark, а опинився в Micromark). Micromark це взагалі повноцінний парсер, але Remark бере від нього саме токенізатор.

Доповнення для токенізатора складається з символу-тригера та логіки, яка споживає символи та генерує токени власних типів. Так, доповнення gfm-task-list-item споживало маркер задачі та перевіряло, чи то пробіл або хрестик. Якщо так, то генерувало токен “задача зроблена/не зроблена”, а в протилежному чині — відмовлялася від обробки. Я поміняв це на простішу логіку, що просто зберігає символ між квадратними дужками в токен taskListItemValue.

Щоб перетворити ці токени на елементи дерева AST, потрібне друге доповнення для іншого етапу, яке називається тут fromMarkdownExtension. Таке доповнення реагує на потік токенів та будує дерево. Відповідно, в моєму випадку воно слухає вихід з taskListItemValue (тобто коли вже відомо, що токен прочитаний повністю) та переносить символ маркера з токена в атрибут вузла listItem.

Все це треба робити тому, що без особливої обробки рядок [ ] не є вірним Markown - це посилання без адреси. Тому не можна просто шукати його в тексті вже по готовому дереву.


26.08.2023

Починай з простого

Хочу звернути увагу на одну професійну ваду, яку за собою помічаю. Коли переді мною стоїть великий проєкт, але більш-менш зрозуміло, що має вийти в кінці, то я починаю робити його, скажімо, від початку та до кінця. А мав би робити від простого до складного.

Проілюструю. Для розробки дерева задач для Obsidian потрібно з документів витягати задачі. Кожна задача має назву — це, власне, той текст, яким вона підписана. Поки все ясно.

Але… тексту може бути більше одного рядка. Або не бути зовсім. Або це не текст, а блок коду, чи заголовок, чи зображення. А також в тексті може бути форматування, посилання, ті ж самі зображення… Markdown все це дозволяє.

Підхід, який я вважаю вадою, це відразу намагатись покрити всі можливі комбінації синтаксису. Їх же ж вигадувати не треба — все відомо. От тільки вигадати код, який все покриває, непросто, та й взагалі, незрозуміло, як підступитись. Навіть маленький шматок (такий, як обхід дерева в пошуці задач) - складна задача, якщо вона має покривати всі можливі варіанти.

Краще, на мою думку, взяти найпростішу ситуацію: коли в документі є тільки список задач, та кожна задача має тільки один рядок опису з чистого тексту. Далі — потроху ускладнювати (наприклад, дозволити більше одного рядку тексту.)

Мені це здається контрінтуїтивним: якщо я знаю майбутні умови, навіщо мені свідомо ігнорувати їх та писати код, який гарантовано доведеться переписувати? Чи не зайва то робота? В тому й справа, що поступовий рефакторинг дає кращий код, ніж спроби відразу передбачити все.

Наступного разу пропоную планувати роботу від найпростішої реалізації до повної.

(Так, я розумію, що це приблизно те, що радить TDD.)