Показаны сообщения с ярлыком bigdata. Показать все сообщения
Показаны сообщения с ярлыком bigdata. Показать все сообщения

воскресенье, 29 марта 2026 г.

Data Engineering on AWS Learning Plans

Метки: , , , , , , , , , ,
Это статья краткая заметка по курсу Data Engineering on AWS Learning Plans (includes labs)
В некотором роде - это аналог курса Инженер облачных сервисов Yandex, но, по ощущениям, имеет меньшую техническую составляющую.

Дальше »
0 коммент.

вторник, 17 июня 2025 г.

Памятка по ClickHouse

Метки: , ,
Краткие заметки курса Managed Service for ClickHouse
Дальше »
0 коммент.

воскресенье, 16 февраля 2025 г.

Dbt

Метки: , , , ,
Вводная статья о основных возможностях DBT.
Дальше »
0 коммент.

среда, 4 декабря 2024 г.

Инженер облачных сервисов Yandex

Метки: , , , , ,
Памятка на основе прохождения курса Инженер облачных сервисов (Сертификат)
Дальше »
0 коммент.

воскресенье, 3 ноября 2024 г.

Spark 3.2 - 4.1 preview - what's new

Метки: ,
A list of new features in Spark that I think are important for a developer.
Дальше »
0 коммент.

среда, 3 июля 2024 г.

Grokking System Design Interview for Engineers

Метки: , ,
Статья заметка, на основании прохождения курса Grokking Modern System Design Interview for Engineers & Managers (Сертификат)
Дальше »
0 коммент.

воскресенье, 28 апреля 2024 г.

ClickHouse vs Spark в Яндекс облаке

Метки: , , , , ,
Часто для DA/DS нужно расчитать множество разрезов одного агрегата.
При расчете не нужны join, но наличие distinct не дает свести к подходу от большего к меньшему.
В этой заметке попытался понять степень преимущества ClickHouse перед Spark и где есть недостатки в реалиях ЯО (спойлер: стоимость и IO при работе с S3).
Дальше »
0 коммент.

четверг, 28 марта 2024 г.

CDC репликация средствами Debezium и Kafka Connect

Метки: , , , ,
Настрока CDC репликации данных между реляционной бд MySql и Kafka
Дальше »
0 коммент.

воскресенье, 7 мая 2023 г.

Памятка по Docker и Kuber

Метки: , , , , , , ,
Дальше »
0 коммент.

четверг, 13 января 2022 г.

Книга: Высоконагруженные приложения. Программирование, масштабирование, поддержка

Метки: , , , , , , , , ,
Это не пересказ всей книги, а краткие заметки, особо запомнившихся разделов.
Дальше »
0 коммент.

среда, 28 июля 2021 г.

Azure: Databricks vs HDInsight

Метки: , , , ,
В облаке MS Azure есть 2 простых способа организовать кластер Spark - это Databricks и HDInsight.
Дальше »
0 коммент.

вторник, 5 января 2021 г.

Оптимизация Spark Scala UDF

Метки: , , , , ,

Проблемы Scala UDF

1. UDF - черный ящик для Codegen: представляет из себя вызов java функции и не встраивается в wholestagegen
2. Нет возможности not null оптимизации
3. UDF не может быть спущена на уровень файлов (predicate pushdown)
4. Конвертация UTF-8 строк Spark в UTF-16 строки JVM при передаче параметров и получении результата.

Дальше »
0 коммент.

пятница, 21 августа 2020 г.

BigData анализ с помощью Spark и Scala

Метки: , , , , , ,
В этой статье я хотел бы охватить основные аспекты работы с фреймворком Spark
Дальше »
1 коммент.

пятница, 27 марта 2020 г.

Oracle DataMiner ML в сравнении с Python sklearn

Метки: , , , , , ,
В этой статье хочу посмотреть на ML опцию, встроенную в Oracle 12.
Дальше »
0 коммент.

среда, 26 февраля 2020 г.

Работа с Kafka через Spark Structure Streaming

Метки: , , , , , , ,
Памятка по чтению данных из Kafka топика средствами Spark Structure Streaming

Дальше »
0 коммент.

суббота, 25 января 2020 г.

SQL заметки за 2019

Метки: , , , , ,
Продолжение цикла заметок и статьи 2016 года.
Хочу зафиксировать моменты Oracle и SQL в общем, которые достаточно интересны, но малы для отдельной статьи.
  • Трансформация запросов
    • Виды преобразований запросов
    • Результрующий запрос после всех преобразований оптимизатора
    • Ручная трансформаиця 1 запроса в другой
  • Статистика
    • Устаревание статистики
    • Инкрементальный сбор статистики в партицированных таблицах
    • Селективность колонки с 12.2
    • Хинт для задания статистики колонки
    • статистика по использованию сегмента
    • Ассоциация статистики к функции
    • Колонки-кандидаты для гистограммы
    • Просмотр данных гистограммы
    • Join cardinality по гистограмме
    • Определение селективности, если на обоих столбцах соединения есть гистограмма
  • PLSQL
    • Автономная транзакция
    • Иключение при поиске элемента по ключу
    • plsql redefinition
    • Консистентность функций
    • Параллелизация pipeline функций
  • PLSQL коллекции
    • Varrays - обычный массив
    • Hash table - Associative array над связанным списком
    • Nested tables
  • Анализ производительности запросов
    • индекс - кандидат на удаление
    • forall - в статистике (ash/awr)
    • Выявление skew через oem monitor
    • Пометка запроса для awr
    • Чтение плана
    • Монотонный рост значений в индексе
    • Долгий вызов plsql в запросе
    • Undo/redo при вставке
    • Параллельное последовательное чтение индекса
    • Result_cache
    • Вставка игнорируя consraint, но с сохранением ошибок
    • Пометка блока горячим
  • Оптимизация хранения
    • Создание not null поля с default
    • Index coalesce
    • Вставка в новую таблицу
    • Вставка в длинную таблицу
    • Include Индекс
    • Дополнительные параметры таблиц в Exadata
    • Отрицательная эффективность Exadata
    • Структура Lob
  • Партицирование
    • Системное партицирование
    • Reference partitions
    • Глобальные индексы
    • INDEXING OFF|On
    • Тепловая карта партиций
  • Настройки бд
    • Виды репликаций
    • Exadata 12.2
    • Особенности только в exadata
  • Разные SQL алгоритмы
    • Пагинация на ключах
    • start_of_group - нумерация групп по разрывам
    • Забор таблицы частями без fullscan, индексов и партиций
    • Поиск одного пропуска
    • Вставка данных больше размера varchar
    • partition join
    • Округление через to int
    • Удаление из обновляемого представления
    • Выражение на месте join
    • DBMS_HS_PASSTHROUGH - Полное выполнение запроса на удаленной бд
    • Top уникальных строк в группе
Дальше »
0 коммент.

понедельник, 19 августа 2019 г.

Оптимизация хранения данных в bigdata

Метки: , , , , , , , , , , ,
Дальше »
5 коммент.

воскресенье, 30 июня 2019 г.

Машинное обучение через решающие деревья

Метки: , , , , , ,
Это краткий пересказ курса: Введение в Data Science и машинное обучение с дополнением 2 тем: градиентный бустинг и решающие деревья в Spark.
Дальше »
2 коммент.

четверг, 29 ноября 2018 г.

Введение в Scala и параллельную разработку

Метки: , , ,
В этой статье я хотел бы охватить все аспекты работы с данными на языке Scala - от примитивов языка до параллельного программирования.
Дальше »
1 коммент.

четверг, 24 мая 2018 г.

LSM дерево: быстрый доступ по ключу в условиях интенсивной вставки

Метки: , , ,
В условиях интенсивной вставки для быстрого доступа к данным обычные btree индексы не подходят.
Во многих базах (Bigtable, HBase, LevelDB, MongoDB, SQLite4, Tarantool, RocksDB, WiredTiger, Apache Cassandra, и InfluxDB ) используется LSM-дерево (Log-structured merge-tree — журнально-структурированное дерево со слиянием)
LSM дерево служит для хранения ключ-значения.
В данной статье рассмотрим двухуровневое дерево. Первый уровень целиком находится в памяти, вторая половина на диске.
Вставка идет всегда в первую часть в памяти, а поиск из всех частей. Когда размер данных в памяти превышает определенный порог, то она записывается на диск. После чего блоки на диске объединяются в один.
Рассмотрим алгоритм по частям:

1. Все записи в дереве маркируются порядковым номером glsn , при каждой вставке этот счетчик увеличивается

Структура для хранения ключа-значения и порядкового номера:
//запись с ключ-значение
class SSItem {
 Integer key;
 String value;
 //+ идентификатор последовательности вставки
 Integer lsn;
 
 SSItem(Integer key, String value, Integer lsn) {
  this.key = key;
  this.value = value;
  this.lsn = lsn;
 }

2. Структуры объядиняются в одну таблицу в памяти.
В моем алгоритме используется хэш таблица.
В реальности чаще всего используется отсортированная по ключу структура - это дает преимущества, что для поиска и слияния используется последовательное чтение, вместо рандомного.
class MemSSTable { 
 
 //из-за хэша нет поиска по диапазону
 HashMap<Integer, SSItem> itms = new HashMap<Integer, SSItem>();

3. Т.к. размер памяти ограничен, то при превышении определенного порога, данные должны быть скинуты на диск.
В моей реализации - это простой вариант без фоновых заданий и асинхронных вызовов
При достижении лимита будет фриз, т.к. таблица скидывается на диск.
В реальных системах используется упреждающая запись: данные на диск скидываются асинхронно и заранее, до достижения жесткого лимита памяти.
 void SaveToDisk() throws FileNotFoundException, UnsupportedEncodingException {
  indx.path = "sstable_" + indx.max_lsn + ".dat";
  PrintWriter writer = new PrintWriter(indx.path, "UTF-8");
  Integer pad = 0;
  //последовательно пишем 10 байт с длиной значения и само значение
  for(Entry<Integer, SSItem> entry : itms.entrySet()) {
   SSItem itm = entry.getValue();
   String val = itm.get();
   writer.print( val );
   //регистрируем в индексе смещения в файле
   indx.keys.put(itm.key, pad);
   pad = pad + val.length();
  }
  writer.close();
  
  LSMTree.indexes.add(indx);
 } //SaveToDisk

4. Получается, что половина всех данных у нас хранится в хэше в памяти, а остальное в виде файлов на диске.
Чтобы не перебирать все файлы на диске создается дополнительная индексная структура, которая будет хранить метаинформацию о файлах в памяти:
//индекс над таблицей с даными
class SSTableIndex {
 //метаданные:
 //минимальный и максимальный ключи в таблице
 Integer min_key;
 Integer max_key;
 //минимальный и максимальный порядковый lsn
 Integer min_lsn;
 Integer max_lsn;
 
 //если таблица на диске, то путь до файла
 String path;
 
 //ключ - смещение ключа в файле
 HashMap<Integer, Integer> keys = new HashMap<Integer, Integer>();
 
 //добавить ключ в индекс
 void add(Integer k) {
  //также обновляем метаданные
  max_lsn = LSMTree.glsn;
  if(min_lsn == null) min_lsn = max_lsn;
  if(min_key == null || k < min_key) min_key = k;
  if(max_key == null || k > max_key) max_key = k;
  //добавление идет в память в хэш таблицу, на первом этапе смещения в файле нет
  keys.put(k, 0);
 }

5. Управляющий объект всего дерева хранит ссылку на таблицу с данными в памяти и на мета-индексы данных на диске:
public class LSMTree {
 
 static int glsn = 0;
 //максимальный размер, после которого таблица должна быть скинута на диск
 //для упрощения алгоритма = числу записей, а не размеру в байтах
 final static int max_sstable_size = 10; 
 
 //текущая таблица в памяти, куда вставляем данные
 MemSSTable MemTable;
 
 //все индексы, даже для таблиц на диске, хранятся в памяти
 static LinkedList<SSTableIndex> indexes = new LinkedList<SSTableIndex>();

6. Когда все объекты описаны, давайте посмотрим как происходит добавление нового элемента.
Добавление всегда идет в таблицу в памяти, что гарантирует быструю вставку:
public class LSMTree {
 //....
 
 //добавить запись
 public void add(Integer k, String v) {
  MemTable.add(k, v);
 }
Подробней логика добавления в таблицу в памяти:
* Увеличиваем глобальный счетчик элементов LSMTree.glsn
* Если число элментов превысило порог, то таблица скидывается на диск и очищается
В реальности это конечно не число элементов, а объем в байтах.
* Создается новый элемент SSItem
* И доблавляется в хэш массив
Причем, если элемент до этого уже существовал, то он перезаписывается.
В реальности хранятся все записи, чтобы была возможность поддержки транзакционности.
* Кроме этого в индексе обновляются метаданные indx.add
class MemSSTable { 
 //.....
 
 //добавить новый элемент
 void add(Integer k, String v) {
  //увеличиваем глобальный счетчик операций glsn
  LSMTree.glsn++;
  
  //если размер превышает, 
  if(itms.size() >= LSMTree.max_sstable_size) {
   try {
    //то сохраняем таблицу на диск
    //в реальных движках используется упреждающая фоновая запись
    //когда папять заполнена на N% (n<100), то данные скидываются на диск заранее, чтобы избежать фриза при сбросе памяти и записи на диск
    SaveToDisk();
   } catch (FileNotFoundException | UnsupportedEncodingException e) {
    e.printStackTrace();
    return;
   }
   //очищаем данные под новые значения
   indx = new SSTableIndex();
   itms = new HashMap<Integer, SSItem>();
  }
  
  //обновляем медаданные в индексе
  indx.add(k);
  
  SSItem itm = new SSItem(k, v, indx.max_lsn);
  
  //в моей реализации, при повторе ключ перезаписывается
  //т.е. транзакционность и многоверсионность тут не поддерживается
  itms.put(k,  itm);
  
 } //add
Если после вставки нового элемента старые данные оказались на диске, то в метаданных индекса прописывается ссылка на точное смещение в файле:
class SSTableIndex {
 //...
 
 //если таблица на диске, то путь до файла
 String path;
 
 //ключ - смещение
 HashMap<Integer, Integer> keys = new HashMap<Integer, Integer>();

7. С вставкой разобрались, теперь обратная операция - поиск элемента в дереве:
* Сперва мы проверяем наличие ключа в хэш таблице в памяти. Если элемент нашелся, то на этом все.
* Если элемента нет, то мы пробегамся по всем метаиндексам в поиске нашего ключа.
* проверяем, что ключ входит в диапазон indx.min_key - indx.max_key индекса
* И для полной точности проверяем наличие ключа в хэше ключей indx.keys.containsKey
* Если элемент нашелся, то это еще не конец, цикл продолжается, пока мы не переберем все индексы.
Т.к. ключ может добавляться несколько раз в разные промежутки времени.
* Из всех совпадений выбираем индекс с максимальным счетчиком вставки - это последнее изменение ключа
public class LSMTree {
 //.....
 
 //получить значение по ключу
 String getKey(Integer key) {
  //сперва смотрим в памяти
  String val = MemTable.getKey(key);
  
  if(val == null) {
   SSTableIndex indx_with_max_lsn = null;
   //потом таблицу по индексам, которая содержит наш ключ
   //если содержится в нескольких, то берем с максимальным lsn, т.к. это последнее изменение
   for (SSTableIndex indx : indexes) {
    Integer max_lsn = 0;
    if(key >= indx.min_key && key <= indx.max_key && max_lsn < indx.max_lsn ) {
     if(indx.keys.containsKey(key)) {
      max_lsn = indx.max_lsn;
      indx_with_max_lsn = indx;
     }
    }
   }
   //читаем из таблицы с диска
   if(indx_with_max_lsn != null) {
    try {
     return indx_with_max_lsn.getByPath(key);
    } catch (IOException e) {
     e.printStackTrace();
    }
   }
  }
  
  return val;
 }
* Определим нужный индекс обращаемся по нему к таблице на диске:
** Открываем нужный файл
В реальности, скорей всего, файы постоянно держатся открытыми для экономии времени.
** Следуя смещенями из индекса переходим к нужной точке файла file.seek
** И считываем значение file.read
class SSTableIndex {
 //...
 
 //получить значение ключа из открытого файла
 String getByPath(Integer key, RandomAccessFile file) throws IOException {
  //получаем смещение в файле для ключа из индекса
  Integer offset = keys.get(key);
  
  //смещаемся в файле
  file.seek(offset);
  
  //резервируем 10 байт под переменную с длинной значения
  byte[] lenb = new byte[10];
  file.read(lenb, 0, 10);
  
  Integer len = Integer.parseInt(new String(lenb, StandardCharsets.UTF_8));
 
  file.seek(offset + 10);
  
  //считываем значение
  byte[] valb = new byte[len];
  file.read(valb, 0, len);
  
  return new String(valb, StandardCharsets.UTF_8);
 } //getByPath
 
 //получить значение ключа с диска
 String getByPath(Integer key) throws IOException {
  if(!keys.containsKey(key)) return null;
  
  RandomAccessFile file = new RandomAccessFile(path, "r");
  
  String val = getByPath(key, file);
  
  file.close();

  return val;
 }

8. Т.к. ключ может вставляться неограниченное число раз, то со временем он может находится в нескольких файлах на диске одновременно.
Также, если бы LSM дерево поддерживало транзакционность, то в файлах также хранились бы разные версии одного ключа (изменения или удаления).
Для оптимизации последующего поиска применяется операция слияния нескольких файлов в один:
* Сортируем индексы по убыванию lsn
* Последовательно считываем элементы из первого индекса и записываем в новый
* Если элемент уже присутствует в объединенном индексе, то он пропускается
* Создается новый единственный файл и индекс со всеми ключами и значениями
* Старые файлы и индексы удаляются
public class LSMTree {
 //....
 
 //объединить несколько таблиц на диске в 1 большую
 void merge() throws IOException {
  Integer min_key = null;
  Integer max_key = null;
  Integer min_lsn = null;
  Integer max_lsn = null;
  
  //сортируем таблицы по убыванию lsn
  //чтобы вначале были самые свежие ключи
  Collections.sort(indexes, new Comparator<SSTableIndex>() {
   @Override
   public int compare(SSTableIndex o1, SSTableIndex o2) {
    if(o1.max_lsn > o2.max_lsn) {
     return -1;
    } else if(o1.max_lsn < o2.max_lsn) {
     return 1;
    }
    return 0;
   }
  });
  
  SSTableIndex merge_indx = new SSTableIndex();
  
  Integer pad = 0;
  merge_indx.path = "sstable_merge.dat";
  PrintWriter writer = new PrintWriter(merge_indx.path, "UTF-8");
  
  //пробегаемся по всем индексам, чтобы слить в 1
  for (SSTableIndex indx : indexes) {
   if(min_lsn == null || indx.min_lsn < min_lsn) min_lsn = indx.min_lsn;
   if(min_key == null || indx.min_key < min_key) min_key = indx.min_key;
   if(max_key == null || indx.max_key > max_key) max_key = indx.max_key;
   if(max_lsn == null || indx.max_lsn > max_lsn) max_lsn = indx.max_lsn;
   
   RandomAccessFile file = new RandomAccessFile(indx.path, "r");
   
   //т.к. данные в таблицах не упорядочены, это приводит к рандомным чтениям с диска
   //в реальности делают упорядочнный по ключу массив, чтобы делать быстрые последовательные чтения
   for(Entry<Integer, Integer> entry : indx.keys.entrySet()) {
    //оставляем запись только с максимальным lsn
    Integer key = entry.getKey();
    if(!merge_indx.keys.containsKey(key)) {
     String val = indx.getByPath(key, file);
     
     SSItem itm = new SSItem(key, val, 0);
     String itmval = itm.get();
     
     writer.print( itmval );
     merge_indx.keys.put(key, pad);
     pad = pad + itmval.length();     
    }
   }
   //записываем и удаляем старые файлы
   file.close();
   //delete
   File fd = new File(indx.path);
   fd.delete();
  }  
  
  merge_indx.min_lsn = min_lsn;
  merge_indx.min_key = min_key;
  merge_indx.max_key = max_key;
  merge_indx.max_lsn = max_lsn;
  
  writer.close();
  
  //переименовываем к обычному имени
  File fd = new File(merge_indx.path);
  merge_indx.path = "sstable_" + merge_indx.max_lsn + ".dat";
  File fdn = new File(merge_indx.path);
  fd.renameTo(fdn);
  
  indexes = new LinkedList<SSTableIndex>();
  indexes.add(merge_indx);
  
 } //merge
В моей реализации используется хэш массив, что дает большое число случайных чтений с диска.
В реальности данные хранят в отсотированной структуре, что позволят выполнять слияние 2 отсортированных массивов в один за линейное время используя только быстрое последовательное чтение.


Полный код класса LSM дерева можно посмотреть на github
0 коммент.
Подписаться на: Сообщения (Atom)