В этой статье я (опять) хочу рассмотреть алгоритм поиска решения задачи полного покрытия, теперь уже с нормальной реализацией через структуру "танцующих ссылок". Заодно на этом примере хочу показать, где и зачем указание типов в Julia критично для производительности, а где оно не обязательно.

Задача точного покрытия множества $$ некоторым набором $$ его подмножеств состоит в выборе попарно непересекающихся подмножеств $$, в сумме составляющих $$. Например, если множество $$ — это геометрическая фигура, а $$ — это кусочки "паркета", то задача точного покрытия спрашивает, можно ли замостить фигуру таким паркетом.

Как пример можно рассмотреть складывание геометрических фигур из фигурок пентамино

Некоторые решения для прямоугольников (из Википедии):

Для конечного множества $$ и конечного числа подмножеств $$ задача может быть представлена как матрица логических значений (0/1), где в $$-й строке единицы соответствуют элементам множества $$, содержащимся в $$. Задача тогда состоит в выборе таких строк, чтобы в получившейся матрице в каждом столбце была ровно одна единица.

Пример матрицы:

Строки 1, 4 и 5 составляют точное покрытие.

Задача является NP-полной, поэтому единственным гарантированным способом решения является поиск с возвратом. Особенности задачи позволяют построить специальную структуру данных для такого поиска, популяризованную Дональдом Кнутом, — систему "танцующих ссылок".

"Алгоритм X"

Алгоритм поиска точного покрытия, описанный Кнутом в работе "Танцующие ссылки", представляет собой простой поиск с возвратом. Псевдокод этой процедуры выглядит следующим образом:

Вход:     `matr` - матрица из непокрытых столбцов     `solution` - массив, содержащий строки решения     `k` - указатель на текущий индекс массива  Процедура `Algorithm_x`     Если `matr` не содержит непокрытых столбцов:         Вернуть (или вывести) `solution`.     Иначе выбрать столбец `c`.     Покрыть столбец `c`.     Для всех строк `r`, пересекающихся со стобцом `c`:         Записать `solution[k] = r`.         Для всех столбцов `j`, пересекающихся с `r`:             Покрыть столбец `j`.         Вызвать `Algorithm_x(matr, solution, k+1)`.         Если алгоритм нашёл решение, вернуть его.         (бэктрекинг)         Для всех столбцов `j`, пересекающихся с `r`:             Восстановить столбец `j`.     Восстановить столбец `c`.     Возврат из процедуры.

"Покрытие" столбца c означает вычёркивание из матрицы его и всех строк, с которыми он пересекается (поскольку если столбец покрыт какой-либо строкой r, то другими строками его покрыть уже нельзя). Восстановление означает вставку удалённого столбца и строк обратно.

Танцующие ссылки

Поскольку алгоритм поиска с возвратом требует удаления некоторых ветвей решения и возвращения их на место, неплохо бы использовать структуру данных, с которой это можно сделать быстро. Кнут в качестве такой структуры данных предлагает "танцующие ссылки", основанные на представлении матрицы в виде тороидально связанного списка.

Идея танцующих ссылок основана на том, что удаление узла node из двусвязного списка делается очень просто: если элемент имеет ссылку prev на предыдущий и next на следующий элемент, то удаление — это

node.next.prev = node.prev node.prev.next = node.next

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

node.next.prev = node node.prev.next = node

Если из списка удалено несколько элементов, то вставка их в порядке, обратном порядку удаления, восстанавливает исходное состояние списка.

Для булевой матрицы можно представлять единичные элементы узлами списка, связанного по двум направлениям. Для приведённой выше матрицы список будет выглядеть так (из статьи Кнута):

h — входной узел для структуры, в узлах A — G хранятся ссылки на соседей и число строк, пересекающих столбец, в остальных узлах хранятся только ссылки на ненулевые элементы в той же строке и в том же столбце. Также внутренние узлы хранят ссылки на заголовки столбцов, на рисунке не показанные.

Процедура покрытия столбца в этой структуре требует следующих действий:

• Отцепить заголовок столбца от правого и левого соседей.
• Проходя по ссылкам вниз, для каждой пересекаемой строки $r$ отцепить от соседей сверху и снизу все ссылки в той же строке, кроме собственно $r$.

Восстановление выполняется в обратном порядке — сначала восстановить для каждой строки (проходя вверх по ссылкам от заголовка столбца) соседей по вертикали, затем восстановить заголовок столбца в ряду. Чтобы структура корректно восстанавливалась, покрытие и восстановление столбцов должны вызываться в строго обратном порядке.

Рассмотрим реализацию этой структуры и алгоритма поиска точного покрытия на языке Julia.

Узел списка содержит ссылки на узлы слева, справа, сверху и снизу и на головной узел столбца, к которому он относится:

mutable struct LinkNode     left     right     above     below     col     # конструктор с привязкой к столбцу     function LinkNode(col)         self = new()         self.above = self.below = self.right = self.left = self         self.col = col         return self     end     # конструктор с пустым столбцом (для входного узла)     function LinkNode()         self = new()         self.above = self.below = self.right = self.left = self         return self     end end

Головной узел столбца содержит ссылки на соседние элементы, размер и идентификатор.

mutable struct LinkColumn     links     size     id     function LinkColumn(id)         self = new()         links = LinkNode(self)         self.links = links         self.size = 0         self.id = id         return self     end end

Сама матрица представляется входным узлом, от которого можно перейти к списку матриц.

struct LinkMatrix     root_node     #=     конструктор создает список столбцов из итерируемого объекта,     содержащего идентификаторы столбцов     =#     function LinkMatrix(ids)         root = LinkNode()         self = new(root)         prev = root         for id in ids             col = LinkColumn(id)             collinks = col.links             collinks.left = prev             collinks.right = root             prev.right = collinks             root.left = collinks             prev = collinks         end         return self     end end

Алгоритм поиска точного покрытия записывается в соответствии с псевдокодом:

function algorithm_x!(matr, solution=FullRow[])     if iscovered(matr)         return solution     end     col = choose_col(matr)     cover!(col)     for node in col         push!(solution, FullRow(node))         for j in RestRow(node)             cover!(j.col)         end         if !isnothing(algorithm_x!(matr, solution))             return solution         end         node = pop!(solution).node         # важен порядок восстановления         for j in Iterators.reverse(RestRow(node))             uncover!(j.col)         end     end     uncover!(col)     return end

Вспомогательные структуры данных и процедуры:

# проверка, покрыта ли матрица полностью iscovered(matr) = matr.root === matr.root.right  # итератор по столбцам матрицы function Base.iterate(matr::LinkMatrix, next = matr.root.right)     next === matr.root && return     return (next.col, next.right) end  #= структура данных, представляющая все узлы в строке, кроме заданного =# struct RestRow     node end  # итерация по всем узлам в строке, кроме заданного function Base.iterate(row::RestRow, next = row.node.right)     next === row.node && return     return (next, next.right) end  # итерация справа налево function Base.iterate(row::Iterators.Reverse{<:RestRow}, next = row.itr.node.left)     next === row.itr.node && return     return (next, next.left) end  # строка, содержащая заданный узел struct FullRow     node end  # итерация по строке, начиная с заданного узла function Base.iterate(row::FullRow)     node = row.node     return (node, node.right) end  function Base.iterate(row::FullRow, next)     next === row.node && return     return (next, next.right) end

Выбор столбца, который пытаемся накрыть следующим, делается на основе "S-эвристики" — выбирается столбец, для которого меньше всего возможных накрывающих его строк:

function choose_col(matr)     bestcol = matr.root.right.col     s = bestcol.size     for col in matr         l = col.size         l < 2 && return col # если возможен только 1 вариант или ни одного, выбираем сразу         if l < s             s, bestcol = l, col         end     end     return bestcol end

Процедура cover!(col) "отцепляет" столбец от правого и левого соседей (что важно — оставляя связи по вертикали без изменений, чтобы можно было потом восстановить), затем проходится по каждой строке и отцепляет узлы от соседей сверху и снизу (кроме тех ссылок, которые по цепочке ведут к столбцу col). Когда узел отцепляется от соседей по вертикали, размер столбца, где он находился, уменьшаем на единицу.

function cover!(col)     detach_rl!(col.links)     for node in col         for elt in RestRow(node)             detach_ab!(elt)         end     end end  # отсоединяет от соседей слева и справа function detach_rl!(node)     node.right.left = node.left     node.left.right = node.right     return node end  # отсоединяет от соседей сверху и снизу function detach_ab!(node)     node.above.below = node.below     node.below.above = node.above     node.col.size -= 1     return node end

Процедура восстановления, uncover!(col) возвращает всё назад:

function uncover!(col)     # важен порядок прохода по столбцу     for node in Iterators.reverse(col)         # порядок прохода по строке не важен         for elt in RestRow(node)             restore_ab!(elt)         end     end     restore_rl!(col.links) end  function restore_rl!(node)     node.right.left = node     node.left.right = node     return node end  function restore_ab!(node)     node.above.below = node     node.below.above = node     node.col.size += 1     return node end

Всё, что осталось для удобной жизни — это добавить процедуру добавления строки, которая накрывает столбцы с заданными идентификаторами:

#= matr - матрица, куда вставляется строка col_ids - коллекция с идентификаторами =# function insert_row!(matr, col_ids)     isempty(col_ids) && return     num_inserted = 0     first_in_row = nothing     prevnode = nothing     # идём по столбцам, если id подходит - создаём новый узел, прицепляем к строке     for col in matr         if col.id in col_ids             newnode = LinkNode(col)             if isnothing(first_in_row)                 first_in_row = newnode             end             first_in_row.left = newnode             newnode.right = first_in_row             if !isnothing(prevnode)                 prevnode.right = newnode                 newnode.left = prevnode             end             prevnode = newnode             num_inserted += 1             # если все идентификаторы найдены - подцепляем строку к матрице             if num_inserted == length(col_ids)                 for node in FullRow(first_in_row)                     col = node.col                     collinks = col.links                     lastnode = collinks.above                     col.size += 1                     node.above = lastnode                     node.below = collinks                     lastnode.below = node                     collinks.above = node                 end                 return first_in_row             end         end     end     #=     сюда попадаем, если не нашли все идентификаторы     в этом случае строка содержит идентификатор, которого нет в столбцах     игнорируем эту строку и выходим     =#     return end

Скорость работы

Проверим алгоритм на решении судоку и замерим скорость.

Судоку преобразуется в следующую задачу полного покрытия:

• (:row, row, num) — в строке row есть число num
• (:col, col, num) — в столбце col есть число num
• (:block, col, num) — в столбце block есть число num
• (самое хитрое условие) (:fill, row, col) — на пересечении столбца col и строки row есть число

Наличие уже заполненных клеток приводит к тому, что часть столбцов уже "накрыта", и их в матрицу задачи вносить не нужно (или можно внести и сразу же "закрыть").

function sudoku2xcover(fill)     ncells = size(fill)     side = ncells[1]     side == ncells[2] || throw(ArgumentError("Invalid matrix size $ncells"))     blockside = isqrt(side)     blockside^2 == side || throw(ArgumentError("Side $side is not a full square"))     row_constr = trues(ncells)     col_constr = trues(ncells)     blk_constr = trues(ncells)     for col in 1:side, row in 1:side         num = fill[row,col]         if num in 1:side             block = col - (col - 1) % blockside + (row - 1) ÷ blockside             row_constr[row, num] = false             col_constr[col, num] = false             blk_constr[block, num] = false         end     end     constr = collect((:row, row, num) for row in 1:side, num in 1:side if row_constr[row,num])     append!(constr, (:col, col, num) for col in 1:side, num in 1:side if col_constr[col,num])     append!(constr, (:block, block, num) for block in 1:side, num in 1:side if blk_constr[block,num])     append!(constr, (:fill, row, col) for row in 1:side, col in 1:side if !(fill[row,col] in 1:side))     matr = LinkMatrix(constr)     for row in 1:side, col in 1:side, num in 1:side         block = col - (col - 1) % blockside + (row - 1) ÷ blockside         if row_constr[row,num] && col_constr[col,num] && blk_constr[block,num] && !(fill[row,col] in 1:side)             col_ids = (:row, row, num), (:col, col, num), (:block, block, num), (:fill, row, col)             insert_row!(matr, col_ids)         end     end     return matr end  function sol2matr(soln, fieldsize)     ans = zeros(Int, fieldsize)     for node in soln         indval = row2indval(node)         ans[indval.ind] = indval.val     end     return ans end  function row2indval(dlrow)     row, col, n = 0,0,0     for j in dlrow         constr = j.col.id         if constr[1] === :fill             _, row, col = constr         else             _, _, n = constr         end         all(>(0), (row, col, n)) && break     end     return (ind = CartesianIndex(row, col), val = n) end  function sudoku(fill)     cover = sudoku2xcover(fill)     soln = sol2matr(algorithm_x!(cover), size(fill))     soln .+= fill     return soln end

Посмотрим на время решения "самого сложного судоку" под названием "Золотой самородок"

const testpuzzle = [         0 0 0 0 0 0 0 3 9;         0 0 0 0 1 0 0 0 5;         0 0 3 0 0 5 8 0 0;         0 0 8 0 0 9 0 0 6;         0 7 0 0 2 0 0 0 0;         1 0 0 4 0 0 0 0 0;         0 0 9 0 0 8 0 5 0;         0 2 0 0 0 0 6 0 0;         4 0 0 7 0 0 0 0 0     ] julia> using BenchmarkTools  julia> @btime sudoku(testpuzzle);   33.012 ms (115869 allocations: 3.40 MiB)

(ответ не показан, чтобы не спойлить)
Решение требует порядка 0.1 секунды. Быстрее, чем вручную, но как-то не впечатляет. Попробуем "переписать всё в сишном стиле", чтобы ублажить компилятор и ускорить выполнение.

Ускоряем работу, проставив типы

Главная проблема описанной реализации с точки зрения производительности — структуры данных имеют поля с абстрактным типом (когда тип данных поля не указан, он ставится как Any). Поэтому при обращении к полям постоянно требуется боксинг и анбоксинг данных.

Конкретизируем типы полей данных, по возможности. И сразу сталкиваемся с весёлой проблемой. Определение

# так не выйдет mutable struct LinkNode     left::LinkNode     right::LinkNode     above::LinkNode     below::LinkNode     col::LinkColumn end  mutable struct LinkColumn     links::LinkNode     size::Int     id::Any end

не проходит, поскольку LinkColumn — неизвестный тип на этапе определения типа LinkNode. По той же самой причине не проходит определение сперва LinkColumn, а потом LinkNode.

Решением в данном случае будут параметрические типы. Поставим тип поля col в структуре LinkNode как параметр, а поле links в LinkColumn будет иметь тип LinkNode{LinkColumn}. Чтобы избавиться от абстрактного типа для id, параметризуем и LinkColumn типом этого поля.

mutable struct LinkNode{C}     left::LinkNode{C}     right::LinkNode{C}     above::LinkNode{C}     below::LinkNode{C}     col::C     function LinkNode(col::C) where {C}         self = new{C}()         self.above = self.below = self.right = self.left = self         self.col = col         return self     end     function LinkNode{C}() where {C}         self = new{C}()         self.above = self.below = self.right = self.left = self         return self     end end  mutable struct LinkColumn{T}     links::LinkNode{LinkColumn{T}}     size::Int     id::T     function LinkColumn{T}(id) where {T}         self = new{T}()         links = LinkNode(self)         self.links = links         self.size = 0         self.id = id         return self     end end  LinkColumn(id::T) where {T} = LinkColumn{T}(id)

С LinkMatrix проделываем ту же процедуру.

struct LinkMatrix{T}     root::LinkNode{LinkColumn{T}}     function LinkMatrix{T}(ids) where {T}         root = LinkNode{LinkColumn{T}}()         self = new{T}(root)         prev = root         for id in ids             col = LinkColumn{T}(id)             collinks = col.links             collinks.left = prev             collinks.right = root             prev.right = collinks             root.left = collinks             prev = collinks         end         return self     end end  LinkMatrix(ids) = LinkMatrix{eltype(ids)}(ids)

Нужно не забыть указать типы полей во вспомогательных структурах:

struct RestRow{L<:LinkNode}     node::L end  struct FullRow{L<:LinkNode}     node::L end

Проверяем:

julia> @btime sudoku(testpuzzle);   777.426 μs (6803 allocations: 209.91 KiB)

Время выполнения улучшилось с 33 мс до 0.8 мс при том, что типы переменных не указаны нигде, кроме полей структур, конструкторов и перегруженных методов для iterate, где аннотации типов необходимы для правильной диспетчеризации.

Однако стоит дописать аннотацию типа ещё в одном месте — для аргументов процедуры algorithm_x!, где в качестве аргумента по умолчанию указан контейнер с абстрактным типом элементов. Благодаря множественной диспетчеризации можно напрямую перегрузить метод, вызываемый с одним аргументом.

function algorithm_x!(matr::LinkMatrix{T}) where {T}     RowType = FullRow{LinkNode{LinkColumn{T}}}     solution=RowType[]     return algorithm_x!(matr, solution) end

Проверяем:

julia> @btime sudoku(testpuzzle);   547.812 μs (3603 allocations: 129.16 KiB)

Итого получили ускорение больше чем в полсотни раз. При этом каких-то нечеловеческих усилий для расстановки типов прилагать вовсе не приходится, достаточно это сделать только в ключевых местах, в первую очередь — в полях структур (где, в большинстве случаев, о предполагаемых типах полей так и так нужно задумываться). Сильно в этом помогают параметрические типы — если заранее неизвестно, какого типа может быть поле структуры, чаще всего его стоит не оставлять без типа (т.е. с типом Any), а делать его тип параметром:

struct SomeStruct{T}     data::T end

Так поле data может быть чем угодно, но не придётся жертвовать скоростью выполнения.

Заключение

Дизайн языка Julia позволяет использовать его не только как "язык для математиков". Разумная система типов и активное использование аннотаций типов при JIT компиляции позволяют эффективно реализовывать любые классические Computer Science алгоритмы. Особо заморачиваться с типизацией для получения быстрого кода при этом не нужно, что показано примером реализации алгоритма DLX Кнута. Но выставление аннотаций типов в стратегически выверенных точках вполне может дать прирост скорости на 1-2 порядка, поэтому тем, кто начинает программировать на Julia (и тем, кто пробует язык после других языков с динамической типизацией), стоит потратить некоторое время на понимание концепций абстрактных и конкретных типов, параметрических типов, боксинга и устойчивости типов.

1 июня, в Международный день защиты детей, Цифровое деловое пространство совместно с детскими писателями и актерами столичных театров, в том числе Московского Театра на Перовской, «Содружества актеров Таганки», театра «Наш дом» и Московского театра мюзикла, запустили проект «ТехноСказки». Это онлайн-портал, на котором представлены технологические видеопереосмысления в стихах и в прозе всем известных произведений.

Ниже текст моей сказки о Царевне Лягушке и возможности человечества соединить цифровые достижения и заботу о живом, в надежде, что мы сможем сохранить биологическое разнообразие для наших детей.

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

Жил да был Царь, а царство у него было не простое — инновационное! С министрами он общался в мессенджере, жена Царица вела его социальные сети, не менее одного поста в день, и даже, по секрету скажу, был у него уютный чатик с другими царями, так и назывался: «Цари».

Детей у него было трое, да все сыновья. С детства дал он им лучшее онлайн образование, а в свободное время объезжали они царство: старший на самокате электрическом, средний на гироскутере, а младший, Иван, освоил квадрокоптер с камерой и вообще из палат не выходил, снимал на видео и монтировал ролики про красоту земли своей с высоты птичьего полета.

Так бы и жили не тужили, но вышло в стране у них одно приложение, которое идеальную пару каждому подбирало. Сыновья как раз были холостые, так как знакомиться не успевали — все больше курсы новые онлайн проходили.
Приложение собрало много отзывов положительных: что ни отзыв, то история любви романтической. Механика была простая. Открываешь приложение, а там лук нарисован, да не порей, и не репчатый (тот уже занят был в другом приложении), а лук, из которого охотились раньше, когда доставку «Кухня на селе» еще не придумали. Виртуальную тетиву натягиваешь и в дополненной реальности улетает стрела к твоей суженной. Ну не чудо ли? Вот он, прогресс технологий долгожданный, в древних сказаниях описанный.

Пустил стрелу старший брат — упала она на боярский двор, прямо против девичьего терема. Пустил средний брат — полетела стрела к купцу на двор и остановилась у красного крыльца, а на там крыльце стояла душа-девица, дочь купеческая. Пустил младший брат — попала стрела в грязное болото. Пришел он туда со своим квадрокоптером по геолокации, а на месте сидит лягушка амфибия. Смотрит Иван в приложение, а так там и написано: знакомьтесь, мол, ваша суженая, лягушка-квакушка (по латыни Пелофилакс Ридибундус). Он аж сам чуть не квакнул.

Ну, думает Царевич, приехали, взломали меня хакеры юродивые, нечего было по сайтам заморским шастать. Интернет суверенный и державный наш, самый безопасный. Нашли они мою уязвимость и запустили ко мне вирус, придется операционку переустанавливать.

Сам он, конечно, человек был с юмором, благо целых 98 баллов из 100 набрал в онлайн-курсе про чувство юмора. И говорит Царевич амфибии:

— Дорогая, Ридибундус Пелофилакс, встреча наша судьбоносная и рад я невероятнейшее.

В ответ молчание, да только телефон завибрировал, а там сообщение с незнакомого номера.

«Благодарю вас, сударь, покорнейше. Сама не верила отзывам, но теперь очевидно — алгоритм работает, наконец-то польза от интеллекта искусственного».

Он тут и вправду квакнул.

Лягушка ему в ответ квакает. Присмотрелся Царевич, а в лапке у нее портативный телефон японский новой модели, самый маленький на рынке.
И следом сообщение с того же номера — с сердечком!

Иван хоть и был воспитан в традиции, но и вера в технологии была в нем непоколебима. Посадил он лягушку на квадрокоптер и отправился домой к Царю-батюшке.

Вот поженились Царевичи: старший — на боярыне, средний — на купеческой дочери, а Иван-царевич — на лягуше-квакуше. Тут призывает их Царь и приказывает: «Хочу, чтобы жены ваши испекли мне к завтрему по мягкому хлебу белому».

Воротился Иван-царевич в свои палаты невесел, ниже плеч буйну голову повесил, квадракоптер хоть и заряженный, но летать на нем совсем не хочется.
Приходит ему сообщение:

«Ква-ква, Иван-царевич! Почто так кручинен стал? — спрашивает его лягуша. — Подписчики что ли у тебя на канале больше не набираются?»

Смотрит он на свою амфибию — она знать ему послала сообщение и опять с подружками из Южной Америки чатится, дюже быстро переключается между сообщениями. Тут же ей диагноз поставил: клиповое мышление!

Пишет ей: «Как мне не кручиниться? Государь мой батюшка приказал тебе к завтрему изготовить мягкий белый хлеб». Тут же пришел ему ответ: «Не тужи, ненаглядный Иван! Ложись-ка спать-почивать; утро вечера мудренее!»

Так уложила лягуша Царевича спать да сбросила с себя лягушечью кожу — и обернулась душой-девицей, Василисой Премудрою; вышла на красное крыльцо и закричала громким голосом:

«Ах друзья мои, микробы!
На закваске быстро чтобы
Хлеб полезный испекли
С минералами Земли!
Колосочки и тростинки,
И травинки и росинки,
Булку хлеба напитайте,
И Царю здоровья дайте!»

Наутро проснулся Иван-царевич, а у Ридибундус хлеб давно готов — и такой славный, что ни вздумать, ни взгадать, только в сказке сказать! Он сразу фотку сделал и в социальные сети вложил.

Царь кушает, да всю пользу ферментации чувствует, восполнил нехватку волокон пищевых, довольный сидит.

И тут же отдал приказ трём своим сыновьям: «Чтобы жены ваши соткали мне за единую ночь по ковру, да узор чтобы был уникальный, под защиту авторских прав не подпадал, а то потом тролли патентные замучают».

Вновь Иван-царевич невесел, ниже плеч буйну голову повесил. А лягушка сидит с австралийскими родственниками по видео день рождения чей-то отмечает. И опять — лишь лапкой махнула, а у него сообщение

«Ква-ква, Иван-царевич! Почто так кручинен стал? Может, забыл подписку отменить до окончания льготного периода?» — «Как мне не кручиниться? Государь мой батюшка приказал за единую ночь соткать ковер с узором оригинальным, ничьи права не нарушающим». — «Не тужи, Царевич! Ложись-ка спать-почивать; утро вечера мудренее!»

Уложила его спать, а сама сбросила лягушечью кожу — и обернулась душой-девицей, Василисою Премудрою, вышла на красное крыльцо
и закричала громким голосом:

«Ах друзья мои, микробы!
Из волокон срочно чтобы
мне узоров наплели!
Всех народов, всей земли!
Пусть плетутся паутинки,
Из заморских стран картинки.
Ягодки-грибочки!
Травушки-цветочки!»

Как сказано, так и сделано. Наутро проснулся Иван-царевич, а у квакуши ковер давно готов — и такой чудный, что ни вздумать, ни взгадать, разве в сказке сказать. И поскольку все традиции всех концов света сведены в одно, претензий явно не предвидится, всегда можно сказать: «Эклетика вдохновленная народными мотивами».

Благодарствовал Царь за тот ковер Ивану-царевичу, повесил его вместо плазменного экрана, смотрит на фрактальный узор и дух радуется, дыхание становится глубже и видятся ему в узорах растительных диковинные животные, рыбы невиданные … а потом засыпает он, тут все понятно — возраст.

Но как проснулся, отдал новый приказ: чтобы все три Царевича явились к нему на смотр вместе с женами.

Опять воротился Иван-царевич невесел, ниже плеч буйну голову повесил.
Лягушка его явно в каком-то онлайн марафоне участвует, на него даже не смотрит, но меж тем приходит сообщение:

«Ква-ква! Иван-царевич! Почто кручинишься? Неужели модель квадрокоптера твоего устарела, хотя новою была полгода назад еще?»

Пишет он ей: «Как мне не кручиниться? Государь мой батюшка велел, чтобы я с тобой на смотр приходил; а как я тебя в люди покажу?» Отвечает она ему: «Не тужи, Царевич! Ступай один к Царю в гости, а я вслед за тобой буду, как услышишь стук да гром — скажи: это моя лягушонка в коробчонке едет».

Вот старшие братья явились на смотр с своими женами, разодетыми, разубранными; стоят да с Ивана-царевича смеются: «Что ж ты, брат, без жены пришёл? Пущай бы на квадрокоптере прилетела! И где ты этакую красавицу выискал? Чай, все болота исходил?»

Вдруг поднялся великий стук да гром — весь дворец затрясся; гости крепко напугались, повскакивали с мест своих и не знают, что им делать. А Иван-царевич и говорит: «Не бойтесь, господа! Это моя лягушонка в коробчонке приехала».

Подлетела к царскому крыльцу коляска с реактивной тягою, в шесть двигателей, раньше такие максимум по два ставили умельцы, что с ранцами за спиной летают. И вышла оттуда Василиса Премудрая — такая красавица, что ни вздумать, ни взгадать, только в сказке сказать!

Взяла Ивана-царевича за руку и повела за столы дубовые, за скатерти бранные. Стали гости есть-пить, веселиться. Василиса Премудрая испила из стакана да последки себе за левый рукав вылила; закусила блюдом веганским да остатки за правый рукав спрятала. Жены старших Царевичей увидали ее хитрости, давай и себе то ж делать.

После, как пошла Василиса Премудрая танцевать с Иваном-царевичем, махнула левой рукой — сделалось озеро, махнула правой — и поплыли по воде цветы невиданные; Царь и гости диву дались — сразу поняли «Органическое».

А старшие невестки пошли танцевать, махнули левыми руками — гостей забрызгали, махнули правыми — Царю компост прямо в глаз! Царь рассердился и прогнал их с позором изучать переработку отходов.

Тем временем Иван-царевич улучил минуточку, побежал домой, нашёл лягушачью кожу и спалил ее на большом огне.

Приезжает Василиса Премудрая, хватилась — нет лягушачьей
кожи, приуныла, запечалилась и говорит Царевичу:

«Ох, Иван-царевич! Что же ты наделал? Без кожи волшебной связь моя с друзьями-микробами нарушилась и быть здесь больше не могу я! Ищи меня за тридевять земель в тридесятом Царстве — у Кощея Бессмертного, поклонника антиэйджинга».

Обернулась белой лебедью и улетела в окно. Иван-царевич горько заплакал, проверил обновления в социальных сетях, оставил все гаджеты и пошел куда глаза глядят. Первое время было, конечно, непривычно, все казалось, будто телефон в кармане вибрирует.

Шел он близко ли, далеко ли, долго ли, коротко ли — попадается ему навстречу старый старичок, с виду похож на сморчок, вместо носа почти пяточок.

«Здравствуй, — говорит, — добрый молодец! Чего ищешь, куда путь держишь?»

Царевич рассказал ему своё несчастье.

Старик начал заговор приговаривать: «Эх, Иван-царевич! Зачем ты лягушачью кожу спалил? Не ты её надел, не тебе и снимать было! Василиса Премудрая хитрей, мудреней своего отца уродилась. Он всё бессмертия фармпрепаратами достичь пытался, а она поняла, что в теле сотни метров слизистой и триллионы микробов живут, да с ними подружилась! Он за то осерчал на неё и велел ей три года квакушею быть. Вот тебе клубок; он, конечно, не навигатор автомобильный, но принцип тот же: куда покатится — ступай за ним смело, привыкай к устройствам аналоговым, заодно тебе цифровой детокс будет».

Перед тем как клубок на землю бросить, старик заговорил его:

«Ах трава-мурава!
Мать-Земля всегда права!
Пусть клубочек приведет,
Пусть дорогу он найдет!»

Иван-царевич поблагодарил старика и пошёл за клубочком.

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

Говорит им Иван: «Дорогой Медведь! По латински Ursus! Дорогой Заяц! По латински Lepus! Мы с вами — дети эволюции, от одного общего предка, жившего 150 миллионов лет назад, происходим. Все мы — млекопитающие, многие гены у нас дюже сходные!»

Восприняли медведь с зайцем короткий урок биологии, прониклись теорией эволюции, смотрят — и лапы у них на Ивановы похожи, и соски на теле есть.

«Доказательно рассуждаешь, Иван! Верно мы имели предков общих, авось еще свидимся — пригодимся тебе».

Идёт Иван дальше, глядь, а над ним летит селезень. Царевич призадумался: онлайн курс по эволюции-то он проходил, да в те дни интернет был не шибко хороший и вещание шло с помехами. Ну, думает, скажу как помнится:

«Дорогой Селезень! По латински Драке, или Анас! Мы с тобой — оба дети эволюции и от одного общего предка, жившего 300 миллионов лет назад, происходим, звали предков наших Amniatis! Появилась у них амниотическая жидкость и способность яйца с детенышами на земле откладывать или в себе носить! Оба мы — позвоночные да и многие гены у нас дюже сходные!»

Слушает селезень, вспоминает свое название латинское. Особенно Драке ему понравилось — так как на дракона похожее. Видит общие черты: позвоночник, ребра. Радостно отвечает: «Доказательно рассуждаешь, Иван! Верно мы имели предков общих, авось еще свидимся — пригожусь тебе».

Пошел Иван дальше, видит улитка ползет.

Царевич явно в онлайне этого не помнит материала, но зато бумажная у него была энциклопедия, из нее он и цитирует:

«Дорогая улитка виноградная! По латински Хеликс Поматия! Мы с тобой — дети эволюции и от одного общего предка, жившего 600 миллионов лет назад, происходим! Посмотри на асимметрию своего тела и вращение спирали своей ракушки, есть у нас общий ген с тобой, за формирование этой асимметрии в зародыше отвечающий!»

Смотрит улитка на Ивана: одна нога и впрямь другой короче, глаза немного разного размера, ухо оттопырено. Видимо, и правда были общие предки.

Говорит ему: «Доказательно рассуждаешь, Иван! Верно мы имели предков общих, авось еще свидимся — пригожусь тебе, сама ползу я в гости к моллюску-родственнику на море, обещал он мне дать в прокат ракушку зубчатую».

Долго ли, коротко ли — прикатился клубочек к избушке, что стоит на куриных лапках да кругом повёртывается.

Говорит Иван-царевич: «Избушка, избушка! Стань по-старому, как мать поставила, — ко мне передом, а к морю задом».

Избушка повернулась к морю задом, к нему передом. Царевич взошёл в неё и видит, старушка с длинными волосами на шпагате сидит, дышит громко и глубоко, потом подпрыгивает — ноги в пол, руки в пол, а таз к верху. Похоже на собаку, что морду вниз опустила.

«Гой еси, добрый молодец! Зачем ко мне пожаловал?» — спрашивает у него старушка, не разгибаясь.

«Ах ты, Бабушка Яга! Не признал тебя, думал ты в сказках только бываешь! Доброго тебе здравия!» — отвечает Иван

«Да какая я тебе Баба-Яга! Я личный тренер Кощея бессмертного по йоге! Баба Йог! А Баба у нас в Индии уважительное обращение. Ты на волосы мои не смотри, они за ночь вырастают у меня, так как метаболизм очень резвый!
Прознал Кащей про пользу йоги для антиэйджинга, да и спрятал меня в заброшенном парке развлечений этническом, все равно сюда никто не ходит. Я и поселился в избушке. Не отпускает он домой меня!»

Царевич пожалел Йога и рассказал ему, что ищет свою жену Василису Премудрую.

«А, знаю! — сказал баба-йог. — Она теперь у Кощея Бессмертного; трудно ее достать, нелегко с Кощеем сладить. Каждый день делает он себе инъекции от старения, шприц с препаратами прячет как следует! Так что смерть его на конце иглы, та игла в яйце, то яйцо в утке, та утка в зайце, тот заяц в сундуке, а сундук стоит на высоком дубу, и то дерево Кощей как свой глаз бережёт».

Указал Йог, в каком месте растет этот дуб. Иван-царевич пришел туда и не знает, что ему делать, как сундук достать? Вдруг откуда ни взялся — прибежал медведь, Урсус, и выворотил дерево с корнем. Сундук упал и разбился вдребезги, а из него выбежал заяц да во всю прыть наутек как пустился. Смотрит Иван, а за ним уж другой заяц, Лепус, гонится. Нагнал, ухватил и в клочки разорвал! Вылетела было из зайца утка и поднялась высоко-высоко, летит. А за ней селезень, Драко, бросился, как ударит её — утка тотчас яйцо выронила, и упало то яйцо в море.

Иван-царевич, видя беду неминучую, залился слезами. Вдруг из моря выползает улитка с ракушкою зубчатой, одолжила в лизинг у моллюска родственника, а на зубчике у нее яйцо. Взял Иван то яйцо, разбил, достал иглу и отломил кончик: сколько ни бился Кощей, сколько ни метался во все стороны, а пришлось ему помереть!

Иван-царевич пошел в дом Кощея, взял Василису Премудрую и воротился домой. После того они жили вместе и долго и счастливо, блог об их жизни совместной и продуктах ферментированных собрал три миллиона подписчиков.

Сказка — ложь, да в ней намек! Добрым молодцам урок!

Автор выражает благодарность
Редактору Елене Шкарубо
Иллюстратору Алле Тяхт (ссылка на работы)

Список иллюстрация
1 — Лягушка со стрелой — автор Алла Тяхт
2 — Электронная микроскопия микробов в волокнах хлебной закваски Belitz, Grosch and Schieberle (2009).
3 — Слева на право сверху вниз: 
1) Африканский мотив 
2) Микробы вблизи слизистой кишечника
3) Микробы зубной эмали
4) Русский народный узор, источник ornamika.com
 5) Микробы на волокнах высушенной слизистой
6) Узор Шапибо, народов амазонки
4 — Дерево Эволюции, источник сайт National Geographic

Дано: Аккаунты в Google, VK, Telegram.
Задача: Создать хранилище музыкальных групп с возможностью удобного пополнения.
Инструменты: Google Apps Script (GAS), VK API, Tampermonkey, Telegram Bot API.

Создание Google Таблицы

Создаём новую Google Таблицу.
Делаем закреплённый заголовок (потом все циклы перебора ячеек из-за этого будут начинаться не с 0, а с 1).
В принципе наш шаблон готов.
Единственное, я не сделал привязку к колонкам через имена (не хотел использовать циклы), так что на протяжении всего скрипта буду обращаться к жёстко зашитому номеру колонки.

Жмём «Инструменты — Редактор скриптов».

Создаём 2 скрипта: Код.gs и Бот.gs.

access_token = '1111111111' // VK token ss = SpreadsheetApp.getActiveSpreadsheet() // Таблица sheet = ss.getSheets()[getNumSheet('Группы')] // Лист data = sheet.getDataRange().getValues() // Все ячейки numRows = sheet.getLastRow()+1 // Последняя строка faveTag = 'муз.группы' // Тег закладок в ВК  // Принимаем входящие get запросы function doGet(e) { try {     var link = e.parameters['link']     /*       A - Название       B - English       C - Ссылка       D - Город       E - Жанр       F - Описание       G - Примечание     */     var n = searchExists(link)     if (n != false) return ContentService.createTextOutput('Группа '+n+' уже есть!')     // Запрос в API VK https://vk.com/dev/groups.getById     var html = UrlFetchApp.fetch('https://api.vk.com/method/groups.getById.json?group_id='+link+'&fields=city,description&access_token='+access_token+'&v=5.107')     // Парсим в json первый элемент response     var json = JSON.parse(html).response[0]     addInTableFromArray(json, link)     sort()     return ContentService.createTextOutput('Добавлено')   } catch (e) {      return ContentService.createTextOutput('Ошибка из гуглотаблиц doGet! '+e)   } }  // Поиск стиля/жанра группы из описания по регулярке function searchGenre(txt) {   var t = txt.match(/(?:(?:стил[ь|я|ю|ем|е]|genre|жанр[а|у|ом|е]?)[\s:-]+){1}([a-zа-я\/-]+)/i)   if(txt != '' && t) return t[1] }  // Поиск русских букв в названии function isRus(txt) {   return txt.search(/[^A-Za-z0-9\/.:_]+/i) }  // Сортировка function sort(){   // Диапазон сортируемых ячеек от левой верхней до правой нижней   var tableRange = "A2:G"+numRows   var editedCell = sheet.getActiveCell()   var range = sheet.getRange(tableRange)   // Порядок сортировки по номеру столбца. Начинается не с 0, а с 1   range.sort([{      column : 4,     ascending: true   },{     column: 1,     ascending: true   },{     column: 2,     ascending: true   }]) }  // Поиск существующих групп function searchExists(t) {   for (var i = 1; i < data.length; i++) {     if (t == data[i][2] || 'club'+t == data[i][2]){       return data[i][0]+data[i][1]     }   }   return false }  // Подтягивание данных массово если их нет function addInfo(isBot = false) {   var arr = []   var j = 0   var part = 1000 // Кол-во символов, на которое будет делиться блок текста. Из-за ограничений в адресной строке и UrlFetchApp.fetch   arr[j] = new Array()   for (var i = 1; i < data.length; i++) {     var txt = data[i][2].replace('https://vk.com/','').replace('vk.com/','').replace('^club','')     if (txt != '' && data[i][0] == '' && data[i][1] == '' && data[i][3] == '' && data[i][4] == '' && data[i][5] == '' && data[i][6] == ''){       arr[j].push(txt)       if (arr[j].toString().length > part){         j++         arr[j] = new Array()       }     }   }   if (arr[0].length == 0){     if (isBot) return false     else{       SpreadsheetApp.getUi().alert('Нет групп, которые нужно дополнить')       return false     }   }   // Цикл по ссылкам   for (var t = 0; t < Math.ceil(arr.toString().length/part); t++) {     var html = UrlFetchApp.fetch('https://api.vk.com/method/groups.getById.json?group_ids='+arr[t].toString()+'&fields=city,description&access_token='+access_token+'&v=5.107')     var json = JSON.parse(html).response     if(json){       for (var i = 0; i < json.length; i++) {         var id = json[i].id         var link = json[i].screen_name         var name = json[i].name         var description = (json[i].description)?json[i].description:''         var city = (json[i].city)?json[i].city.title:''         var rus = (isRus(name) != -1)?"A":"B"             // Скрипт можно попробовать заменить на двумерный массив к arr         for (var j = 1; j < data.length; j++) {           var nameCell = data[j][2].replace('https://vk.com/','').replace('vk.com/','').replace('^club','')           if (nameCell == link || nameCell == id){             var num = j+1             break           }         }         sheet.getRange(rus+num).setValue(name.replace('=',''))         sheet.getRange("C"+num).setValue('=HYPERLINK("https://vk.com/'+link+'";"'+link+'")')         sheet.getRange("D"+num).setValue(city)         sheet.getRange("E"+num).setValue(searchGenre(description))         sheet.getRange("F"+num).setValue(description)       }     }   }   sort()   return true }  // Втянуть группы из закладок ВК function getVkFave(isBot = false) {   var idTag   var getTags = UrlFetchApp.fetch('https://api.vk.com/method/fave.getTags.json?access_token='+access_token+'&v=5.107')   var res = JSON.parse(getTags).response   var iTag = res.items   for (var i = 0; i < iTag.length; i++) {     if (iTag[i].name == faveTag) idTag = iTag[i].id   }      // Предупреждение   if (!isBot){     var ui = SpreadsheetApp.getUi()     var resp = ui.alert('После втягивания закладок с тегом "'+faveTag+'" они будут удалены из ВК. Продолжаем?', ui.ButtonSet.YES_NO)   }   var inside = function (){     var getPages = UrlFetchApp.fetch('https://api.vk.com/method/fave.getPages.json?tag_id='+idTag+'&fields=city,description&access_token='+access_token+'&v=5.107')     var iPage = JSON.parse(getPages).response.items     // Цикл по каждой закладке. Добавление в таблицу, удаление с ВК     for (var j = 0; j < iPage.length; j++) {       var gr = iPage[j].group       addInTableFromArray(gr)       numRows++         UrlFetchApp.fetch('https://api.vk.com/method/fave.removePage?group_id='+gr.id+'&access_token='+access_token+'&v=5.107')         Utilities.sleep(1000) // костыль     }     sort()   }   if (isBot) { // Костыль, потому что бот стопарится на ui     inside()   }else if(resp == ui.Button.YES) {     inside()   } }  // Добавление строки в таблицу function addInTableFromArray(arr, linkIn) {   if (linkIn){     var link = linkIn   }else{     var link = arr.screen_name     if (searchExists(link) != false) return false   }   var name = arr.name // Название   var description = (arr.description)?arr.description:'' //Описание   var city = (arr.city)?arr.city.title:'' // Город   // Если в тексте нет русских букв, значит пишем название в колонку "English"   var rus = (isRus(name) != -1)?"A":"B"   // Добавление строки в таблицу   sheet.getRange(rus+numRows).setValue(name.replace('=',''))   sheet.getRange("C"+numRows).setValue('=HYPERLINK("https://vk.com/'+link+'";"'+link+'")')   sheet.getRange("D"+numRows).setValue(city)   sheet.getRange("E"+numRows).setValue(searchGenre(description))   sheet.getRange("F"+numRows).setValue(description) } // Актуализировать ссылки. Единоразово. function checkActualLink(){   for (var i = 1; i < data.length; i++) {     try {       var num = i+1       UrlFetchApp.fetch("https://vk.com/"+data[i][2])       sheet.getRange('C'+num).setBackgroundColor('')     }catch(err) {       var num = i+1       sheet.getRange('C'+num).setBackgroundColor('red')     }   } } // Статус URL в строке. Запуск добавлением кода в ячейку function getStatusUrl(url){    var options = {      'muteHttpExceptions': true,      'followRedirects': false    }    var response = UrlFetchApp.fetch(url.trim(), options)    return response.getResponseCode() } //Поиск номера листа по имени function getNumSheet(nameList){   var s = SpreadsheetApp.getActiveSpreadsheet().getSheetByName(nameList)   if (s != null) {     return s.getIndex()-1   }else{     return false   } } //Удалить спецсимволы function escapeHtml(text) {   return text       .replace(/&/g, "")       .replace(/</g, "")       .replace(/>/g, ""); } // Меню function onOpen() {   SpreadsheetApp.getUi()   .createMenu('Меню специальное')   .addItem('Сортировка', 'sort')   .addItem('Втянуть закладки из ВК', 'getVkFave')   .addItem('Дозаполнить пустые', 'addInfo')   .addToUi(); }  // Краткий вызов логирования function ll(t){   return Logger.log(t) } 

var botApi = 'https://api.telegram.org/bot1123123:AAA/' // Токен Telegram бота  /* Команды:  /start - Начало работы бота  /sort - Сортировка  /getvkfave - Втянуть закладки из ВК   /addinfo - Дозаполнить пустые  /getall - Получить все группы */ function doPost(e){   var inp = JSON.parse(e.postData.contents)   // Логи   var sheet2 = ss.getSheets()[getNumSheet('Логи')]   sheet2.getRange('A1').setValue(inp)      var inpTxt = inp.message.text   var chatId = inp.message.chat.id      var link = inpTxt.replace('https://vk.com/','').replace('vk.com/','').replace('^club','')   // Команды бота   // start   if (inpTxt == '/start' || inpTxt == 'В начало'){     sendText(chatId, 'Бот заносит группы из ВК в Google таблицу.\n'+                     '/start - Начало работы бота\n'+                     '/sort - Сортировка\n'+                     '/getvkfave - Втянуть закладки из ВК\n'+                     '/addinfo - Дозаполнить пустые\n'+                     '/getall - Получить все группы')     return true   }   // sort   if (inpTxt == '/sort' || inpTxt == 'Сортировка'){     sort()     sendText(chatId, 'Отсортировано')     return true   }   // getvkfave   if (inpTxt == '/getvkfave' || inpTxt == 'Втянуть закладки из ВК'){     getVkFave(true)     sendText(chatId, 'Втянуто')     return true   }   // addinfo   if (inpTxt == '/addinfo' || inpTxt == 'Дозаполнить пустые'){     if (addInfo(true)) sendText(chatId, 'Дозаполнено')     else sendText(chatId, 'Нет групп, которые нужно дополнить')     return true   }   // getall   if (inpTxt == '/getall' || inpTxt == 'Получить все группы'){     var arr = [[],[],[],[],[],[],[],[],[],[],['В начало']] // TODO доделать     var repeat = ''     var n = 0     var j = 0     for (var i = 1; i < data.length; i++) {       if (j == 4){ // Количество на одной строке         n++         j = 0       }       if (repeat != data[i][3]){         arr[n][j] = data[i][3]         if (data[i][3] == '') arr[n][j] = '---'         j++       }       repeat = data[i][3]     }     var key = JSON.stringify({keyboard:                                arr,                               resize_keyboard:true,                               one_time_keyboard:true                             });     sendText(chatId, 'Выберите город', key)     return true   }      // Город   if (isRus(link) != -1) {     var name = (inpTxt == '---')?'Не заполнен':inpTxt     for (var j = 1; j < data.length; j++) {       if (data[j][3] == inpTxt || inpTxt == '---') {         var str = 'Город '+name+'\n\n'         for (var i = 1; i < data.length; i++) {           if ((data[j][3] == data[i][3]) || (data[i][3] == '' && inpTxt == '---')) {             if (str.length >= 4000) { // Ограничение на кол-во символов в сообщении Telegram бота               sendText(chatId, str)               str = ''             }             str = str + '<a href="https://vk.com/' + data[i][2] + '">' + escapeHtml(data[i][0] + data[i][1]) + '</a> \n'           }         }         if (str != '') sendText(chatId, str)         return true       }     }     sendText(chatId, inpTxt + ' - это не муз.группа и не команда бота')     return true   }   // Проверка на валидность   if (getStatusUrl('https://vk.com/'+link) != 200 && getStatusUrl('https://vk.com/club'+link) != 200){     sendText(chatId, inpTxt+' - битая ссылка')     return true   }      var name = searchExists(link)   if (name != false){     sendText(chatId, 'Группа '+name+' уже есть')     return true   }else{     var html = UrlFetchApp.fetch('https://api.vk.com/method/groups.getById.json?group_id='+link+'&fields=city,description&access_token='+access_token+'&v=5.103')     var json = JSON.parse(html).response[0]     addInTableFromArray(json, link)     sort()     sendText(chatId, 'Группа '+json.name+' добавлена')     return true   } } //Отправить сообшение боту function sendText(chatId, text, key = ''){   var payload = {     'method': 'sendMessage',     'chat_id': String(chatId),     'text': text,     'parse_mode': 'HTML',     'reply_markup': key,     'disable_web_page_preview': true,     'one_time_keyboard':true   }        var data = {     "method": "post",     "payload": payload   }   // для дебага комментируем UrlFetchApp.fetch и вставляем ll(text)   UrlFetchApp.fetch(botApi, data) } 

Подробнее разберём ниже.

Жмём "Опубликовать — Развернуть, как веб приложение".

Теперь у нас есть ссылка вида script.google.com/macros/s/AAA/exec, подставив к которой параметр «link», мы сможем занести группу ВК в Google Таблицу.

Юзерскрипты в браузере

Первый и основной способ занесения данных!

Открываем браузер Google Chrome или Mozilla Firefox и ставим плагин юзерскриптов Tampermonkey.
Ссылки для Хрома, для Мозиллы

Изначально пользовался Greasemonkey, но пришлось перейти на Tampermonkey из-за кроссбраузерности.
У кого возникнут вопросы, почему параметры юзерскрипта начинаются с префикса GM_, а не TM_ — идея не моя, идём в документацию.

Вставляем скрипт vkGroupToGS, нажав на первую вкладку с плюсиком.

// ==UserScript== // @name         vkGroupToGS // @namespace    https://vk.com/* // @version      0.1 // @author       You // @match        https://vk.com/* // @grant        GM_xmlhttpRequest // ==/UserScript==     var url_first = 'https://script.google.com/macros/s/AAA/exec'     var url_short = document.location.href.replace("https://vk.com/", "")     var d = document.createElement('div')     var head = document.querySelector('.left_menu_nav_wrap')     d.setAttribute('id', 'send_group')     d.style.display = 'inline-block'     d.style.position = 'relative'     d.style.fontSize = '50pt'     d.style.cursor = 'pointer'     d.innerHTML = '+'     head.parentNode.appendChild(d)     d.onclick = function() {     setTimeout(function() {         GM_xmlhttpRequest({             method: 'GET',             url: url_first + '?link=' + url_short,             headers: {                 'Accept': 'application/atom+xml,application/xml,text/xml'             },             onload: function(x) {                 console.log(x.responseText)                 if (/Ошибка/.test(x.responseText)) document.querySelector('#send_group').style.color = 'red'                 else document.querySelector('#send_group').style.color = 'green'             }         })     }, 0) }; 

«Файл — Сохранить».

Как видим, наш скрипт рисует плюсик (на что хватило фантазии) в левом блоке left_menu_nav_wrap.

По нажатию на плюсик выполняется GM_xmlhttpRequest из vkGroupToGS в наш скрипт Код.gs по ссылке Google Таблицы, приложенной выше (url_first).

Tampermonkey запросит у нас связать эти 2 скрипта правами, жмём либо "Всегда разрешать" либо "Всегда разрешать домену" для "script.google.com". Повторить при надобности для "script.googleusercontent.com".

Как только запрос успешно улетит, придёт колбэк из GM_xmlhttpRequest и окрасит нашу кнопку в зелёный цвет ✚ при удачном добавлении либо в красный ✚ если вернулась ошибка.

Плюс Tampermonkey — облачное хранение скриптов в Google (раньше не было) при наличии их плодовитости и своего воображения.

Вернёмся к Google Таблице.
Перед тем, как начать разбирать наш Код.gs я хочу поделиться документацией для разработки в ВК — vk.com/dev

Токен ВК

Получение ключа доступа
Выполнение запросов к API ВКонтакте

Пока научился только одним способом добывать токен — через самописные приложения.

Заходим сюда.
Платформа — "Standalone-приложение".
После создания всё, что нам надо — это ID приложения (ныне семизначный), пусть будет 1234567.
Но нам нужен токен.
Очень хорошо про токен написано в Знакомстве с API ВКонтакте.
Если не хотим читать, просто открываем ссылку, вставляя в client_id свой ID приложения.

Нас редиректит на страничку с надписью:

Пожалуйста, не копируйте данные из адресной строки для сторонних сайтов. Таким образом Вы можете потерять доступ к Вашему аккаунту.

И это верно, будьте очень аккуратны с токеном!

Токен копируем из адресной строки после access_token.

Сразу поделюсь, что с этим токеном можно запросы вида vk.com/dev/groups.search?params%5Bq%5D=%D0%BC%D1%83%D0%B7%D1%8B%D0%BA%D0%B0&params%5Btype%5D=page&params%5Bcountry_id%5D=1&params%5Bcity_id%5D=1&params%5Bfuture%5D=0&params%5Bmarket%5D=0&params%5Boffset%5D=0&params%5Bcount%5D=10&params%5Bv%5D=5.107

можно спокойно преобразовывать в ссылки api.vk.com/method/groups.search?q=%D0%BC%D1%83%D0%B7%D1%8B%D0%BA%D0%B0&type=page&country_id=1&city_id=1&future=0&market=0&offset=0&count=10&access_token=1111111111111&v=5.107 и получать информацию в любом приложении.

Я открыл маленький ящик пандоры, возможно это и не новость, но таким способом можно получить много полезного из ВК, автоматизировать множество процессов и сделать уйму удобняшек.

Конечно с определёнными ограничениями, допустим не больше 999 сущностей в ответе или 20 запросов в секунду и т.п.

Также кому-нибудь будет интересно поиграться с хранимками — в нашем приложении вкладка "Хранимые процедуры".
Там есть свои правила вытягивания информации, очень удобно для последовательных запросов, чтоб не делать множество циклов у себя в коде.

Следим за версиями!
С их изменениями может меняться функциональность методов. Ныне прикладываю примеры для версии 5.107.

Итак, токен у нас есть, переходим к…
Код.gs

doGet(e) — Принимаем входящие get запросы от бота, ВК и просто с браузера.
Входные параметры парсятся, как e.parameters[‘ВХОДНОЙ_ПАРАМЕТР’]
Прилетает ссылка, проверяем, есть ли в таблице. Если нет, запрашиваем подробную информацию через groups.getById, парсим, добавляем.
! Внимание! Скрипт простой, так что будет проглатывать все прилетающие ссылки, так что будьте аккуратны даже введя 123 при проверке скрипта.
searchGenre — умный поиск стиля/жанра группы, из-за которого я и поставил метку «регулярные выражения» в статье.
Возможны улучшения.
Пока работает только на поиск последующей цепочки слов через слеш или дефис после слов "стиль или жанр или genre".
isRus — простая регулярка, исключающая русские буквы.
sort — сортировка. Поставил по умолчанию — 1. город, 2. название.
searchExists — простой поиск существующих групп через цикл.
addInfo — сделал скрипт для себя, оставил здесь, как бонус. Нужен если у вас есть список ссылок, но нет по ним данных.
Вставляем список в колонку «Ссылка», жмём "Дозаполнить пустые" в главном меню и остальные колонки дозаполняются из ВК.
Из-за ограничений на количество символов в UrlFetchApp.fetch и в количестве ссылок, помещаемый в адресную строку пришлось сделать цикл по 1000 символов.
getVkFave — ещё один бонус, возникший в голове во время написания статьи и которым я сам стал пользоваться.
Суть — заходим с телефона в приложение ВК, натыкаемся на группу, которую хотим сохранить, сохраняем её в закладках с заранее добавленной меткой "муз.группы" (глобальная переменная faveTag).
Как они накопятся, заходим в нашу Google Таблицу, вызываем меню, жмём "Втянуть закладки из ВК".
Скрипт с токеном лезет в api.vk.com/method/fave.getTags, парсит, добавляет в таблицу, предварительно предупредив об удалении из ВК (тут аккуратней с тестированием, всё удаляется подчистую с закладок с этим тегом).
getStatusUrl и checkActualLink — эксперимент, вылившийся в 2 скрипта.
Суть — проверять валидность и доступ до ссылок.
Потому что за годы накопления музыкальных групп я столкнулся с тем, что паблики удаляют либо переименовывают.
Кто будет пользоваться моей удобняшкой, советую некое TODO, которое будет не просто удалять невалидные ссылки, но и проверять через groups.search по названию наличие в ВК.
checkActualLink — единоразово проверяет валидность, окрашивая в красный невалидные.

• Минус — низкая скорость.
• Плюс — выполнять можно, когда захочется.

getStatusUrl — вызывается в ячейке через скрипт

=getStatusUrl(CONCAT("https://vk.com/";C2))

Основу взял отсюда.

• Минус — запускается для всех ячеек при каждом открытии страницы.
• Плюс — отрабатывает параллельно для всех ячеек, то есть скорость в разы выше, чем у checkActualLink.

Далее идут удобняшки для гуглоскриптов:
addInTableFromArray — Добавление строки в таблицу. Либо с цикла либо единоразово.
getNumSheet — Поиск номера листа по имени. Честно, не нашёл в интернете способа проще, чем этот. Нужен из-за смещения номеров листков при добавлении новых. Основу взял отсюда.
escapeHtml — Удалить спецсимволы
ll — для себя сделал Logger.log кратким, сокращает время, советую.
onOpen — Всем знакомая функция для отрисовки меню в Google Таблице.

Итак, наш Код.gs ловит ссылки с ВК через Tampermonkey и добавляет группы в Google Таблицу.

ВКЛЮЧАЕМ ЛЕНЬ

• Мы сидим за компьютером.
• Мы сидим в телефоне.

С компьютера мы научились добавлять группы через "плюсик" в ВК и через закладки.
Через телефон только через закладки в приложении ВК.

Разберём ещё два варианта внесения групп.

USI

Юзерскрипты в мобильном браузере.
Кому-то он покажется старомодным и ненужным, но найдутся те люди, которые вынесут плюсы из него.
Поискав в интернете нашёл пока только такой плагин.
Работает только в Firefox (тестировал только в android).
Огромный плюс — можно использовать скрипт Tampermonkey.
Из-за отличий вёрстки между vk.com и m.vk.com, а также из-за открывания окна по умолчанию в m.vk.com я не стал рисовать плюсик, а сделал простой скрипт VK_event_to_list_mvk, срабатывающий при открытии окна (гореть мне в аду за setTimeout, знаю).

// ==UserScript== // @name         VK_event_to_list_mvk // @namespace    https://m.vk.com/* // @match        https://m.vk.com/* // @grant    GM_xmlhttpRequest // ==/UserScript== setTimeout(function() {     var url_first = 'https://script.google.com/macros/s/111/exec';     var url_short = document.location.href.replace("https://m.vk.com/", "");     GM_xmlhttpRequest({         method: 'GET',         url: url_first + '?link=' + url_short,         headers: {             'Accept': 'application/atom+xml,application/xml,text/xml'         },         onload: function(x) {             alert(x.responseText);         }     }); }, 2000); 

Telegram Бот

Создаём бота по инструкции.
Нам нужен токен, пусть он будет 123123.
Создаём скрипт Бот.gs, вставляем в переменную botApi наш 123123, обрамляя кавычками и ссылкой api.telegram.org.
Далее надо сцепить нашего бота с Google Таблицей. Посмотреть, как это сделать через WebHook можно в предыдущей статье.

Что будет делать наш бот?
Разложим по командам:

• /start — Начало работы бота
• /sort — Сортировка
• /getvkfave — Втянуть закладки из ВК
• /addinfo — Дозаполнить пустые
• /getall — Получить все группы

Видим, что у нас есть начало работы бота, туда мы вставим просто tutorial с описательной частью на ваше усмотрение.
Три команды из главного меню на всякий случай.
И очередной бонус — /getall, о нём ниже.

Команды для удобного вызова (в строке ввода сообщения написать слеш) можно добавить в том же @BotFather через /setcommands.
Формат — строки через тире:

start - Вернуться в начало sort - Сортировка getvkfave - Втянуть закладки из ВК addinfo - Дозаполнить пустые getall - Получить все группы

Бот.gs
doPost — принимает входящие сообщения от бота.
Естественно, как пытливый программист, я сразу начал использовать логи. Возможно есть способы проще, но я просто создал новый лист, назвал его «Логи» и ловлю в первую ячейку входящие запросы.
Поэтому после того, как мы распарсили входящее сообщение через JSON.parse(e.postData.contents), сразу пишем в логи.
Далее определяем, какая из команд нам пришла.
Если не команда, проверяем на валидность, то есть существует ли группа в ВК.
sendText — отправляет сообщения боту (по умолчанию parse_mode = HTML), документация.

/getall — разберём отдельно.
Пусть вас не пугает моё решение из

[[],[],[],[],[],[],[],[],[],[],['В начало']]

Сделано для заполнения строчек городами, пока ограничимся 8-10 строчками по 4 города (переменная j = 4).
Если музыкальная группа без города, вставляем —.
Просто выбираем город и ловим русские буквы в Бот.gs.
Выводим список ссылок, ничего более.

Помним, что доступ к документации и тестированию бота через адресную строку через Hotspot Shield Free VPN Proxy — Unlimited VPN (для Google Chrome).

Вот мы и изучили три способа внесения в нашу таблицу:

• Юзерскрипты в браузере
• Юзерскрипты в мобильном браузере (USI)
• Telegram Бот

Что нужно знать и помнить?

Префикс club в ссылках ВК
В группах ВК есть 2 типа хранения идентификатора.

1. Название на английском с допустимыми подчёркиваниями и дефисами.
2. ID

Причём выкладываться могут и так и так.
Проверить просто.
Если есть группа, допустим vk.com/4soulsband, подставляем 4soulsband в group_ids в vk.com/dev/groups.getById, выводится перечень параметров, один из которых ID. И если мы перед ним поставим club, вуаля, попадаем на ту же страницу vk.com/club68130764.

Ограничение на хранение групп в ВК до 5000
Кажется смешным, но мне не хватило.

Моя боль с обновлением страницы ВК
Каюсь, пока не смог победить отлов перехода между страницами в ВК для сброса состояния плюсика в Tampermonkey. TODO

Использование Google Таблиц, как БД

• Плюс — доступность
• Минус — когда копится больше 5000 строк, работа с "БД" замедляется. Так что для серьёзных проектов лучше использовать нормальные СУБД.

Определение города группы
Адрес группы в ВК может быть тут vk.com/dev/groups.getAddresses, соответственно кто захочет улучшить поиск города для группы, может использовать его.

Итог

У нас есть:

1. Google таблица для сбора данных, с которой мы научились работать.
2. Знания по VK API. То есть вы уже в курсе, что мы можем не ограничиваться музыкальными группами.
3. Telegram Бот с БД, которую не нужно разворачивать и настраивать.

Моя цель не кичиться очередной созданной игрушкой, моя цель показать новичкам (и не только) огромный пласт открытых API`шек, которые помогут облегчить жизнь в той или иной степени, перенестись с железной земли в «облака», так сказать.
Данный функционал готов, как и открыт для улучшений.
Удачи в разработке и постижении новых знаний.

Документация

Google Apps Script — Spreadsheet Service
Telegram Bot API
VK API
Учимся писать userscript’ы
Userscripts. Углубляемся
Мониторинг сайта с помощью Google Docs
Баловство. Пишем Telegram бота на Google script
[Примеры, Google Apps Script] Разработка дополнений/скриптов для Google Таблиц (spreadsheets)
How to use google spreadsheets to check for broken links

Хотя Kubernetes не обладает этими функциями прямо «из коробки», он предоставляет API, которым можно воспользоваться для решения подобных задач. Инструменты для автоматизированного Blue/Green развертывания и масштабирования кластера Kubernetes были разработаны в рамках проекта Cloud RTI, который создавался на основе open-source.

В этой статье, расшифровке видео, рассказывается, как настроить Kubernetes вместе с другими компонентами с открытым исходным кодом для получения готовой к производству среды, которая без простоев в продакшене воспринимает код из коммита изменений git commit.

Сегодня мы поговорим о Kubernetes, в частности, о его автоматизации. Мы немного рассмотрим основы этой системы, а затем перейдем к тому, как встраивать Kubernetes в проекты на стадии разработки. Меня зовут Пол, я из Нидерландов, работаю в компании под названием Luminis Technologies и являюсь автором книг «Конструирование облачных приложений с OSGi» и «Модулирование Java 9». То, о чем я буду говорить, сильно отличается от темы этих книг.
В последний год большая часть моего времени была затрачена на работу над инфраструктурной платформой на базе Kubernetes и создание для нее инструментов, преимущественно на Golang. Кроме того, я все еще продолжаю работать над книгой по Java 9. Мое хобби – тяжелая атлетика. Итак, давайте перейдем к делу.

Почему нужно озаботиться Kubernetes? В первую очередь, потому, что он позволяет запускать Docker в кластерах. Если вы не используете Docker, то вы не в теме. Если вы работаете с Docker, то знаете, что он в основном предназначен для запуска контейнеров на вашей собственной машине. Он улучшает работу со множеством сетей, однако все это ограничено одной машиной, поэтому нет никакой возможности запускать контейнеры в кластере.

Создатели Docker постоянно расширяют его возможности, однако если вам действительно нужно запускать контейнеры в продакшене, вам понадобится что-то на подобии Kubernetes, потому что Docker с его командной строкой в этом не поможет.

Поговорим об основах Kubernetes. Прежде чем мы рассмотрим использование API для автоматизации, необходимо понять концепцию работы этой платформы. Типичный кластер включает в себя следующие элементы. Мастер-нод осуществляет управление и контроль работы всего кластера и решает, где будут запланированы контейнеры и каким образом они будут запущены. Он запускает API-сервер, который является важнейшим элементом работы платформы, позже мы подробно рассмотрим этот вопрос.

Здесь имеется целая куча рабочих узлов Node, в которых содержаться поды Pods с контейнерами Docker, и распределенное хранилище etcd. Узлы – это место, где будут запускаться ваши контейнеры. Kubernetes не работает с контейнерами Docker непосредственно, а использует для этого абстракцию под названием Pod. Рабочие ноды запускают кучу контейнеров, а Master-node заботится о том, чтобы они работали. Кроме того, здесь имеется распределенное хранилище etcd типа «ключ-значение», в котором хранится вся информация о кластере. Etcd является отказоустойчивым, так что по крайней мере состоит из 3 независимых нодов. Это обеспечивает работу мастера без потери состояния.

После запуска Kubernetes со всеми вышеупомянутыми компонентами начинается развертывание контейнеров scheduling. Развертывание означает, что контейнеры начинают работу в кластере. Для выполнения этой работы в первую очередь вам нужен объект под названием Replication Controller, запускаемый на мастер-сервере, который позволяет создать и отслеживать состояние нескольких экземпляров подов.

Чтобы настроить контроллер репликации на создание, например, 5 реплик контейнеров в пяти различных рабочих узлах, нужно располагать таким количеством узлов. Кроме того, что контроллер начинает работу этих контейнеров, он отслеживает их состояние. Если из-за нехватки памяти один из контейнеров выйдет из строя, контроллер зафиксирует уменьшение количества с 5 до 4 и запустит новый контейнер на одном из доступных узлов. Это означает, что при работе Kubernetes вы не запускаете контейнеры на каких-то конкретных узлах, а задаете требуемое состояние — настраиваете платформу на развертывание 5 контейнеров и передаете управление контроллеру репликации, который заботится о том, чтобы поддерживать это состояние. Так что Replication Controller является очень важным концептом.

Как я сказал, Kubernetes не работает с контейнерами напрямую. Он делает это через Pod – абстракцию на вершине контейнеров. Важно, что Kubernetes оперирует не только Docker-контейнерами, но и, например, его альтернативой – контейнерами rkt. Это не официальная поддержка, потому что если посмотреть техническую документацию Kubernetes, в ней говорится только о контейнерах Docker. Однако по мере развития платформы в нее добавляется совместимость с контейнерами других форматов.

Каждый под может содержать множество контейнеров с одинаковым циклом жизни. Это означает, что мы не сможем запускать в одном поде контейнеры различного назначения, потому что все они могут существовать только в один и тот же период времени. Они запускаются одновременно и одновременно прекращают свою работу. Так что если вы работаете с микросервисами, то не сможете поместить их все в один и тот же под. Контейнеры внутри пода «видят» друг друга на локальном хосте.

Если вы, к примеру, разворачиваете веб-сервис, то pod для этого приложения будет содержать контейнер nginx, причем nginx не модифицированный, а прямо «из коробки». Для того, чтобы этот nginx заработал, мы должны будем добавить свои собственные HTML-файлы и поместить их в отдельный контейнер веб-файлов. Оба эти контейнера помещаются в один общий под и начинают работать совместно, как если бы существовали на одной физической машине, поэтому они видят файлы одной и той же файловой системы, размещенные на одном и том же локальном хосте. Службы services, обеспечивающих взаимодействие компонентов кластера, работают при помощи переменных среды env vars.

Следующее, что обеспечивает под – это сетевое взаимодействие networking. Если вы запускаете несколько контейнеров на одной физической машине, которая также может размещаться в облаке, и все эти контейнеры используют порты, например, мы используем 3 приложения Java, которые работают с одним и тем же портом 8080, то это чревато конфликтом. Чтобы его избежать, вам понадобится разметка портов port mapping, что значительно осложнит процесс развертывания приложений.

Поэтому было бы прекрасно, если бы каждый запускаемый контейнер имел свой собственный виртуальный IP-адрес с доступом ко всем доступным портам, не задумываясь об их возможном конфликте. Это именно то, что обеспечивает Kubernetes.

Каждый раз, создавая pod, он создает для него собственный виртуальный IP-адрес. Порты не делятся между остальными подами, поэтому никакого конфликта не наблюдается. Единственная вещь, работающая по этому IP-адресу – это то, что делает данный контейнер. Это все упрощает.
Однако при этом возникает новая проблема: если ваш виртуальный IP-адрес меняется каждый раз при перезапуске контейнеров, что нередко случается, то как же вы сможете использовать эти контейнеры? Предположим, у нас есть 2 разных пода, которые связываются друг с другом, однако их IP-адреса все время меняются. Для решения этой проблемы Kubernetes использует концепт под названием services. Эти сервисы настраивают прокси на вершине ваших подов и продолжают использовать виртуальные IP-адреса определенного диапазона, но это фиксированные адреса, которые не меняются все время.

Поэтому когда поды хотят связаться друг с другом, они делают это не напрямую, а через services, используя эти фиксированные IP-адреса.

Эти services организуют трафик всех реплик, которым обмениваются между собой компоненты кластера. Поэтому services очень важны для обеспечения коммуникации между компонентами.
Концепция Services значительно облегчает мультикомпонентный процесс развертывания, когда несколько компонентов являются частью более крупного приложения, относящегося, например, к архитектуре микросервисов, хотя лично я не люблю иметь дело с микросервисами.

Каждый имеющийся у вас компонент может быть развернут как отдельный под со своим собственным жизненным циклом. Они не зависят друг от друга и имеют отдельные пространства имен, свои собственные IP-адреса и диапазоны номеров портов, могут независимо обновляться и масштабироваться. Использование services значительно облегчает межкомпонентную коммуникацию. На следующем слайде приведен пример приложения из нескольких компонентов.

Первый под Frontend представляет собой интерфейс пользователя, который использует несколько бэкенд-сервисов, или реплик бэкенд-сервисов. Вы видите пачку из нескольких таких подов, для взаимодействия с которыми в качестве прокси используются службы services. Вас не должна заботить работоспособность каждого пода, потому что при выходе из строя одного из них Kubernetes автоматически перезапустит новый. Бэкенд-сервис использует ряд других служб, расположенных в разных подах, и все они используют для взаимодействия концепцию services. Все это отлично работает, так что если вы используете такую архитектуру, Kubernetes легко обеспечит ее развертывание. Если архитектура построена по другому принципу, у вас могут быть проблемы.

Следующая важная концепция, с которой нужно познакомиться, это пространство имен Namespaces.

Это изолированные пространства внутри Kubernetes, в которых содержася поды, контроллеры репликации и сервисы. Изоляция означает, например, что когда среда разработки находится в одном пространстве имен, а продакшн – в другом, вы используете services с одинаковым именем для предотвращения конфликта между разными пространствами имен. Таким образом можно легко расположить разные среды в одном физическом кластере Kubernetes.

Развертывание приложения является необходимым шагом перед выпуском приложения в продакшн. В документации Kubernetes указано, что для осуществления развертывания необходимо использовать инструмент командной строки kubectl. Этот инструмент постоянно совершенствуется и прекрасно подходит для развертывания чего-либо.

Вы видите файлы конфигурации yaml, которые необходимо создать для API с помощью команды kubectl. На следующем слайде показано, как выглядит типичный yaml-файл.

В данном файле мы задаем контроллер репликации. Первой важной частью является строка с количеством реплик, которыми мы хотим располагать, replicas:3. Это количество равно числу узлов, которые нужно задействовать. В данном случае число 3 означает, что мы хотим запустить поды на 3 различных машинах нашего кластера. Контроллер репликации проводит мониторинг состояния системы и при необходимости автоматически перезапускает поды, чтобы обеспечить постоянную работу заданного количества реплик.

В нижней части кода расположены строки, представляющие собой спецификацию пода. Здесь описываются порты, узлы хранилищ, имя и образ веб-сервера и прочая информация, необходимая для нашего Docker-контейнера.

Наконец, здесь имеется целая куча метаданных, таких как метки labels. Метки представляют собой пары «ключ-значение» и добавляются к объектам, как поды. Они используются для группировки и выбора подмножеств объектов. Они очень важны для организации API- взаимодействия, связывая вместе контроллеры, поды и сервисы.

Под не знает, какой контроллер репликации его создал, а контролер репликации не знает список подов, которые создает. Но и поды, и контроллер имеют метки, совпадение которых указывает, что конкретный под принадлежит конкретному контроллеру. Это достаточно слабая, но гибкая связь, которая обеспечивает устойчивую работу API и автоматизированных вещей.

Сейчас вы увидите короткое демо, в котором показана работа kubectl, а далее мы углубимся в работу балансировщика нагрузки и использование API. Итак, я ввожу команду kubectl get pods, но система не показывает никаких подов, потому что мы еще ничего не запустили. Далее я ввожу команду ls, чтобы просмотреть список имеющихся файлов.

Теперь я ввожу название первого файла из списка и на экран выводится конфигурационный yaml-файл, похожий на тот, который мы только что рассмотрели. Давайте используем этот файл для создания пода, введя команду kubectl create –f nginx-controller.yaml. В результате у нас будет создан под. Повторив команду kubectl get pods можно увидеть, что этот под работает.

Но это всего лишь один под. Давайте попробуем масштабировать наш контроллер, создав несколько реплик. Для этого я ввожу команду kubectl scale rc nginx – replicas=5, где rc – это контроллер репликации, а 5 – необходимое количество экземпляров, или реплик этого контроллера. Вы видите ход создания контейнеров, и если повторить ввод команды kubectl get pods через пару секунд, видно, что большинство созданных контейнеров уже начали работать.

Таким образом мы увеличили количество подов, или реплик, работающих в нашем кластере, до 5 экземпляров. Также, к примеру, можно взглянуть на IP-адрес, созданный для первой реплики, введя команду kubectl describe pod nginx-772ia. Это виртуальный IP-адрес, который присоединен к данному конкретному контейнеру.

Его работа будет обеспечена упомянутыми выше службами services. Давайте посмотрим, что произойдет, если уничтожить одну из работающих реплик, ведь у нас в любом случае должна быть обеспечена работа заданного количества экземпляров. Я ввожу команду kubectl delete pod nginx-772ia и система сообщает, что под с таким идентификатором был удален. Использовав команду kubectl get pods, мы видим, что у нас снова работает 5 экземпляров контроллера, а вместо удаленной реплики nginx-772ia появилась новая с идентификатором nginx-sunfn.

Это произошло потому, что Kubernetes заметил выход из строя одной из реплик. В реальности это была не случайная неполадка, а осознанное действие, постольку я собственноручно ее удалил. Но поскольку число реплик, заданное конфигурацией кластера, осталось неизменным, контроллер репликации отметил исчезновение одного из экземпляров и тут же восстановил требуемое состояние кластера созданием и запуском нового контейнера с новым ID. Конечно, это глупый пример, когда я сам удаляю реплику и жду, что контроллер ее восстановит, но аналогичные ситуации происходят в реальной жизни вследствие сбоя контейнера, например, из-за нехватки памяти. В этом случае контроллер также перезапустит под.

Если у нас имеется несколько продакш-сценариев, в которых приложение Java неправильно настроено, например, установлено недостаточное количество памяти, это может вызвать сбой как через несколько часов, так и спустя недели после запуска программы. В таких случаях Kubernetes позаботиться о том, чтобы рабочий процесс не прерывался.

Еще раз напомню, что все вышесказанное не применимо на этапе продакшн, когда для обеспечения работы продукта вы не должны использовать командную строку kubectl и прочие вещи, вводимые с клавиатуры. Так что перед тем, как мы приступим к автоматизации развертывания, нужно решить еще одну большую проблему. Предположим, у меня прямо сейчас работает контейнер nginx, но я не имею к нему доступа из «внешнего мира». Однако если это веб-приложение, то я могу получить к нему доступ через интернет. Для обеспечения стабильности этого процесса используется балансировщик нагрузки, который располагается перед кластером.
Нам нужно получить возможность управлять сервисами Kubernetes из внешнего мира, причем эта возможность не поддерживается автоматически «прямо из коробки». К примеру, для обеспечения HTTP-балансировки нужно использовать SSL offloading, или выгрузку SSL. Это процесс удаления шифрования на основе SSL из входящего трафика, который получает веб-сервер, выполняемый для того, чтобы освободить сервер от расшифровки данных. Для балансировки трафика можно использовать также Gzip-сжатие веб-страниц.

В последних версиях Kubernetes, например, 1.02, имеется новая функция под названием Ingress. Она служит для конфигурирования балансировщика нагрузки. Это новая концепция в API, при которой вы можете написать плагин, который настроит любой используемый вами внешний балансировщик нагрузки.

К сожалению, на сегодня эта концепция не доработана до конца и предлагается в альфа-версии. Можно продемонстрировать, как она будет работать в будущем, однако это не будет соответствовать тому, как она работает сегодня. Я использую балансировщик, предоставляемый Google Cloud Engine, однако если вы не работаете с этим сервисом, вам придется что-нибудь сделать самим, по крайней мере, в данный момент. В будущем, вероятно, через месяц, это станет намного легче – для балансировки трафика можно будет использовать функцию ingress.

На сегодня эта проблема решается созданием пользовательского балансировщика трафика. В первую очередь можно использовать ha-прокси, расположенный перед кластером Kubernetes. Он работает снаружи кластера на внешней машине или наборе машин. Далее необходимо предусмотреть автоматическое динамическое конфигурирование ha-прокси, чтобы не настраивать его вручную при создании каждого нового пода. Аналогичную работу необходимо выполнить для nginx, Apache и других серверов, и при этом ha-прокси выступает легко интегрируемым инструментом.

На следующем слайде показано, как узел балансировщика нагрузки обрабатывает входящий HTTPS-трафик, причем ha-прокси расположен на внешней машине или кластере машин, расположенном за пределами кластера Kubernetes. Здесь же располагается выгрузка SSL. Прокси определяет запрашиваемые адреса и затем передает трафик сервисам Kubernetes, не интересуясь тем, что IP-адреса подов могут меняться с течением времени. Далее services передают трафик работающим подам с динамическими IP-адресами.

Если вы применяете сервис AWS, можно использовать концепцию балансировщика нагрузки ELB. Elastic Load Balancing перенаправляет трафик на исправные инстансы Amazon, обеспечивая стабильность работы приложений. Этот механизм особенно хорош, если вам нужна масштабируемость балансировщика нагрузки.

В этом случае трафик сначала направляется на сервис AWS, где и происходит выгрузка SSL, после чего он поступает в узел балансировщика нагрузки ha-прокси.

Аналогично можно поступить, если ваши кластеры полностью находятся внутри частной виртуальной сети VPN. В данном случае использование AWS ELB полностью обеспечивает безопасность системы. Вам не нужно осуществлять SSL между различными компонентами за пределами кластера. Единственная вещь, которая будет связана с внешним миром, это наш ha-прокси.

Концептуально это выглядит достаточно просто, но как оно работает в реальности? Как нужно настроить ha-прокси, чтобы он знал о сервисах Kubernetes? Если взглянуть на ha-прокси так же, как мы рассматриваем nginx, можно заметить, что он до сих пор использует статичные файлы конфигурации. Так что если вы хотите добавить к нему новый бэкенд, которым в данном случае являются наши сервисы Kubernetes, нам потребуется изменить файл конфигурации, перегрузить ha-proxy и только после этого все заработает как надо. Разумеется, что мы не хотим выполнять это вручную. Поэтому можно использовать маленький open-source инструмент под названием Confd, который управляет файлами конфигурации локальных приложений с помощью данных etcd. Если в хранилище метаданных etcd происходят изменения, Confd автоматически генерирует конфигурационный шаблон, который перенастраивает ha-прокси в соответствии с новыми условиями работы.

Может показаться, что такой подход требует дополнительных усилий, однако это очень простой инструмент, работающий с шаблонами, поэтому его использование довольно тривиальная задача.

26:00 мин

Продолжение будет совсем скоро…

Немного рекламы 🙂

Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Equinix Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?