Archive for category программирование

сумасшедший алгоритм

Posted by John Lepikhin in Performance, программирование on November 16th, 2009

Уже 3-й день размышляю над алгоритмом следующей задачки.

Дано:

  1. Есть кластер. В кластере живёт несколько узлов. В узле живёт несколько веб-серверов. В веб-сервере живёт несколько аккаунтов. В аккаунте живёт несколько сайтов.
  2. Для каждого сайта известна текущая нагрузка. Соответственно, известна нагрузка для каждого из аккаунтов.
  3. Известно количество сайтов в каждом из аккаунтов.
  4. Для каждого аккаунта сказано, на скольких минимум узлах (не веб-серверах) он должен присутствовать. Пусть это будет μ.
  5. Для каждого аккаунта известно, какие веб-серверы обрабатывают его в данный момент.

Задача состоит в том, чтобы перераспределить аккаунты по веб-серверам так, чтобы

  1. Аккаунты с максимальной нагрузкой присутствовали на максимальном числе узлов. Ну и соразмерно все остальные.
  2. Каждый аккаунт представлен минимум на μ узлах.
  3. В пределах одного узла каждый аккаунт представлен лишь один раз.
  4. Текущая нагрузка наиболее равномерно распределена между всеми узлами (или с каким-то коэффициентом — не суть).
  5. Сайты максимально равномерно распределены между всеми веб-серверами, чтобы минимизировать объём памяти каждого из процессов веб-серверов.
  6. Сделать это всё так, чтобы изменения коснулись по возможности минимального количества веб-серверов, чтобы затем минимум их пришлось заставить перечитывать конфиг.
  7. Делать это каким-то хитрым алгоритмом т.к. простой перебор на потенциальные десятки тысяч сайтов может отожрать немало проца и памяти…

Понятно, что идеально соблюсти все условия не получится. Соответственно, надо либо расставить приоритеты условиям, либо ввести коэффициент максимальной допустимой погрешности решения. Решение вырастает весьма объёмным даже для простого перебора. Мне страшно представить о часе, когда надо будет искать более изящные решения.

, ,

No Comments

… И получился GFS :)

Posted by John Lepikhin in программирование on October 24th, 2009

Доделал «сырую» реализацию тех самых функторов из предыдущего поста. Умеем хранить элементы размером до 2^{62} = 4611686018427387904 = 4 эксабайт. Максимальное количество элементов точно не определено, но примерно равно 2^{200} и изменением буквально десятка байт кода может быть увеличена до примерно 2^{450}. Правда, при этом увеличивается фактический размер ключей и чуть-чуть падает скорость.

Реализованы функторы: Sized (заодно храним фактический размер записи), Splitted (правильнее было бы назвать Striped), Distributed (записи раскидываются по нескольким нижележащим хранилищам), COW (обеспечение почти полной атомарности для всяких сложных хранилищ, типа Splitted, за счёт copy-on-write).

Каким-то сумасшедшим performance пока похвастаться не могу (около 12000 килобайтных выборок в секунду, в случае использования хранилища FileSystem), реализация всё-таки ещё сырая.

Коллега на работе сказанул: «Google BigTable что ли сделал?». Я подумал, и решил, что нет, это Google FS :)

, , ,

No Comments

Функционалы против классов

Posted by John Lepikhin in Ocaml, программирование on October 18th, 2009

Товарищ (RedChrom) задал вопрос, что я использую больше при разработке на Окамле. Не особо задумываясь ответил, что фифти-фифти. Потом сделал простой grep на свои исходники, и выяснил, что на 80% всё-таки модули и функторы. Причём, объекты и классы по большей части в очень старых исходниках. Сейчас 100% функторы.

Read the rest of this entry »

, , ,

1 Comment

JavaScript: безопасный код

Posted by John Lepikhin in Ocaml, программирование on October 7th, 2009

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

Как известно, JavaScript — язык c динамической (для классов с утиной) типизацией, с очень плохо развитой системой типов. Стандартный интерпретатор даже в браузерах Mozilla с расширениями разработчика отлавливает минимум ошибок. Практически все эти ошибки — синтаксические. В результате, писать надёжный код на JavaScript предельно сложно. Положение усугубляет фактическая невозможность запуска программы без использования браузера, т.е. нет никакой песочницы для тестов.

В этой статье я попытаюсь описать некоторые технологии, которые помогут знакомому с Ocaml человеку существенно сократить время написания безопасного, стабильного и более-менее компактного JS-кода. Впрочем, описываемые техники есть и для некоторых других языков с развитой системой типов (например, Haskell).

Read the rest of this entry »

, , , ,

6 Comments

Программист спит

Posted by John Lepikhin in программирование on July 23rd, 2009

Скопировал этот шедевр из блога коллеги. Оригинальный источник и автор утерян. Читать всем не программистам!

Read the rest of this entry »

, , ,

1 Comment

Организация бэкапов с помощью LVM

Posted by John Lepikhin in программирование on June 19th, 2009

Вдруг осознал, что я тут двигаю всякие классные технологии, а сам пребываю в каменном веке. Перенёс /home в LVM. Сразу захотелось использовать моментальные инкрементальные бэкапы LVM. Как это сделать в сети написано (точнее, раскопировано и переведено) уже не один десяток раз. Но я пока не встретил ни одной статьи, где простые примеры создания снимка эволюционировали до полноценного скрипта. Восполню этот пробел quick programming’ом.

Read the rest of this entry »

, , , , ,

No Comments

Решение для решателя Sudoku

Posted by John Lepikhin in Blogroll, Ocaml, Performance, программирование on June 10th, 2009

Хотел вечерком размять мозг — набросать какой-нибудь особенно красивый решатель Sudoku на Ocaml. Но возникла мысль изучить вражеские аналоги. Итак, решатель Sudoku размером 800 с небольшим байт:

include Set.Make(struct type t = (int * int) * int let compare = compare end)
 
let (@) g f x = g (f x) and id x = x and sw f x y = f y x and zip x y = (x, y)
 
let fold9 f = let rec loop i = if i>8 then id else loop (i+1) @ f i in loop 0
 
let fold81 f = fold9 (fold9 @ (@) f @ zip)
 
let mark ((i,j),x as e) : t -> t =
  add e @ fold9 (fun k -> remove ((i/3*3 + k/3, j/3*3 + k mod 3), x) @
    remove ((i,j),k) @ remove ((i,k),x) @ remove ((k,j),x))
 
let search =
  let g p f s = fold (f @ sw mark s) (filter ((=) p @ fst) s) in
  fold81 g
 
let read () =
  let f p = Scanf.scanf "%d " (fun x -> if x>0 then mark (p,x-1) else id) in
  fold81 f (fold81 (fold9 @ ((@) add @ zip)) empty)
 
let print s () =
  let pr ((i,j),x) = Printf.printf "%d%c" (x+1) (if j=8 then '\n' else ' ') in
  iter pr s; print_newline ();;
 
search print (read ()) ()

Вы посмотрите эту красоту, это же [почти] совершенство! А если учесть, что 272 байта — это чтение задачи с STDIN и вывод результата, размер кода сокращается до менее чем 600 байт.

Read the rest of this entry »

, , , ,

No Comments

Микроязык OpQL

Posted by John Lepikhin in Ocaml, программирование on June 3rd, 2009

Сделал микроязык запросов для oProxy. Служит, собственно, для управления ею. Что умеет:

  1. Показать всякую текущую статистику (устаревшее show_workers, show_nodes и т.д.)
  2. Управлять списками наблюдения.

Read the rest of this entry »

, , , ,

No Comments

ocaml-epoll

Posted by John Lepikhin in Ocaml, Performance, программирование on May 29th, 2009

Написал биндинг для работы с epoll(7). Пока бета, но на ней уже ради эксперимента написал успешно работающий маленький веб-сервер :) Скачать можно со страницы Software. epoll является аналогом select() и poll(), но с увеличением количества обрабатываемых сокетов сложность остаётся O(1), что позволяет без особых задержек обрабатывать тысячи параллельных соединений.

, ,

2 Comments

oProxy release

Posted by John Lepikhin in oProxy, программирование on May 20th, 2009

Не прошло и полгода, как я решил разродиться на релиз прокси. Назовём его “1.1″.

Read the rest of this entry »

, , , , ,

3 Comments