Детермінізм і програмне забезпечення: витяг, перетворення та завантаження (ETL)

Вітаю, я програміст і працюю переважно з Back-end і Java-стек, займаюсь батч-джобами, в минулому житті к.т.н.

Чому пишу?

Детермінізм — та річ, над якою «зламано багато списів» у філософів, проте з якою рідко маєш справу в реальній розробці. Нещодавно мав досвід покращення з цього питання для програми, що вибирає гео-дані, обробляє їх та зберігає до вихідних файлів. Хочу поділитись досвідом з питання детермінізму та ПЗ.

Що таке детерміністина програма?

Наразі поширене визначення детерміністичного алгоритму:

«В інформатиці детермінований алгоритм — це алгоритм, який, з урахуванням конкретних вхідних даних, завжди буде видавати на виході ті ж самі вихідні дані».

Дамо своє визначення для програми: «Детерміністична програма — це програма, результат роботи якої залежить виключно від вхідних даних та початкового коду програми».

Для детерміністичної програми виконується:

f1(x) = f2(x) = f3(x)                                                                                      (1)

де f1, f2, f3 — результати (вихідні дані) послідовних повторних запусків програми f, х — вхідні дані.

Чи завжди потрібен детермінізм?

Для більшості (відомих мені) програмних засобів детермінізм не є необхідністю.

Розглянемо приклад. Візьмемо zip-архіватор. Припустимо він з одного й того ж вхідного файлу робить побітно різні архіви. Але забезпечує достатню швидкодію та ступінь стискання. Чи він гірший за той архіватор, що будь-якого дня робитиме по-бітно однаковий файл, але менш продуктивно?

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

Коли детермінізм програми справді бажаний програмісту?

По-перше, для тестування. Набагато простіше тестувати програму що завжди дає однаковий вихід. По-друге, так легше рефакторити «наосліп». Тому що при зміні результатів зрозуміло, що логіка змінилась. Також легше досліджувати регресії.

Кому детермінізм буде корисний в першу чергу?

Як на мене, питання детермінізму може бути корисно в першу чергу програмістам систем, що «продають» не програму як таку, а її результат (вихідні дані) і тестування цих даних дорого коштуватиме. Зазвичай такі програми є batch job, зокрема Extract, Transform, Load (ETL) або Витяг, Перетворення та Завантаження.

Що таке Програмне Забезпечення Витяг Перетворення та Завантаження (ETL)?

Extract, Transform, Load (ETL) або Витяг, Перетворення та Завантаження — процес, який використовується в базах даних та, особливо, у сховищах даних та у засобах Business Intelligence для забезпечення їх роботи в тому числі для підтримки прийняття рішень. ETL-процес, як концепція, набув поширення у 1970-х роках.

Він охоплює наступні етапи обробки даних:

1. Виймання даних із зовнішніх джерел.
2. Перетворення даних, для зберігання даних у відповідній структурі або форматі, з метою подальшого аналізу.
3. Завантаження даних у кінцеву базу даних. Більш точно, це може бути вітрина даних або сховище даних.

Для Extract, Transform, Load (ETL) або Витяг, Перетворення та Завантаження часто вартість перезапуску програми є досить високою, так само високою є вартість перезапуску кожного з етапів процесу, включаючи тестування.

Коли детермінізм потрібен для ETL-програм?

Для Extract, Transform, Load (ETL) або Витяг, Перетворення та Завантаження часто вартість перезапуску програми є досить високою, так само високою є вартість перезапуску кожного з етапів процесу, включаючи тестування.

Детермінізм для ETL бажаний в тому числі бо він може зменшити витрати на прогон тестів та повторний запуск.

Наприклад, уявимо задачу створення вбудованих мап для автомобілів компанії Example-Automotive*. Ці мапи будуть завантажуватись безпосередньо до комп’ютера автомобілів на СТО. Раз в півроку їх хочеться оновлювати.

Для цього програма створює якісь файли географічної інформації згідно ISO GDF 5.0 з реляційної Бази Даних (БД) OpenStreetMap*. Скажімо для кожного міста (Дніпро, Запоріжжя*) раз на квартал створюються окремі GDF-файли.

Ці GDF-файли будуть потім використовуватись якимись транспортними засобами Example-Automotive*.

Перш ніж завантажити ці файли до авто їх багаторазово перевірятимуть на відповідність формату, на розміри (кожного блоку), інтеграцію, відповідність реальності. Це можуть робити автоматизовано та «вручну». Потім Example-Automotive* відправить водія на авто за тестовими маршрутами. Все це досить дорого. А якщо мапа попереднього кварталу змінилась у м. Дніпро та не змінювалась у м. Запоріжжя то до м. Запоріжжя водій може і не їхати?

Якщо GDF-файл збігається з вже перевіреним раніше, то відпадає потреба у повторному проїзді водієм-тестувальником маршруту.

Які основні причини недетермінізму програм?

Існує думка, що (1) виконуються для всіх добре написаних програм. Але чи це так?

Вікіпедія дає основні причини не детермінізму алгоритму:

«Якщо він використовує зовнішні стани, окрім вхідних даних, таких як введення даних користувачем, глобальна змінна, апаратний таймер значення, випадкове значення, або дані, збережені на жорсткому диску. Якщо він діє таким чином, що, наприклад, якщо він має кілька процесорів, які записують одні й ті ж самі дані у один і той самий час. В даному випадку, точний порядок, в якому кожен процесор записує дані будуть впливати на результат. Якщо апаратна помилка призводить до зміни стану»

Справді, перша проблема, на яку я спотикався, це дата та час. Особливо, коли використовують системні. Часто дата/час запуску програми прямо йде у вихідний файл. Інколи — опосередковано. Наприклад, можуть вилучатись «застарілі» дані про стан доріг, бо їх «відремонтував» УкрАвтодор* згідно з планом. Часові пояси різних ЕОМ при паралельному процесі теж впливають. Також всі базові функції з часом мають похибку, інколи суттєву.

Джерелом не детермінізму можуть бути й інфраструктурні збої. Програми можуть припиняти роботу через обмеження по пам’яті, часу виконання, тощо. Опустимо їх всі.

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

Розглянемо питання детермінізму, що виникали на етапах ETL, які є наслідком програми (чи можуть бути розв’язані програмою).

Чи може Витяг (Extract) вносити не детермінізм?

Почнемо з БД. З неї буде потрібно витягти дані. Найчастіше виникає потреба додавати сортування. Розглянемо приклади. Маємо наступний код (мова SQL*):

  
  create table S(id string, name string)                 ; --                                           (2) 
  insert into S(id, name) values (‘1’, ‘001’)            ;--                                            (3)
  insert into S(id, name) values (‘2’, ‘002’)            ;--                                            (4)

--   …

  insert into S(id, name) values (‘k’, ‘k’)                 ;--                                            (5)
  create table B                                                       --                                            (6) 
           as select * from table S                               ;--                                            (7)
  create table C (id string, name string)                 ;--                                            (8)
  insert into C select * from B                                 ;--                                            (9)

-- ...

  select name from S where rownum < 10             ;--                                           (10)

Як щодо детермінізму (6)..(9)? Інколи можливі нюанси, бо всі колонки мають однаковий тип і бувають неочікувані результати, переважно якщо хтось змінив DDL, але все ж.

Чи є (10) детерміністичним? Ні. Бо БД не зобов’язана сортувати select-block.

А якщо додати PRIMARY KEY, index на id? Майже, але теж ні. Чому? Бо часто СУБД оптимізує запити для максимального перформансу. Наприклад, БД може використовувати heap organized table. Відповідно, і доступ є випадковим. Інколи можливі десь і кеші.

Добре, а якщо ось так:

select name from A where id between 1 and 10     ;--                                     (11)

Теж ні, бо інколи (можливо раз на сто запитів) буде спочатку другий, а потім перший. Тобто краще писати :

  
  select name from                                                        
   (select name, id from A order by id) 
   where rownum < 10
   order by id                                                               ;--                                  (12)

Подібних (10) запитів в ETL програмі можуть бути тисячі. І треба розуміти що за детермінізм кожної сплачується перформенсом. Часто ЕОМ є орендованими і швидкодія має значення на кошторис. Тому бажано додати order by тільки в критично важливі для детермінізму запити. А в які потрібно?

З іншого боку — на таблицю S не задавався UNIQUE CONSTRAINT на колонку id. Якщо бувають два записи з однаковим id то запит (12) теж не детерміністичний. Це теж часто буває проблемою. Створення constraint вимагає часу та ресурсів БД. Це знову ж таки швидкість і пам’ять. Часто краще проводити сортування по максимальній сукупності колонок:

   select name from A where d between 1 and 10 order by id, name  ...                                  (13)

Інколи порівняти записи обчислювально важко. Наприклад, якщо одна з колонок — геометрія. Відомі мені БД зберігають геометрії у вигляді BLOB. Їх можливо відсортувати по розміру BLOB в байтах. Але цього не завжди достатньо.

БД мають геометричні пакети, наприклад можуть створювати spatial index. На жаль, часто вони працюють повільніше за аналоги на C/Java. Також часто ліцензії обмежують кількість CPU, розмір пам’яті тощо. Часто має сенс підготувати додаткові колонки для сортування ще на етапі підготовки даних.

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

Чи може Перетворення (Transform) вносити недетермінізм?

Дані вибрали з БД, тепер їх треба обробити (етап transform). Тут також доводилось використовувати сортування.

Часто потрібно підібрати структуру даних. Наприклад, потрібно сконтанувати (12) від сіявши дублікати. Розглянемо код мовою Java*:

  
  as = new HashSet(результат (12))                 ;//                                                   (14)
  String acommon = “”                                        ;//                                                   (15)
  for (String s: as)                                                //                                                   (16)
       acommon = acommon + s.toString()          ;//                                                   (17)

  
   Set as = new LinkedHashSet(результат(12))   ;//                                             (18)
   String acommon = “”                                        ;//                                               (19)
   for (String s : as)                                              //                                                (20)
     acommon = acommon + s.toString()            ;//                                                (21)

Чим впровадження linked-hash-set проти hash-set краще? Бо для linked-hash-set цикл for-each іде в послідовності внесення. Відповідно якщо (12) детерміністичний то і (21) буде детерміністичним Чим заплатили? Linked-hash-set потребує додаткову пам’ять на тримання зв’язків.

А як щодо обробки, наприклад, stream API Java 8+*? Розглянемо приклад:

  as.stream()                                                       //                                 (22)
      .map(s -> map-function(s)                            //                                 (23)
       .filter(s -> check-function(s))                         //                                (24)
       .limit(5)                                                          //                                (25)
       .collect(Collectors.toList())                            //                                (26)

Чи цей код є детерміністичним?

Тут те ж саме, залежить від типу колекції та функцій map-function та check-function, для linked*/arraylist має бути детерміністичним.

А як щодо parallel-stream?

JavaDoc :

«Except for operations identified as explicitly nondeterministic, such as findAny(), whether a stream executes sequentially or in parallel should not change the result of the computation»

У помічених мною випадках використання parallelstream проти stream майже не вносить не детермінізм.

Інколи використовуються бізнес правила (Drools*) та моделі (Predictive Model Markup Language*, Excel); котрі обробляються стороннім ПЗ «з коробки». Наприклад, для Drools rule engine створює дерево рішень, при цьому він не зобов’язаний враховувати порядок правил у файлі. Для цього інколи існують пріоритети на правила, про які краще подбати заздалегідь. Часто це складно, бо моделі/правила приходять ззовні.

Multithreading є очевидним джерелом не детермінізму. Проте він досить рідко випливає «як грім серед неба». Часто паралелізм легко прибрати.

Чи може Завантаження (Load) вносити не детермінізм?

При завантаженні даних зустрічався з вже розглянутими питаннями з паралельністю, датами/часом, потребою перетворення до канонічного вигляду геометрії, сортуванням.

Також доводилось:

1. Примусово задавати версію формату вихідних файлів. Наприклад, бібліотеки sqlite часто йдуть «з коробки» Операційної Системи (ОС). Відповідно, оновлення ОС можуть призвести до зміни формату.
2. Примусово викликати vacuum у вихідній БД. Бо інакше БД може провести vacuum «коли заманеться». Тоді розмір вихідного файлу може бути не детерміністичним.
3. Інколи слід подбати і про детермінізм роботи клієнтського ПЗ. Наприклад, якщо ETL генерує правила про рекомендовану швидкість на ділянках дороги (мова Drools*-like).

  
rule "магістральна дорога ремонтується"
    when
     $ділянка: ДілянкаДороги(рекомендованаШвидкість == -1, ремонтується == “так”)
    then
     $ділянка.рекомендованаШвидкість = 50;
    end                                                                             //                                     (27)

rule "крута магістральна дорога"
    when
    $ділянка: ДілянкаДороги(рекомендованаШвидкість == -1, кутПоворота == “крутий”)
    then
     $ділянка.рекомендованаШвидкість = 40;
    end                                                                             //                                      (28)

Яка буде «ділянка.рекомендованаШвидкість», якщо виконуються обидва правила (27, 28)? Це залежить від rule-engine на стороні клієнта та інших генерованих правил. Має сенс додавати пріоритет (salience) до правил, що генеруються.

Як знайти джерело недетермінізму?

Для цього, на мою думку, слід мати «зліпки» даних на кожному етапі запусків ETL що різняться. Доведеться їх порівнювати. Дуже допомагають інтерпретовані мови програмування, зокрема я використовував Project Jupyter та Apache Zeppelin.

Висновки

1. Не детермінізм може вносити будь-який код на різних рівнях/модулях/етапах.
2. Для того щоб розв’язувати проблему не детермінізму треба запастись часом та терпінням.
3. Часто для того щоб зробити програму більш детермінізму доводиться платити її ефективністю (перформенс, пам’ять тощо).

Дякую за увагу.

Подяки: Д. Татаренко, О. Драбич за відгуки та рекомендації. А. Бережний за допомогу з перевіркою SQL.

Див. також:
www.ocoudert.com/...​e-software-deterministic
en.wikipedia.org/...​i/Deterministic_algorithm

Примітки:
(*) - назви вигадані, їх зв’язок з реальністю випадковий;
(**) - між послідовними стартами програми.
Оригінал доступен за лінкою

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті