Задачи на собеседованиях #214. Задачи от Stack Group и решение задач от Virtuozzo

Как насчет свежей порции облачных ноябрьских задачек? А вот и нет! Задачки-то обычные, приземленные. «Облачная» — это компания, нам с тобой эти задачи задает. Встречай — Stack Group, которая предоставляет весь спектр соответствующих услуг: IaaS, storage, VDI / VDI GRID, DRaaS и другие. Облако Stack Group корпоративного класса, построено на базе собственного ЦОД — М1, а также партнерских дата-центров в Москве, Франкфурте и Амстердаме. Как видишь, работодатель большой и завидный :).

Задачи

Исходные данные:

order_header — таблица заголовка заказа:

id
INT IDENTITY(1,1)
Идентификатор таблицы заказа
reg_number
VARCHAR(MAX) NOT NULL
Регистрационный номер заказа
on_date
DATETIME NOT NULL
дата формирования заказа

order_details — таблица деталей заказа:

id
INT IDENTITY(1,1)
идентификатор строки деталей заказа
hdr_id
INT NOT NULL
идентификатор заказа
good_id
INT NOT NULL
идентификатор товара
amount
DECIMAL(19,4) NOT NULL
количество товара
price
DECIMAL(19,2) NOT NULL
цена за единицу измерения товара для данного заказа

Для реализации на Transact-SQL:

1. Напишите скрипты создания таблиц со связями между собой, скрипты должны пересоздавать таблицы.
2. Выберите все заказы и для каждого заказа выберите строку деталей с максимальной суммарной стоимостью товара в заказе; если детали две, то выбрать одну с максимальной стоимостью единицы товара.
3. Напишите хранимую процедуру, которая выполнит обновление всех заказов с заданной даты @date_from по заданную дату @date_to, в которых присутствует товар с заданным идентификатором @good_id_old, и заменит его на товар с идентификатором @good_id_new (данный товар тоже может уже быть в заказе, его следует также просуммировать с существующим). Задачу необходимо выполнить без использования циклов и курсоров.
4. Выполнить предыдущую задачу, если известно, что записей в таблице очень много (~10 миллионов) и таблица является высоконагруженной.

Для реализации на C#:

1. Напишите отображения двух таблиц в Entity Framework согласно нотации Code First, используя синтаксис Fluent.
2. Напишите выборку LINQ, в которой выберите все заказы и для каждого заказа — строку детали с максимальной суммарной стоимостью товара в заказе; если детали две, то выбрать одну с максимальной стоимостью единицы товара.

Для реализации на ASP.NET MVC 5, синтаксис представления Razor:

1. Напишите форму в представлении с использованием HTML и разметки Razor для редактирования строки создания и редактирования строки заказа.

Наш победитель: Jack Black и его решения

Задание 1 (Приложение: run.c)

Окружение создается с помощью механизмов Linux namespaces. Создаем копию дерева ФС для текущего процесса:

if (unshare(CLONE_NEWNS) == -1)
{
  printf("Error: cannot unshare (%s)\n\n", strerror(errno));
  return 1;
}

Приватно монтируем /dev/shm, чтобы избежать конфликтов семафоров программы:

if (mount("tmp", "/dev/shm", "tmpfs", MS_NOSUID, "") == -1)
{
  printf("Error: cannot mount /dev/shm (%s)\n\n", strerror(errno));
  return 1;
}

Дальше следует обычный exec.

Задание 2 (приложение: json.patch)

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

stat("/dev/random", {st_mode=S_IFCHR|0666, st_rdev=makedev(1, 8), ...}) = 0 <0.000006>

Если посмотреть код UUID библиотеки, то можно увидеть

static int have_random_source(void)
{
  struct stat s;
  return (!stat("/dev/random", &s) || !stat("/dev/urandom", &s));
}

void uuid_generate(uuid_t out)
{
  if (have_random_source())
    uuid_generate_random(out);
  else
    uuid_generate_time(out);
}

Таким образом, прямой вызов uuid_generate_random() может избавить от лишней проверки. Однако остается комбинация

open("/dev/urandom", O_RDONLY|O_CLOEXEC) = 3 <0.000007>
fcntl(3, F_GETFD)                        = 0x1 (flags FD_CLOEXEC) <0.000006>
fcntl(3, F_SETFD, FD_CLOEXEC)            = 0 <0.000006>
getuid()                                 = 1000 <0.000006>
getppid()                                = 24557 <0.000005>

Решением может стать вызов более низкоуровневой функции __uuid_generate_random библиотеки с указанием количества элементов. Это дает возможность один раз тратить время на генерацию UUID:

__uuid_generate_random(0x7ffdcded6e60, 0x7ffdcded6e00, 0x7ffdcded6e00, 0) = 0 <0.000534>

А в цикле делать только преобразования:

uuid_unparse(0x7ffdcded6e70, 0x7ffdcded6e30, 0x7ffdcded6e30, 0) = 0 <0.000077>

Против изначальной издержки итерации:

uuid_generate(0x7ffd15645a70, 0xffffffff, 0x7efe536a5780, 0) = 0 <0.000167>
uuid_unparse(0x7ffd15645a70, 0x7ffd15645a80, 0x7ffd15645a80, 0x7efe533db709) = 0 <0.000076>

Конкретно в случае данной программы можно отказаться от использования JSON-библиотеки:

json_object_new_object(0x7fffc0cf5960, 0x7fffffdb, 0x7fffc0cf5c64, 36)     = 0x19e00c0 <0.000075>
json_object_new_string(0x7fffc0cf5c40, 0, 0x19e0370, 0x19e0370)            = 0x19e0380 <0.000075>
json_object_new_int(0, 0x7fffc0cf5c65, 0xc0ff01d000000000, 0)              = 0x19e0400 <0.000074>
json_object_new_int(0, 0, 0, 9)                                            = 0x19e0450 <0.000072>
json_object_object_add(0x19e00c0, 0x400d64, 0x19e0380, 9)                  = 0 <0.000140>
json_object_object_add(0x19e00c0, 0x400d69, 0x19e0400, 2)                  = 0 <0.000073>
json_object_object_add(0x19e00c0, 0x400d70, 0x19e0450, 6)                  = 0 <0.000072>
json_object_to_json_string(0x19e00c0, 16, 0x19e0230, 3)                    = 0x19e0520 <0.000077>
puts("{ "uuid": "0fb70fdf-218b-4869-9d"...)                                = 76 <0.000197>
json_object_put(0x19e0450, 0x7f8d05d9d000, 0x7f8d057699e0, 0x7f8d05494710) = 1 <0.000127>
json_object_put(0x19e0400, 0xffffffff, 0x7f8d05767780, 0)                  = 1 <0.000078>
json_object_put(0x19e0380, 0xffffffff, 0x7f8d05767780, 0x19e0440)          = 1 <0.000075>
json_object_put(0x19e00c0, 0xffffffff, 0x7f8d05767780, 0x19e03f0)          = 1 <0.000074>

в пользу форматированного вывода:

printf("{ "uuid": "%s", "number": %d, "v"..., "19bde036-3cf5-4d61-b70e-d1ec4e4f"..., 1, 1)   = 76 <0.000217>

Результирующий патч в приложении.

Задание 3 (приложение: buils.sh)

Пример вызова скрипта:

./build.sh -f task2.sfx  -n task2 -r 3
./build.sh -f task2.sfx  -n task2 -r 3

К сожалению, под рукой была только Ubuntu, делал на ней.

Разбор решения задач от победителя: комментирует Юрий Пудгородский

Задание 1

В задании требуется понять с помощью strace, отладчика или еще каким-либо способом, как процессы конфликтуют друг с другом. По итогам запуска strace можно определить, что процесс использует именованные posix semaphore и shared memory объекты. В результате параллельно исполняющиеся процессы конкурируют за имя вновь созданных объектов, только первый создавший объекты может успешно работать.

Очевидное решение — создать такое runtime-окружение для каждого процесса, в котором пространство имен posix semaphore объектов не пересекается. Ранее для таких задач пользовались методом runtime interception системного или библиотечного вызова. В перехваченном вызове подменяли имя на уникальное для каждого процесса. Одно из таких решений — определение собственных shm_open() и sem_open() через LD_PRELOAD, подстановка уникального имени с PID процесса как части имени и затем вызов оригинального API через RTLD_NEXT.

С появлением в Linux специальной файловой системы с точкой монтирования /dev/shm, в пространстве имен которой находятся все semaphore и shared memory объекты, а также per-process namespace для mount points, решение может более простым и идеологически общим. В нем мы создаем приватный mount namespace для child process, монтируем в нем свой собственный экземпляр /dev/shm и исполняем в таком окружении timer process.

Именно такое решение в современном стиле process namespaces было выполнено кандидатом — на 100% корректное и элегантное.

Задание 2

Аналогично первому заданию предполагается инструментальное runtime-профилирование с помощью strace и compile-time профилирование для определения узкого места алгоритма. Для начала можно запустить исследуемую программу под time и обратить внимание на соотношение времени исполнения в режиме ядра и пользовательском. Время исполнения в ядре оказывается сравнимым по порядку с пользовательским, что дает нам основание говорить об узком месте, связанном с использованием системных вызовов. Профилирование с помощью strace это подтверждает, также мы получаем не только время исполнения, но и некоторое представление о задаче, решаемой с помощью этих вызовов.

Им оказывается алгоритм генерации случайных UUID, основанный на применении стандартной 3rd party библиотеки libuuid. В процессе генерации libuuid открывает /dev/urandom интерфейс к генератору случайных чисел, предоставляемому ядром Linux, читает необходимое количество случайных данных, закрывает FD и создает случайный UUID на полученной основе. Дальнейшее исследование показывает, что узким местом оказывается именно производительность /dev/urandom. Оптимизации, связанные с устранением многократного повторения stat() или даже модификация исходного текста, чтобы устранить open()/close() для каждого UUID, лишь незначительно снижают общее время. Никакой другой интерфейс, предоставляемый libuuid, не позволяет генерировать большое количество UUID с высокой скоростью.

Решением проблемы может быть использование своего userspace генератора случайных чисел с высокой производительностью и принятие специальных мер для уникальности UUID из разных процессов (примешивание к pseudo-random-данным PID процесса, высокоточной метки времени и так далее). Другими словами, своя собственная реализация UUID-генератора.

После устранения libuuid и обращений к /dev/urandom профилирование покажет, что основная часть userspace-исполнения приходится на JSON-библиотеку. Ее замена на простой форматный printf() дает ускорение приблизительно в три раза и может считаться оправданной в подобных случаях.

Решение кандидата выполнено по двум пунктам из трех, итого оценка 66% из 100% возможных:

• анализ и профилирование — complete;
• замена /dev/urandom на userspace pseudo-random — not complete;
• оптимизация JSON-форматирования — complete.

Задание 3

Не самое интересное задание, проверяющее умение пакетировать RPM и скриптово-интеграционные способности.

В задаче не предполагалось кодирование на языке С, наиболее оптимальным будет автоматический скрипт на Shell/Bash/Python или другом подходящем скриптовом языке. Использование изолированного окружения при запуске самораспаковывающегося исполняемого файла необязательно, так как оно явно не требуется в техническом задании, но может быть обосновано соображениями безопасности.

Решение кандидата — без изоляции процесса распаковки, но с помощью профессионально оформленного скрипта на Bash. 100%.