Прискорюємо передачу даних в localhost

Зроблено в Росії

Один з найшвидших спосіб межпроцессного взаємодії реалізується за допомогою поділюваної пам'яті (Shared Memory). Але мені здавалося не логічним, що в знайдених мною алгоритмах, пам'ять все одно треба копіювати, а після перезапуску клієнта (причому він допускався лише один) потрібно перезавантажувати сервер. Взявши волю в кулак, я вирішив розробити повноцінний клієнт-сервер з використанням разделимой пам'яті.

І так, спочатку потрібно визначити функціональні вимоги до розроблюваного клієнт-серверу. Перша і основна вимога: дані не повинні копіюватися. По-друге, «мультиклиентность» — до сервера можуть підключатися кілька клієнтів. По-третє, клієнти можуть перепідключатися. І у четвертих, по можливості повинно бути кроссплатформенно. З накладаються вимог, можна виділити складові частини архітектури:

  • компонент, інкапсульовану роботу з пам'яттю, що розділяється;
  • менеджер пам'яті (allocator);
  • компонент, інкапсульовану роботу з пересилання буфером даних та
    реалізує ідеології «copy on write»(далі CBuffer);
  • межпроцессный мютекс;
  • межпроцессная умовна змінна або її аналог;
  • і безпосередньо клієнт і сервер.
Проблем роботи з пам'яттю, що розділяється досить багато. Тому не будемо винаходити велосипед і візьмемо від boost.interprocess по максимуму. По-перше, візьмемо класи shared_memory_object, mapped_region, які полегшать нам роботи з пам'яттю, що розділяється в linux і windows. Від туди можна взяти і реалізацію IPC семафора – який буде виконувати функції як мютекса так і умовної змінної. Також візьмемо в якості зразка для CBuffer, boost реалізацію std::vector (При роботі з пам'яттю, що розділяється оперувати покажчиками можна, тільки зміщеннями. Тому std::vector + allocator нам не підійде). Ще в boost можна знайти реалізацію межпроцессного deque, але як це використовувати при розробці клієнт-сервера я не знайшов. І залишився тільки питання з менеджером пам'яті(allocator) для спільної пам'яті. Природно, і він є в boost, але він орієнтований на вирішення інших завдань. Таким чином, від boost будуть взяті не потребують компілювання бібліотеки (header only). Хоча boost під MSVC може з цією точкою зору не можна погодитися, тому не забуваємо про дубину – препроцесор BOOST_ALL_NO_LIB забороняє використовувати «pragma comment».(Спогади з нічного монологу: «Якого біса линкуются бібліотеки boost!»)

Реалізація клієнта і сервера
Реалізація передачі даних між клієнтами і серверів досить тривіальна. Вона схоже на реалізацію моделі постачальник-споживач (producer-customer) з використанням семафорів, де в якості «переданого» повідомлення використовується зміщення (адреса) передається буфера, а об'єкти синхронізації замінені на їх межпроцессные аналоги. Кожного клієнта і сервера відповідає своя чергу зсувів, яка грає роль приймального буфера і семафор, який відповідає за повідомлення про зміну черги. Відповідно, коли буфер відправляється іншого процесу, то зміщення буфера кладеться в чергу, а семафор звільняється(post). Далі інший процес зчитує дані і захоплює семафор (wait). За замовчуванням процес чекає отримання даних іншим процесом(nonblock). Приклад реалізації можна взяти звідси. На практиці, крім передачі самого буфера часто необхідно ще передати ідентифікаційну інформацію. Зазвичай це ціле число. Тому метод Send додана можливість передачі числа.

Як клієнти підключаються до сервера?

Алгоритм досить простий, дані про сервер лежать строго за визначеним зміщення в поділюваної пам'яті. Коли клієнт «відкриває» поділювану пам'ять він зчитує структуру за заданою адресою, якщо її немає, то сервер відсутній, якщо є, то він виділяє пам'ять для структури даних клієнта, заповнює її і збуджує подія на сервері із зазначенням зміщення на структуру. Далі сервер додає нового клієнта в зв'язаний список клієнтів і збуджує в клієнті подія «підключений». Відключення здійснюється аналогічним чином.

Оцінка стану з'єднання

Перевірка стану з'єднання між клієнтом і сервером побудована аналогічно TCP. З інтервалом часу відправляється пакет життя. Якщо він не доставлений – значить, клієнт «впав». Також щоб уникнути можливих взаємних блокувань(dead lock) з-за «впав» клієнта, який не звільнив об'єкт синхронізації, пам'ять для пакета життя виділяється із власного резерву сервера.

Реалізація менеджера пам'яті
Як виявилося, найскладніше завдання в реалізації подібно IPC — це реалізація менеджера пам'яті. Адже він повинен не просто реалізувати методи malloc і free по одному з відомих алгоритмів, але і не допустити витоку при «падінні» клієнта, надати можливість «резервувати» пам'ять, виділяти блок пам'яті по конкретному зміщення, не допускати фрагментованість, бути потокобезопасным, а в разі відсутності вільних блоків необхідного розміру, очікувати його появи.

Базовий алгоритм

За основу реалізації менеджера пам'яті був узятий Free List алгоритм. Згідно цього алгоритму, не всі виділені блоки пам'яті об'єднуються в односторонній зв'язаний список. Відповідно, при виділення блоку пам'яті (malloc), шукається перший вільний блок, розмір якого не менше необхідного, і видаляється із зв'язаного списку. Якщо розмір потрібного блоку менше ніж розмір вільного, то вільний блок розбивається на два, перший дорівнює відповідного розміру, а другий «зайвого». Перший блок – це виділений блок пам'яті, а другий додається в список вільних блоків. При звільнення блоку пам'яті(free), звільняється блок додається в список вільних. Далі сусідні вільні блоки пам'яті об'єднуються в один. У мережі є безліч реалізація менеджера пам'яті з алгоритмом Free List. Я використовував алгоритм heap_5 з FreeRTOS.

Алгоритмічні особливості

З точки зору розробки менеджера пам'яті, відмінною особливістю роботи з пам'яттю, що розділяється є відсутність «допомоги» з боку ОС. Тому крім списку вільних блоків пам'яті, менеджер зобов'язаний зберігати інформацію про власника блоку пам'яті. Зробити це можна декількома способами: зберігати в кожному виділеному блоці пам'яті PID процесу, створити таблицю «зсув виділеного блоку пам'яті – PID», створити масив виділених блоків пам'яті для кожного PID окремо. Оскільки кількість процесів зазвичай мало (не більше 10), то було прийнято гібридне рішення, в кожному виділеному блоці пам'яті зберігатися індекс (2 байти) масиву зміщень виділених блоків пам'яті, кожному PID відповідає свій масив, який розташований в кінці «блоку процесу» (в цьому блоці зберігатися інформація про процес) і є динамічним.

Масив організований хитро, якщо блок пам'яті виділено процесом, то в комірці зберігатися зміщення виділеного блоку пам'яті, якщо блок пам'яті не виділена, то в комірці міститься індекс наступної «не виділеної» клітинки (фактично організований однозв'язний список «вільних» елементів масиву, як в алгоритмі Free List). Такий алгоритм роботи масиву, дозволяє проводити видалення і додавання адреси за константна час. Причому при виділення нового блоку шукати відповідну таблицю поточного PID необов'язково, її зміщення завжди відомо заздалегідь. А якщо зберігати зміщення «блоку процесу» у виділеному блоці пам'яті, то при звільненні блоку шукати таблицю також не треба. Із-за прийнятого припущення про малість кількості процесів, «блоки процесів» об'єднані в односторонній зв'язаний список. Таким чином, при виділенні нового блоку пам'яті (malloc) складність додавання інформації про власника дорівнює О(1), а при звільненні(free) блоку пам'яті О(n), де n – кількість процесів, що використовують спільну пам'ять. Чому не можна використовувати дерево або хеш-таблиці для швидкого пошуку зміщення «блоку процесу»? Масив виділених блоків є динамічним, отже, зміщення у «блоку процесів» може змінитися.

Як писалося вище, для роботи «клієнт-сервер» необхідно додати можливість «резервування» блоків пам'яті. Це реалізується досить просто, резервний блок пам'яті «виділяється»для процесу. Відповідно, коли необхідно виділити блок пам'яті з резерву, то резервний блок процесу звільняється, і далі операції аналогічні звичайному виділення. Далі, виділення блоку пам'яті по заданому адресою реалізується теж просто, оскільки інформація про выделанных блоках зберігатися в «блоці процесу».

При такій великій кількості постійно зберігається службової інформації може виникнути фрагментація пам'яті з-за різного часу «життя» блоків, тому в менеджері пам'яті вся службова інформація(великий час життя) виділяється з кінця області, а виділення «користувача» блоків(малий час життя) спочатку. Таким образів, службова інформація буде фрагментувати пам'ять тільки при відсутності вільних блоків.

Структура пам'яті представлена на малюнку нижче.

Структура пам'ятіСтруктура пам'яті

А що станеться, якщо один з процесів використовують спільну пам'ять впаде?

На жаль, я не знайшов способу отримати подія від ОС «процес завершився». Але є можливість перевірити існує процес чи ні. Відповідно, коли в менеджері пам'яті виникає помилка, наприклад, закінчилася пам'ять, то менеджер пам'яті перевіряє стан процесів. Якщо процесу не існує, то на підставі даних, що зберігаються в «блоці процесу» потрапила пам'ять повертається в обіг. На жаль, із-за відсутності події «процес завершився», може виникнути ситуація коли процес звалився в момент володіння межпроцессным мъютексом, що, природно, призведе до блокування менеджера пам'яті і неможливості запуску «очищення». Щоб цього уникнути, в заголовок додана інформація про PID власника мъютекса. Тому, при необхідності, користувач можна викликати перевірку примусово, скажімо кожні 2 секунди. (метод watch dog)

Через використання «copy-on-write», може статися ситуація, коли буфером володіють одночасно декілька процесів, причому, за законом підлості, один з них упав. У цьому випадку можуть виникнути дві проблеми. Перша, якщо звалився процес був власником буфера, то він буде видалений, що призведе до SIGNSEV в інших процесів. Друга, з-за того що звалився процес не зменшив лічильник в буфері, то він ніколи не буде видалений, тобто виникне витік. Простого і продуктивного вирішення цієї проблеми я не знайшов, але, на щастя, така ситуація рідкість, тому я прийняв вольове рішення, якщо крім впав процесу є ще один власник, то чорт з ним, хай пам'ять витікає, буфер переміщується до процесу жбурнув очищення.

Зазвичай менеджер пам'яті у разі відсутності вільного блоку пам'яті повертає NULL або викидає виключення. Але нас цікавить» не виділення блоку пам'яті, а його передача, тобто відсутність вільного блоку, говорить не про помилку, а про необхідність почекати поки інший процес звільнить блок. Очікування у циклі, зазвичай погано пахне. Тому менеджер має два режими виділення: класичний, якщо немає вільного блоку, повертає NULL і очікує, якщо немає вільного блоку, то процес блокується.

Реалізація решти компонентів
Основу реалізації решти компонентів становить boost, тому далі я зупинюся тільки на їх особливостях. Особливістю компонента, инкапсулирующего роботу з пам'яттю, що розділяється (далі CSharedMemory) наявність заголовка з межпроцессным мютексом для синхронізації методів роботи з пам'яттю, що розділяється. Як показала практика, без нього не обійтися. Оскільки зазвичай розмір буфера даних не змінюється або змінюється тільки з початку (наприклад, вставка заголовка в буфера даних для передачі по мережі.) алгоритм резервування пам'яті в CBuffer відмінний від коефіцієнтного алгоритму резервування пам'яті в std::vector. По-перше, у реалізації CBuffer додана можливість задавати резерв спочатку, за замовчуванням він дорівнює 0. По-друге, алгоритм резервування пам'яті наступний: якщо розмір виділеного блоку менше 128 байт, то резервується 256 байт, якщо розмір буфера даних менше 65536, то резервується розмір буфера плюс 256 байт, в іншому випадку резервується розмір буфера плюс 512 байт.

Кілька слів з приводу використання sem_init в Linux

Основні джерела дають не зовсім коректну версію програмного коду використання sem_init між процесами. В Linux необхідно вирівнювати пам'ять для структури sem_t, наприклад ось так:

(_sem_t*)(((uintptr_t)mem+__alignof(sem_t))&~(__alignof(sem_t)-1)

Тому, якщо у вас sem_post(sem_wait) повертає EINVAL, спробуйте вирівняти пам'ять для структури sem_t. Приклад роботи з sem_init.

Разом
В результаті вийшов клієнт-сервер, швидкість передачі якого не залежить від обсягу даних, вона залежить тільки від розміру переданого буфера. Ціна цього – деякі обмеження. В Linux найбільш істотне з них — це «витік» пам'яті після «завершення процесу. Її можна видалити вручну або перезавантажити ОС. При використанні windows проблема інша, там «витікає» колективна пам'ять на жорсткому диску, якщо вона не була видалена викликом методу класу сервера. Ця проблема не усувається перезапуском ОС, тільки ручним видаленням файлів у папці boost_interprocess. Оскільки мені інколи доводиться працювати зі старими компіляторами, в репозиторії лежить boost версії 1.47, хоча з останніми версіями, бібліотека працює спритніше.

Результати тестування в Windows представлені на графіку нижче

Тести під WindowsДе взяти код?
Вихідний код стабільної версії лежить тут. Там же є і бінарники (+ VC redistributable) для швидкого запуску тесту. Для любителів QNX в исходниках є toolchain для CMake. Нагадую, якщо CMake не збирає исходники, почистіть змінні оточення, залишаючи тільки каталоги цільового компілятора.

І наостанок посилання на реалізацію LookFree IPC з використанням спільної пам'яті.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.