Author Archive

Степени двойки

Список степени двойки.

Степени двойки позволяют оценить алгоритмы, работающие за логарифмическое время.

Степень двойки (2x) Значение
01
12
24
38
416
532
664
7128
8256
9512
101 024
112 048
124 096
138 192
1416 384
1532 768
1665 536
17131 072
18262 144
19524 288
201 048 576
212 097 152
224 194 304
238 388 608
2416 777 216
2533 554 432
2667 108 864
27134 217 728
28268 435 456
29536 870 912
301 073 741 824
312 147 483 648
324 294 967 296
338 589 934 592
3417 179 869 184
3534 359 738 368
3668 719 476 736
37137 438 953 472
38274 877 906 944
39549 755 813 888
401 099 511 627 776
412 199 023 255 552
424 398 046 511 104
438 796 093 022 208
4417 592 186 044 416
4535 184 372 088 832
4670 368 744 177 664
47140 737 488 355 328
48281 474 976 710 656
49562 949 953 421 312
501 125 899 906 842 624
512 251 799 813 685 248
524 503 599 627 370 496
539 007 199 254 740 992
5418 014 398 509 481 984
5536 028 797 018 963 968
5672 057 594 037 927 936
57144 115 188 075 855 872
58288 230 376 151 711 744
59576 460 752 303 423 488
601 152 921 504 606 846 976
612 305 843 009 213 693 952
624 611 686 018 427 387 904

Резервное копирование в Vertica

В Vertica мы храним аналитические данные, которые в принципе можно не бэкапировать, т.к. объем данных - не велик, и можно перезалить в любой момент. Но это касается лишь новых данных, есть часть данных из старых источников: Oracle, Excel и текстовых документов, которые не желательно перезаливать. Лучше восстановить данные из бэкапа, чем собирать данные из старых источников, которые, возможно, уже и не существуют или с ними что-то случилось.

Снимать бэкап нужно под пользователем dbadmin:

su dbadmin

Создайте директорию, в которую будет записана резервная копия:

mkdir /home/dbadmin/backups20190207

В Vertica создание резервной копии и восстановление из нее осуществуляется с помощью утилиты vbr (думаю, это означает Vertica Backup and Restore). Для vbr нужно создать конфигурационный файл, который используется как для создания копии, так и для восстановления из нее.

Примеры конфигурационных файлов можно посмотреть в каталоге:

/opt/vertica/share/vbr/example_configs

Создайте новый конфигурационный файл /opt/vertica/share/vbr/example_configs/backup_restore_your_database.ini со следующим содержимым:

[Mapping]
v_your_database_node0001 = []:/home/dbadmin/backups20190207
#v_your_database_node0002 = []:/home/dbadmin/backups20190207

[Misc]
tempDir = /tmp

[Database]
dbName = YOUR_DATABASE
dbUser = dbadmin
dbPassword = YOUR_PASSWORD
#dbPromptForPassword = True

Нужно перечислить все узлы вашего кластера: v_your_database_node0001, v_your_database_node0002 и т.д. В нашем случае кластера нет, поэтому одна нода.

В dbName, dbUser и dbPassword укажите параметры подключения к вашей базе данных.

Пароль можно не прописывать, а каждый раз запрашивать, расскомментировав строку: dbPromptForPassword = True.

Возможные проблемы

В данной инструкции явно прописана учетка и пароль, т.к. без этого возникала проблема подключения:
Unable to log vbr invocations. Error SQL command "select log_vbr_invocations('Full Backup Task', '/tmp/vbr_2020-01-04-115520.log', 'SQL6F52TLDAFPCZ9YZEOH83P9YYKL9HW', 'Fail');" failed: vsql: FATAL 3781:  Invalid username or password
Error: SQL command "select name,catalogpath from v_internal.vs_nodes;" failed: vsql: FATAL 3781:  Invalid username or password
Backup FAILED.

Инициализация директории

Перед непосредственным созданием бэкапа нужно проинициализировать указанную в конфиге директорию:

/opt/vertica/bin/vbr -t init -c /opt/vertica/share/vbr/example_configs/backup_restore_your_database.ini

Создание резервной копии

После инициализации директории выполните команду:
/opt/vertica/bin/vbr -t backup -c /opt/vertica/share/vbr/example_configs/backup_restore_your_database.ini

Восстановление из резервной копии

Для восстановления из резервной копии выполните команду:
/opt/vertica/bin/vbr -t restore -c /opt/vertica/share/vbr/example_configs/backup_restore_your_database.ini

Профилирование CPU с помощью Flame Graph

Flame Graph позволяет визуально увидеть чем были заняты процессоры в течении определенного периода.

Снять Flame Graph можно по классической инструкции: https://github.com/BrendanGregg/FlameGraph, что требует некоторых манипуляций.

Но можно пойти более легким путем, используя async-profiler:

  1. Скачиваем стабильный релиз в виде архива
  2. Распаковываем архив
  3. Выполняем команду:
    ./profiler.sh -d 30 -f /tmp/flamegraph.svg <PID>

    Где <PID> - это идентификатор Java-процесса.

    -d 30 - продолжительность профилирования, в секундах.

    /tmp/flamegraph.svg - файл сохранения Flame Graph.

Flame Graph можно прекрасно просматрировать в браузере без использования каких-либо дополнительных средств.

В этом можно убедиться на следующем примере Flame Graph (можно кликать на области): Your browser does not support SVG

Поиск искомого Java-процесса можно осуществляется через утилиту jps.

Скрипт, автоматизирующий поиск и снятие Flame Graph:

PID=`jps | grep YOUR_APP_NAME | awk '{print $1}'`
echo PID = $PID
FG=/tmp/flamegraph$PID.svg
echo FG = $FG
~/soft/async-profiler-1.6-macos-x64/profiler.sh -d 30 -f $FG $PID
p.s. Этому блогу исполнилось 7 лет!

Алгоритм Ахо-Корасик на Java

Пример реализации алгоритма Ахо-Корасика на Java.

При реализации использовался следующий материал:

  1. https://e-maxx.ru/algo/aho_corasick
  2. https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE-%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA

Данный алгоритм был опробован на задаче: https://www.hackerrank.com/challenges/determining-dna-health/problem

Пример использования:

List<AhoCorasick.Entry> entryList = new ArrayList<>();
 
List<String> list = Arrays.asList("b", "c", "aa", "d", "b");
 
for (String s : list) {
    AhoCorasick.Entry entry = new AhoCorasick.Entry();
    entry.setValue(s);
    entryList.add(entry);
}
 
 
AhoCorasick ahoCorasick = new AhoCorasick(entryList, 26);
 
ahoCorasick.solve("caaab");

Сама реализация алгоритма:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
/**
 * Реализация алгоритма Ахо-Корасика
 */
public class AhoCorasick {
 
    private List<Entry> entryList;
    private int alphabetSize;
    private List<Vertex> vertexList;
    private int vertexCount;
 
    public AhoCorasick(List<Entry> entryList, int alphabetSize) {
        this.entryList = entryList;
        this.alphabetSize = alphabetSize;
    }
 
    // Строка набора
    public static class Entry {
        private String value;
 
        public String getValue() {
            return value;
        }
 
        public void setValue(String value) {
            this.value = value;
        }
 
        @Override
        public String toString() {
            return "Entry{" +
                    "value='" + value + '\'' +
                    '}';
        }
    }
 
    // Вершина бора (состояние конечного детерминированного автомата)
    public static class Vertex {
        private int next[];         // массив сыновей
        private boolean isLeaf;     // терминальная вершина
        private int parent;         // родительская вершина
        private int charIndexFromParent;// символ перехода от родителя
        private int suffixLink;     // суффиксная ссылка
        private int go[];           // массив переходов, используемый для вычисления суффиксных ссылок
 
        public Vertex(int alphabetSize) {
            this.next = newIntArray(alphabetSize);
            this.go = newIntArray(alphabetSize);
            this.parent = -1;
            this.suffixLink = -1;
        }
 
        private int[] newIntArray(int size) {
            int[] ints = new int[size];
            Arrays.fill(ints, -1);
            return ints;
        }
 
        @Override
        public String toString() {
            return "Vertex{" +
                    "next=" + Arrays.toString(next) +
                    ", go=" + Arrays.toString(go) +
                    ", isLeaf=" + isLeaf +
                    '}';
        }
    }
 
    public List<Entry> getEntryList() {
        return entryList;
    }
 
    // добавить строку в набор
    public boolean addEntry(Entry entry) {
        return entryList.add(entry);
    }
 
    // поиск всех строк из заданного набора в тексте
    public void solve(String text) {
        vertexList = new ArrayList<>();
        vertexList.add(new Vertex(alphabetSize));
        vertexList.add(new Vertex(alphabetSize));
        vertexCount = 1;
 
        for (Entry entry : entryList) {
            addToTrie(entry);
        }
 
        int v = 0;
        for (char ch : text.toCharArray()) {
            v = go(v, charToIndex(ch));
            Vertex vertex = vertexList.get(v);
            if(vertex.isLeaf) { // посещение терминальной вершине - это нахождение строки из заданного набора
                System.out.println(v + " " + vertex);
            }
        }
 
    }
 
    // добавить в бор
    private void addToTrie(Entry entry) {
        int v = 0;
        for (char ch : entry.value.toCharArray()) {
            int sym = charToIndex(ch);
            if(vertexList.get(v).next[sym] == -1) {
                Vertex vertex = vertexList.get(vertexCount);
                vertex.suffixLink = -1;
                vertex.parent = v;
                vertex.charIndexFromParent = sym;
 
                vertexList.add(new Vertex(alphabetSize));
                vertexList.get(v).next[sym] = vertexCount++;
            }
            v = vertexList.get(v).next[sym];
        }
        vertexList.get(v).isLeaf = true;
    }
 
    private int charToIndex(char ch) {
        return ch - 'a';
    }
 
    // обычный переход
    private int go(int v, int sym) {
        Vertex vertex = vertexList.get(v);
        if(vertex.go[sym] == -1) {
            if(vertex.next[sym] != -1) {
                vertex.go[sym] = vertex.next[sym];
            } else {
                vertex.go[sym] = v == 0 ? 0 : go(goBySuffixLink(v), sym);
            }
        }
        return vertex.go[sym];
    }
 
    // переход по суффиксной ссылке (к вершине, в которой оканчивается наидлиннейший собственный суффикс строки)
    private int goBySuffixLink(int v) {
        Vertex vertex = vertexList.get(v);
        if(vertex.suffixLink == -1) {
            if(v == 0 || vertex.parent == 0) {
                vertex.suffixLink = 0;
            } else {
                vertex.suffixLink = go(goBySuffixLink(vertex.parent), vertex.charIndexFromParent);
            }
        }
        return vertex.suffixLink;
    }
 
}

Sublime gcc docker

При разработке на C++ может возникнуть ситуация, когда ваша ОС не подходит.

Например, в моем случае у меня MacBook, но нужно использовать epoll, который не подджерживается в Mac OS.

Можно выйти из ситуации следующим путем, если вы пишите и билдите код в редакторе Sublime.

В Sublime выберите Tools > Build System > New Build System...

Откроется шаблон, замените его содержимое на следующее:

{
 "shell_cmd": "docker run --rm -v \"${file_path}\":/usr/src/myapp -w /usr/src/myapp gcc:4.9 g++ -std=c++11 \"${file_name}\" -o \"${file_base_name}\" && docker run --rm -v \"${file_path}\":/usr/src/myapp -w /usr/src/myapp gcc:4.9 ./\"${file_base_name}\"",
 "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
 "working_dir": "${file_path}",
 "selector": "source.c++",
 "variants":
 [
  {
   "name": "Run",
   "shell_cmd": "docker run --rm -v \"${file_path}\":/usr/src/myapp -w /usr/src/myapp gcc:4.9 g++ -std=c++11 \"${file_name}\" -o \"${file_base_name}\" && \"${file_base_name}\" && docker run --rm -v \"${file_path}\":/usr/src/myapp -w /usr/src/myapp gcc:4.9 ./\"${file_base_name}\""
  }
 ]
}

Сохраните файл, будет предложено наименование файла в формате YOUR_NAME.sublime-build

Чтобы воспользовать новым вариантом сборки, выберите Tools -> Build System -> YOUR_NAME.

Сделайте Build.

Если нужно отредактировать файл YOUR_NAME.sublime-build, установите плагин PackageResourceViewer.

Понимание OpenID Connect (OIDC)

Превосходная статья по пониманию OpenID Connect: https://habr.com/ru/post/422765/

В данной статье в пункте 6 указано, что хранение токенов (access_token и refresh_token) в браузере не очень секьюрно, лучше это делать на уровне бэкенда. Но это требует сессию, к которой будут крепится токены.

Сессия хранится в Cookie, Cookie передаются во всех запросах к одному хосту, даже с других сайтов, поэтому нужно защить запросы еще CSRF-токеном.

Также сессии нужно передавать между бэкендами для балансировки нагрузки.

Сессии хранятся в памяти, поэтому большое кол-во пользователей может исчерпать память.

Понимание Kerberos

Отличное видео-объяснение протокола Kerberos

https://www.youtube.com/watch?v=_44CHD3Vx-0 (Продолжительность: 6 минут)

Цербер (Кербер) - трехголовый пес.

Примечательно, что протокол построен на симметричной криптографии с использованием трех различных закрытых ключей.

TAG:

Отличный курс по Active Directory

Всегда казалось, что Active Directory - это что-то супер сложное для понимания.

Но найдя понятный и простой курс по AD, уже так не думаю 🙂

Курс состоит всего из 4 модулей общей продолжительностью чуть больше часа.

Название модуля Ссылка на youtube Продолжительность
Введение в Active Directory https://www.youtube.com/watch?v=fojHlsyGQqA 20 мин.
Создание первого домена https://www.youtube.com/watch?v=rJJKYe5VECk 10 мин.
Подразделения, группы, учетные записи пользователей https://www.youtube.com/watch?v=ZTnLg9CzZZQ 27 мин.
Включение компьютера в домен https://www.youtube.com/watch?v=JMfe3_OmnRA 10 мин.

Исследование Keycloak

Если у вас уже установлен keycloak и настроен realm, то запросить open-id конфигурацию данного realm можно командой:

curl http://{KEYCLOAK_HOST}:{KEYCLOAK_PORT}/auth/realms/{YOUR_REALM}/.well-known/openid-configuration | jq '.'

Результат будет представлен в виде JSON. Чтобы удобочитаемо отформатировать JSON, можно воспользоваться утилитой jq (https://stedolan.github.io/jq/), которую нужно будет дополнительно установить.

Небольшое описание полученных данных

issuer - базовый адрес realm'а;

authorization_endpoint - конечная точка авторизации; Получить публичный ключ для проверки подписи токена:

curl http://{KEYCLOAK_HOST}:{KEYCLOAK_PORT}/auth/realms/{YOUR_REALM}/protocol/openid-connect/certs | jq '.'

TAG: ,

Highload табличка

Часто возникает необходимость оценки скорости работы системы или какой-нибудь утилитки. Приходится брать калькулятор делить/умножать на секунды, минуты, часы и дни. Расчеты получаются, конечно же, приблизительные. Поэтому хотелось бы иметь примерную табличку, чтобы реже пользоваться калькулятором.
Кол-во операций,
транзакций и т.д.
За 24 часа
(86 400 секунд)
За 10 часов
(36 000 секунд)
За 10 часов
(600 минут)
1 000 000 11.6 в секунду 27.8 в секунду 1 666.7 в минуту
10 000 000 115.7 в секунду 277.8 в секунду 16 666.7 в минуту
100 000 000 1 157.4 в секунду 2 777.8 в секунду 166 666.7 в минуту
300 000 000 3 472.2 в секунду 8 333.3 в секунду 500 000.0 в минуту
500 000 000 5 787.0 в секунду 13 888.9 в секунду 833 333.3 в минуту
700 000 000 8 101.9 в секунду 19 444.4 в секунду 1 166 666.7 в минуту
1 000 000 000 11 574.1 в секунду 27 777.8 в секунду 1 666 666.7 в минуту