{\r\n "endpoint": "https:\/\/fcm.googleapis.com\/fcm\/send\/c1KrmpTuRm…",\r\n "expirationTime": null,\r\n "keys": {\r\n "p256dh": "BGyyVt9FFV…",\r\n "auth": "R9sidzkcdf…"\r\n }\r\n}<\/code><\/pre>Далі ми берем цей обʼєкт і відправляємо на наш сервер, де кладемо його у базу даних або зберігаємо іншим способом щоб використовувати його в подальшому.<\/p>\n
Якщо придивитися до структури PushSubscription, можна помітити адрес ендпоінта. Суть в тому, що наш сервер не відправляє сповіщення напряму в браузер. Для цього використовується спеціальний push service, який у кожного розробника браузера свій.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/push-notifications-structure.png\")
\n<\/div>\n<\/div>Нам повезло, що браузери змогли домовитись і стандартизувати протокол push сервіса, тому нам можна не паритись за формат даних для кожного вендора. Усі вони приймають один формат даних, який містить:<\/p>\n
\n- Контент повідомлення<\/li>\n
- Кому його відправити<\/li>\n
- Як саме його відправити, з яким пріорітетом, в який топік та з яким таймаутом.<\/li>\n<\/ul>\n
Кожне повідомлення шифрується за допомогою ключів, що були створені при генерації підписки. Крім цього, потрібно також підписувати повідомлення за допомогою приватного ключа, щоб підтвердити, що це саме наш сервер відправляє повідомлення. Виглядає це ось так:<\/p>\n
\n- Генеруємо пару публічного та приватного ключа, які ще називають VAPID ключами. Цей крок треба зробити всього один раз. В інтернеті купа онлайн сервісів де можна згенерувати ключі.<\/li>\n
- Публічний ключ використовуємо при створенні підписки на стороні браузера. Дальше цей ключ асоціюється з ендпоінтом для конкретної підписки.<\/li>\n
- Приватний ключ використовуємо для підписки повідомлення на стороні нашого сервера.<\/li>\n
- Дальше за допомогою публічного ключа ми можемо перевірити що повідомлення було відправлено саме нашим сервером а не кимось іншим.<\/li>\n<\/ol>\n
Структура VAPID ключа:<\/p>\n
{\r\n "sub": "mailto:bohdan@stefaniuk.io",\r\n "public_key": "sdgdklsnvi2f0m-12dgsg...",\r\n "private_key": "1fn0ASFfnaksf..."\r\n }<\/code><\/pre>Але, як в тому жарті, є нюанс. Subject в VAPID ключі є опціональним і його не обовʼязково відправляти разом з запитом на push сервіс. Проте Сафарі так не вважає, ще й вимагає специфічний формат. Коли я генерував ключі, то мав ось такий sub mailto: <bohdan@stefaniuk.io><\/i>.<\/p>\n
В хромі все працювало чудово, а сафарі кидав помилку, що запит невалідний. Виявилось, що вони не підтримують пробіли та кутові лапки, замінив sub на mailto:bohdan@stefaniuk.io<\/i> і все запрацювало.<\/p>\nРеалізація бекенду<\/b><\/h2>\n
Якщо у вас macOS, то ви не зможете локально протестувати сповіщення. Проблема в тому що .NET не підтримує шифрування AesGcm на маках, тому при відправці вилетить ексепшен. Поки я не знайшов як це обійти.<\/p>\n
На стороні сервера будемо використовувати бібліотеку Lib.Net.Http.WebPush<\/i> яка під капотом буде шифрувати, підписувати та відправляти наші сповіщення. Для цього вона дає декілька базових модельок та один клас для відправки пушів.<\/p>\n
Почнемо з реалізації створення та видалення підписок та зберігання їх в БД. Для цього добавимо клас ApplicationPushSubscription, який описує структуру таблиці та підключимо його в Entity Framework контекст:<\/p>\n
public class ApplicationPushSubscription\r\n{\r\n [Key]\r\n public string P256Dh { get; set; }\r\n public string Endpoint { get; set; }\r\n public string Auth { get; set; }\r\n public Guid UserId { get; set } \/\/ Id користувача в нашій системі\r\n}\r\n\r\npublic class DatabaseContext : DbContext\r\n{\r\n public DbSet<ApplicationPushSubscription> PushSubscriptions { get; set; }\r\n}<\/code><\/pre>Тепер створимо клас PushNotificationsService в який добавимо методи для створення та видалення підписок. Метод створення буде приймати екземпляр класу PushSubscription з бібліотеки Lib.Net.Http.WebPush.<\/p>\n
Його можна було б змінити на свій клас, щоб логіка бібліотеки не просочувалась в інші модулі але задля простоти залишимо так як є.<\/p>\n
public class PushNotificationsService\r\n{\r\n private readonly DatabaseContext _context;\r\n private readonly PushServiceClient _pushClient;\r\n \r\n public PushNotificationsService (DatabaseContext context, PushServiceClient pushClient)\r\n {\r\n _context = context;\r\n _pushClient = pushClient;\r\n }\r\n \r\n public async Task CreateSubscription(Guid userId, PushSubscription pushSubscription)\r\n {\r\n var subscription = new ApplicationPushSubscription()\r\n {\r\n UserId = userId,\r\n AccountId = currentUser.AccountId,\r\n Endpoint = subscription.Endpoint,\r\n P256Dh = subscription.GetKey(PushEncryptionKeyName.P256DH),\r\n Auth = subscription.GetKey(PushEncryptionKeyName.Auth)\r\n };\r\n \r\n if (await _context.PushSubscriptions.AnyAsync(x => x.P256Dh == subscription.P256Dh))\r\n {\r\n return;\r\n }\r\n \r\n _context.PushSubscriptions.Add(subscription);\r\n \r\n try\r\n {\r\n await _context.SaveChangesAsync();\r\n }\r\n catch (DbUpdateException)\r\n {\r\n var alreadyExists = await _context.PushSubscriptions.AnyAsync(x => x.P256Dh == subscription.P256Dh);\r\n if (!alreadyExists)\r\n {\r\n throw;\r\n }\r\n }\r\n }\r\n \r\n public async Task DeleteSubscription(Guid userId, string endpoint)\r\n {\r\n var subscription = await _context.PushSubscriptions\r\n .FirstOrDefaultAsync(x => x.UserId == userId && x.Endpoint == endpoint);\r\n \r\n if (subscription == null)\r\n {\r\n return;\r\n }\r\n \r\n _context.PushSubscriptions.Remove(subscription);\r\n await _context.SaveChangesAsync();\r\n }\r\n}<\/code><\/pre>Реалізовуємо метод для відправки сповіщень нашим користувачам. Він буде приймати Id користувача якому ми відправляємо повідомлення і модель з даними.<\/p>\n
Нам залишається отримати підписку з БД, серіалізувати повідомлення в JSON і скормити це все бібліотеці.<\/p>\n
public async Task SendNotificationAsync(Guid userId, PushNotificationModel model)\r\n{\r\n try\r\n {\r\n var applicationPushSubscriptions = await _context.PushNotifications\r\n .Where(x => x.UserId == userId)\r\n .ToList();\r\n \r\n foreach(var applicationPushSubscription in applicationPushSubscriptions)\r\n {\r\n var pushSubscription = new PushSubscription();\r\n pushSubscription.Endpoint = applicationPushSubscription.Endpoint;\r\n pushSubscription.SetKey(PushEncryptionKeyName.P256DH, applicationPushSubscription.P256Dh);\r\n pushSubscription.SetKey(PushEncryptionKeyName.Auth, applicationPushSubscription.Auth);\r\n \r\n var settings = new JsonSerializerSettings { ContractResolver = new CamelCasePropertyNamesContractResolver() };\r\n var payload = JsonConvert.SerializeObject(model, settings);\r\n \r\n var pushMessage = new PushMessage(payload);\r\n await _pushClient.RequestPushMessageDeliveryAsync(\r\n pushSubscription,\r\n pushMessage,\r\n _pushClient.DefaultAuthentication,\r\n VapidAuthenticationScheme.WebPush);\r\n }\r\n }\r\n catch (PushServiceClientException exception)\r\n {\r\n if (exception.StatusCode is HttpStatusCode.NotFound or HttpStatusCode.Gone)\r\n {\r\n _context.PushSubscriptions.Remove(subscription);\r\n await _context.SaveChangesAsync();\r\n }\r\n else\r\n {\r\n \/\/ Re-Throw exception or log\r\n }\r\n }\r\n catch (Exception exception)\r\n {\r\n \/\/ Re-Throw exception or log\r\n }\r\n}<\/code><\/pre>Структура класу PushNotificationModel<\/i> досить проста та універсальна. Я передаю заголовок сповіщення, текст та додаткові дані:<\/p>\npublic class PushNotificationModel\r\n{\r\n public string Title { get; set; }\r\n public string Body { get; set; }\r\n public object AdditionalData { get; set; }\r\n}<\/code><\/pre>Підключаємо наш сервіс в ендопінт:<\/p>\n
[Route("api\/push-notifications")]\r\n[Authorize]\r\n[ApiController]\r\npublic class PushNotificationsController : ControllerBase\r\n{\r\n private readonly PushNotificationService _pushNotificationService;\r\n\r\n public PushNotificationsController(PushNotificationService pushNotificationService)\r\n {\r\n _pushNotificationService = pushNotificationService;\r\n }\r\n \r\n [HttpPost("subscriptions")]\r\n public async Task<IActionResult> CreateSubscription([FromBody] PushSubscription subscription)\r\n {\r\n var user = HttpContext.GetCurrentUser(); \/\/ Our custom method to get current logged-in user\r\n await _pushNotificationService.CreateSubscription(user.Id, subscription);\r\n return Ok();\r\n }\r\n\r\n [HttpDelete("subscriptions")]\r\n public async Task<IActionResult> DeleteSubscription([FromQuery] string endpoint)\r\n {\r\n var user = HttpContext.GetCurrentUser();\r\n await _pushNotificationService.DeleteSubscription(user.Id, endpoint);\r\n return Ok();\r\n }\r\n}<\/code><\/pre>Все що залишається — підключити наші класи в DI і все готово. Для простоти підключення можемо добавити ще один пакет Lib.AspNetCore.WebPush<\/i>.<\/p>\nservices.AddTransient<PushNotificationService>();\r\nservices.AddMemoryVapidTokenCache();\r\nservices.AddPushServiceClient(options =>\r\n{\r\n var clientOptions = configuration.GetSection(nameof(PushServiceClient));\r\n options.Subject = clientOptions.GetValue<string>(nameof(options.Subject));\r\n options.PublicKey = clientOptions.GetValue<string>(nameof(options.PublicKey));\r\n options.PrivateKey = clientOptions.GetValue<string>(nameof(options.PrivateKey));\r\n});<\/code><\/pre>Реалізація фронтенда<\/b><\/h2>\n
Підтримка технології Web Push була додана в Сафарі тільки в версії MacOS 13 та вище.<\/p>\n
Перше, що потрібно реалізувати на стороні клієнта — це запит прав на отримання сповіщень. Для цього використовуємо обʼєкт Notification<\/i>:<\/p>\n\/\/ Запит у браузера прав на підключення пушей\r\nasync function askPermission() {\r\n const permissionPromiseResult = await new Promise(function (resolve, reject) {\r\n const permissionResult = Notification.requestPermission(function (result) {\r\n resolve(result);\r\n });\r\n\r\n if (permissionResult) {\r\n permissionResult.then(resolve, reject);\r\n }\r\n });\r\n \r\n if (permissionPromiseResult !== 'granted') {\r\n alert("We weren't granted permission.");\r\n } else {\r\n await subscribeUserToPush();\r\n }\r\n}<\/code><\/pre>Після того, як отримали права, нам потрібно зареєструвати service worker в якому буде логіка відображення сповіщень, створити підписку та відправити її на наш сервер.<\/p>\n
При створенні підписки необхідно передати наш публічний ключ. Але він повинен бути в форматі масиву байтів, тому треба спочатку його декодувати і вже тоді передавати.<\/p>\n
В результаті отримуємо обʼєкт pushSubscription<\/i>, який ми відправляємо на створений раніше ендпоінт. Крім цього, ще відправляємо Bearer<\/i> токен, щоб розуміти до якого користувача привʼязати підписку.<\/p>\nconst publicKey = "vapid-public-key";\r\n\r\nasync function subscribeUserToPush() {\r\n const registration = await navigator.serviceWorker.register('\/service-worker.js');\r\n const subscribeOptions = {\r\n userVisibleOnly: true,\r\n applicationServerKey: urlBase64ToUint8Array(publicKey),\r\n };\r\n\r\n var pushSubscription = await registration.pushManager.subscribe(subscribeOptions);\r\n \r\n fetch('http:\/\/localhost:5000\/api\/push-notifications\/subscriptions', {\r\n method: 'POST',\r\n headers: {\r\n 'Content-Type': 'application\/json',\r\n 'Authorization': 'Bearer 1245'\r\n },\r\n body: JSON.stringify(pushSubscription)\r\n }).then(function (response) {\r\n if (response.ok) {\r\n alert('Successfully subscribed for Push Notifications');\r\n } else {\r\n alert('Failed to store the Push Notifications subscription on server');\r\n }\r\n }).catch(function (error) {\r\n console.log('Failed to store the Push Notifications subscription on server: ' + error);\r\n });\r\n \r\n return pushSubscription;\r\n}\r\n\r\nfunction urlBase64ToUint8Array(base64String) {\r\n var padding = '='.repeat((4 - (base64String.length % 4)) % 4);\r\n var base64 = (base64String + padding).replace(\/\\-\/g, '+').replace(\/_\/g, '\/');\r\n\r\n var rawData = window.atob(base64);\r\n var outputArray = new Uint8Array(rawData.length);\r\n\r\n for (var i = 0; i < rawData.length; ++i) {\r\n outputArray[i] = rawData.charCodeAt(i);\r\n }\r\n return outputArray;\r\n};<\/code><\/pre>Наш сервіс воркер буде максимально простим. Для початку додамо логіку відображення пушей та передачі в них додаткових даних з сервера.<\/p>\n
Також необхідно додати логіку обробки кліку по сповіщенню. Ми будемо перевіряти чи відкритий сайт в браузері. Якщо ні, то відкривати його в новій вкладці. А якщо у нас вже є вкладка з сайтом, то переключаємось на неї і робимо редірект на потрібну сторінку.<\/p>\n
self.addEventListener('push', function (event) {\r\n var data = event.data.json();\r\n \/\/ {\r\n \/\/ "title": "New Notification",\r\n \/\/ "body": "This is the body of the notification"\r\n \/\/ "additionalData": {\r\n \/\/ "pageId": "12512515"\r\n \/\/ }\r\n \/\/ }\r\n\r\n event.waitUntil(self.registration.showNotification(data.title, {\r\n body: data.body,\r\n icon: '\/logo.png',\r\n data: {\r\n pageId: data.additionalData?.pageId,\r\n },\r\n }));\r\n});\r\n\r\nself.addEventListener('notificationclick', function (event) {\r\n var notification = event.notification;\r\n\r\n event.waitUntil(\r\n self.clients.matchAll().then(function (allClients) {\r\n if (allClients.length === 0) {\r\n self.clients.openWindow(\r\n `${self.location.origin}\/page\/${notification?.data?.pageId}`,\r\n );\r\n notification.close();\r\n return;\r\n }\r\n\r\n allClients[0]?.navigate(`\/page\/${notification?.data?.pageId}`);\r\n allClients[0]?.focus();\r\n notification.close();\r\n }),\r\n );\r\n});<\/code><\/pre>В результаті всіх цих маніпуляцій у нас є сервер, який вміє відправляти сповіщення та клієнт, який вміє створювати підписки, відображати сповіщення та обробляти кліки.<\/p>\n
Окремо ще можна поговорити про топіки та пріоритети сповіщень, але це виходить за рамки цієї статті. Можливо, розкажу про це пізніше :)<\/p>\n
Ресурси<\/b><\/h2>\n\n- Оглад того як працюють пуші<\/a><\/li>\n
- Стаття з прикладом реалізації пушів за допомогою ASP.NET<\/a><\/li>\n
- Репозиторій з прикладами використання бібліотеки<\/a><\/li>\n<\/ul>\n",
"date_published": "2023-06-08T20:43:17-04:00",
"date_modified": "2023-06-08T20:42:47-04:00",
"tags": [
"asp.net core",
"код",
"програмування"
],
"image": "https:\/\/www.stefaniuk.website\/pictures\/push-notifications-structure.png",
"_date_published_rfc2822": "Thu, 08 Jun 2023 20:43:17 -0400",
"_rss_guid_is_permalink": "false",
"_rss_guid": "277",
"_e2_data": {
"is_favourite": false,
"links_required": [
"system\/library\/highlight\/highlight.js",
"system\/library\/highlight\/highlight.css"
],
"og_images": [
"https:\/\/www.stefaniuk.website\/pictures\/push-notifications-structure.png"
]
}
},
{
"id": "271",
"url": "https:\/\/www.stefaniuk.website\/all\/ordered-queue-and-heap\/",
"title": "Очередь с приоритетом",
"content_html": "
Представим что нужно спроектировать список задач. У каждой задачи есть приоритет, это значит, что вначале должны быть самые приоритетные задачи. Сами задачи можно обрабатывать только по одной, мы не можем взять задачу с центра списка.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-pic-1.png\")
\n<\/div>\n<\/div>Такой список достаточно просто реализовать с помощью обычного массива. Задачи будем хранить в случайном порядке, а в момент получения текущей задачи будем искать самую приоритетную. В таком случае добавление новой задачи будет иметь сложность O(1), а вот получение O(n), потому что каждый раз нужно искать элемент с самым большим приоритетом.<\/p>\n
Второй вариант тоже использует обычный массив, только элементы в нем хранятся уже в отсортированном виде. В таком случае сложность меняется зеркально. Добавление нового элемента будет занимать O(n), а получение O(1).<\/p>\n
Оба варианта не совсем эффективны, особенно когда очень много данных. Здесь на помощь приходят очереди с приоритетом.<\/p>\n
Очереди с приоритетом строятся на базе такой структуры данных как куча. Поэтому важно рассмотреть ее устройство. Куч есть большое множество, но нас сейчас интересует только двоичная куча.<\/p>\n
Двоичная куча<\/h2>\n
Двоичная куча представляет из себя двоичное дерево где каждый элемент имеет два дочерних элемента и хранит значение не меньшее чем в дочерних. Они также делятся на два типа: максимальная и минимальная. В первой хранятся элементы в порядке убывания, а во второй в порядке возрастания.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-max-min-2.png\")
\n<\/div>\n<\/div>Для хранения данных кучи удобно использовать обычные массивы. Такой подход занимает мало места и сам по себе достаточно элегантный. На как определить какой элемент массива на какой ссылается? Для этого есть две простые формулы.<\/p>\n
\n- 2i + 1 — позволяет найти позицию левого дочернего элемента<\/li>\n
- 2i + 2 — позволяет найти позицию правого дочернего элемента<\/li>\n<\/ul>\n\n
![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-array-structure-3.png\")
\n<\/div>\n<\/div>Сортировка дерева<\/h2>\n\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-sorting-4.png\")
\n<\/div>\n<\/div>Когда добавляем или удаляем элемент из очереди, свойства кучи могут нарушиться. В таком случае нужно привести ее в порядок. Представим, что есть метод MakeHeap, который принимает на вход индекс элемента и он сортирует его поддерево.<\/p>\n
Берем элемент по текущему индексу и сравниваем его с дочерними элементами. Если какой-то дочерний элемент больше текущего, меняем его местами с текущим и спускаемся дальше, чтобы проверить поддерево. Таким образом, мы доходим до конца изначального поддерева сортируя все его поддеревья.<\/p>\n
Как это выглядит в коде:<\/p>\n
private void SortHeap(int i)\r\n{\r\n\tvar size = values.Count;\r\n\tvar left = 2 * i + 1;\r\n\tvar right = 2 * i + 2;\r\n\tvar largest = i;\r\n\t\r\n\tif (left < size && values[left] > values[largest])\r\n\t\tlargest = left;\r\n\t\t\r\n\tif (right < size && values[right] > values[largest])\r\n\t\tlargest = right;\r\n\t\t\r\n\tif (largest != i)\r\n\t{\r\n\t\tvar temp = values[i];\r\n\t\tvalues[i] = values[largest];\r\n\t\tvalues[largest] = temp;\r\n\t\tSortHeap(largest);\r\n\t}\r\n}<\/code><\/pre>Делаем кучу из обычного массива<\/h2>\n
Мы умеем сортировать элементы в поддеревьях, теперь применим этот метод для того, чтобы с обычного массива сделать кучу. Так как потомки гарантированно есть у первых (n\/2 — 1) элементов, то достаточно только для них вызвать метод SortHeap.<\/p>\n
private void MakeHeap()\r\n{\r\n\tfor (int i = values.Count \/ 2 - 1; i >= 0; i--)\r\n\t{\r\n\t\tSortHeap(i);\r\n\t}\r\n}<\/code><\/pre>Добавление нового элемента<\/h2>\n\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-insert-5.png\")
\n<\/div>\n<\/div>Новый элемент сначала добавляется в конец массива, после чего запускаем сортировку дерева. Алгоритм получается достаточно простым:<\/p>\n
if (values.Count == 0)\r\n{\r\n\t\/\/ Просто добавляем в элемент в массив, если он пустой\r\n\tvalues.Add(value);\r\n}\r\nelse\r\n{\r\n\t\/\/ Добавляем элемент в конец массива и запускаем сортировку дерева\r\n\tvalues.Add(value);\r\n\tfor (int i = values.Count \/ 2 - 1; i >= 0; i--)\r\n\t{\r\n\t\tSortHeap(i);\r\n\t}\t\t\r\n}<\/code><\/pre>Удаление элемента<\/h2>\n\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-remove-5.png\")
\n<\/div>\n<\/div>Чтобы удалить элемент нужно поменять его с последним элементов в куче, потом удалить и запустить сортировку кучи. Так как мы делаем очередь, то будем всегда удалять первый (корневой) элемент кучи.<\/p>\n
var size = values.Count;\r\n\t\t\r\nvar last = values.Count - 1;\r\nvar temp = values[0];\r\nvalues[0] = values[last];\r\nvalues[last] = temp;\r\nvalues.RemoveAt(last);\r\n\r\nfor (int i = size \/ 2 - 1; i >= 0; i--)\r\n\tSortHeap(i);\r\n\r\nreturn temp;<\/code><\/pre>Итого<\/h2>\n
Куча обладает необходимыми свойствами для создания очереди с приоритетом. Она хранит данные в отсортированном виде, работает быстрее чем обычный массив. Достаточно реализовать такие же методы как в обычной очереди и у нас получиться очередь с приоритетом:<\/p>\n
\n- Enqueue — обычная вставка в кучу, ничего даже менять не нужно.<\/li>\n
- Dequeue — обычное удаление элемента с кучи, только удаляем мы всегда элемент с 0 индексов.<\/li>\n<\/ul>\n
Посмотреть полную реализацию можно на dotnetfiddle<\/a>.
\n <\/p>\n",
"date_published": "2022-07-05T16:29:29-04:00",
"date_modified": "2022-07-05T16:28:12-04:00",
"tags": [
"dotnet",
"алгоритми та структури даних",
"програмування"
],
"image": "https:\/\/www.stefaniuk.website\/pictures\/heap-pic-1.png",
"_date_published_rfc2822": "Tue, 05 Jul 2022 16:29:29 -0400",
"_rss_guid_is_permalink": "false",
"_rss_guid": "271",
"_e2_data": {
"is_favourite": false,
"links_required": [
"system\/library\/highlight\/highlight.js",
"system\/library\/highlight\/highlight.css"
],
"og_images": [
"https:\/\/www.stefaniuk.website\/pictures\/heap-pic-1.png",
"https:\/\/www.stefaniuk.website\/pictures\/heap-max-min-2.png",
"https:\/\/www.stefaniuk.website\/pictures\/heap-array-structure-3.png",
"https:\/\/www.stefaniuk.website\/pictures\/heap-sorting-4.png",
"https:\/\/www.stefaniuk.website\/pictures\/heap-insert-5.png",
"https:\/\/www.stefaniuk.website\/pictures\/heap-remove-5.png"
]
}
},
{
"id": "269",
"url": "https:\/\/www.stefaniuk.website\/all\/binary-search-and-binary-search-tree\/",
"title": "Бинарный поиск и бинарное дерево поиска",
"content_html": "Бинарный поиск один из самых популярных и простых алгоритмов поиска. Он активно используется во многих системах, например в базах данных для быстрого поиска и индексирования.<\/p>\n
Первое что нужно знать — алгоритм работает только на отсортированных данных. Поэтому перед поиском нужно отсортировать массив.<\/p>\n
Начинается алгоритм с того что берем элемент из середины массива и сравниваем с искомым значением. Если искомый элемент больше среднего, тогда искомое значение лежит в правой части массива. Идем в правую часть массива, опять берем элемент из середины и сравниваем его с искомым. В этот раз искомый элемент меньше среднего, тогда он скорее всего находится в левой части этого под массива.<\/p>\n
Таким образом мы постоянно сравниваем искомое значение со значением из середины массива. После этого откидываем половину значений. Это здорово ускоряет поиск, потому что не нужно проверять все элементы массива. На каждом этапе отбрасывается половина элементов.<\/p>\n
В итоге всех операций наступает момент когда искать приходиться в массиве из одного элемента. В таком случае просто сравниваем с искомым, если равны, тогда мы нашли элемент, если не, тогда не нашли.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/binary-search-1.png\")
\n<\/div>\n<\/div>А теперь живой пример. Есть отсортированный массив и нужно найти число 9. Берем элемент из середины — 8, сравниваем, 9 больше 8, значит нужно продолжить поиск в правой части.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/binary-search-2.png\")
\n<\/div>\n<\/div>Снова берем элемент из середины — 11, 9 меньше 11, значит нужно искать в левой части нашего подмассива.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/binary-search-3.png\")
\n<\/div>\n<\/div>Берем элемент из середины — 9, сравниваем, элементы равны, число 9 есть в массиве и храниться по индексу 4. Мы нашли нужный элемент всего за 3 шага.<\/p>\n
Если пробовать оценить скорость работы алгоритма, то получается что она равна O(log n). Для сравнения, обычный поиск перебором имеет скорость O(n), это значит что нужно перебрать все элементы массива. Что это значит на практике?<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/binary-search-speed.png\")
\n<\/div>\n<\/div>Посмотреть реализацию на C# можно на dotnetfiddle<\/a>.<\/p>\nКак оптимизировать сортировку?<\/h2>\n
Массив всегда должен быть отсортированным чтобы поиск работал, а это значит что при каждом добавлении нового элемента нужно запускать сортировку. Возникает вопрос, а что если сразу вставлять новый элемент в правильное место? Тогда у нас всегда будет отсортированный массив и не нужно каждый раз прогонять сортировку.<\/p>\n
Так же подумали умные ребята и придумали бинарное дерево поиска. Это структура данных, которая основывается на работе бинарного поиска. По сути это реализация бинарного поиска в виде структуры данных.<\/p>\n
Структура дерева достаточно простая: каждый элемент может иметь только два дочерних элемента. Их еще часто называют левым и правым. В левом дочернем элементе храниться значение, меньше чем в родительском, а в правом — больше.<\/p>\n
Как работает поиск в дереве?<\/h2>\n
Сравниваем искомое значение со значением в корневом элементе. Если оно больше, тогда мы идем к правому дочернему элементу и повторяем процедуру. Таким образом мы начинаем с самого верха и плавно опускаемся пока не найдем элемент с таким же значением.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/binary-search-tree-1.png\")
\n<\/div>\n<\/div>Вставка нового элемента работает так же как и поиск. Сравниваем новый элемент с текущим и опускаемся по дереву вниз пока не найдем подходящее место. В итоге при каждом добавлении у нас будет отсортированный набор данных.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/binary-search-tree-2.png\")
\n<\/div>\n<\/div>Но что будет если всегда добавлять элементы с все большим и большим значением? Наше дерево будет выглядеть вот так:<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/binary-search-tree-3.png\")
\n<\/div>\n<\/div>По сути для поиска значения на нужно обойти все элементы дерева, а это значит что скорость работы упадет до O(n). Получается что бинарное дерево поиска в среднем работает со скоростью O(log n), а в худшем O(n).<\/p>\n
Такие деревья еще называют не сбалансированными. Чтобы исправить ситуацию существуют специальные алгоритмы балансировки деревьев, которые приводят их в нормальный вид. Но рассматривать здесь я их не буду.<\/p>\n
Итог<\/h2>\n
Бинарный поиск один из самых простых и элегантных алгоритмов поиска, который привел к созданию новой структуры данных — бинарного дерева поиска. Данная структура является очень популярной и используется по многих системах. Особенно активно в базах данных для создания индексов и оптимизации выборки данных.<\/p>\n
Если тема интересная, то можно копнуть дальше и разобраться с:<\/p>\n
\n- Красно черными деревьями<\/li>\n
- Кучами<\/li>\n
- B-деревьями<\/li>\n
- и т. д.<\/li>\n<\/ul>\n
Бонус<\/h2>\n
На сайте https:\/\/idea-instructions.com<\/a><\/a> есть объяснения разных алгоритмов в стиле инструкций с икеи. Например AVL дерево<\/a><\/p>\n",
"date_published": "2022-06-11T14:00:56-04:00",
"date_modified": "2022-06-13T15:26:28-04:00",
"tags": [
"алгоритми та структури даних",
"програмування"
],
"image": "https:\/\/www.stefaniuk.website\/pictures\/binary-search-1.png",
"_date_published_rfc2822": "Sat, 11 Jun 2022 14:00:56 -0400",
"_rss_guid_is_permalink": "false",
"_rss_guid": "269",
"_e2_data": {
"is_favourite": false,
"links_required": [],
"og_images": [
"https:\/\/www.stefaniuk.website\/pictures\/binary-search-1.png",
"https:\/\/www.stefaniuk.website\/pictures\/binary-search-2.png",
"https:\/\/www.stefaniuk.website\/pictures\/binary-search-3.png",
"https:\/\/www.stefaniuk.website\/pictures\/binary-search-speed.png",
"https:\/\/www.stefaniuk.website\/pictures\/binary-search-tree-1.png",
"https:\/\/www.stefaniuk.website\/pictures\/binary-search-tree-2.png",
"https:\/\/www.stefaniuk.website\/pictures\/binary-search-tree-3.png"
]
}
},
{
"id": "265",
"url": "https:\/\/www.stefaniuk.website\/all\/transactions-and-acid\/",
"title": "Транзакции в базах данных и ACID",
"content_html": "Транзакции поддерживают все реляционные базы данных и некоторые NoSQL базы. Представляют они из себя простой набор команд, который должен быть выполнен как одно целое. В большинстве случает транзакция представляет некую бизнес операцию.<\/p>\n
Базы данных гарантируют что все запросы в рамках транзакции выполняться как одно целое или не выполняться вообще. Отталкиваясь от этой концепции был придуман набор требований к транзакциям и системам, которые их используют. Эти правила гарантируют надежную работу транзакций. Такой набор требований называется ACID.<\/p>\n
ACID гарантирует что данные в БД будут целостные независимо от любых сбоев.<\/p>\n
Всего есть четыре свойства у транзакций:<\/p>\n
\n- Atomicity (атомарность)<\/b> — команды внутри транзакции буду выполнены все вместе или ни одной. То есть транзакция это атомарная команда. Достигается это за счет системы откатов и журнала транзакций. Если внутри транзакции какой-то запрос выполнился с ошибкой, то все изменения, сделанные в рамках этой транзакции откатываются.<\/li>\n
- Сonsistency (консистентность)<\/b> — данные должны быть консистентными после выполнения транзакции. Это значит что в них нету логических и технических противоречий. Например: суммарный баланс счетов должен оставаться неизменным, это логическая целостность. Записи в таблицах не ссылаются на удаленные идентификаторы в другой таблице — техническая целостность.<\/li>\n
- Isolation (изолированность)<\/b> — транзакции зачастую обрабатываются параллельно, это значит что они не должны влиять друг на друга. Так если два человека одновременно пересылают деньги третьему, то одна транзакция может переписать данные другой и деньги потеряются. На практике изоляция достигается за счет уровней изоляции.<\/li>\n
- Durability (стойкость)<\/b> — если транзакция завершена успешно, то она не может быть отменена даже при авариях, внезапном отключении света в датацентре и проблем в сети. В этом случае база данных должна сама восстановить последние изменения.<\/li>\n<\/ul>\n
Отдельно стоит упомянуть уровни изоляции, потому что их понимание позволяет находить баги в коде, который работает с базой. Самих уровней существую большое множество, но рассмотрим четыре основных:<\/p>\n
\n- read uncommited<\/b> — позволяет избежать потерянных обновлений, когда две транзакции изменяют одни и те же данные. Для этого одна транзакция блокирует данные, которые хочет изменить для других UPDATE операций в других транзакциях.<\/li>\n
- read committed<\/b> — решает проблему грязного чтения, когда вычитываем данные во время их обновления. Это может привести к тому что мы получим частично обновленные данные. В таком случае UPDATE операции в транзакции блокируют UPDATE и SELECT операции в других транзакциях. Именно этот уровень изоляции используется по умолчанию в большинстве БД.<\/li>\n
- repeatable read<\/b> — внутри транзакции может быть несколько операций SELECT, которые читают одни и те же данные. Repeatable read гарантирует что это операции внутри одной транзакции будут возвращать одинаковые данные. Даже если другие транзакции хотят их удалить или изменить. В таком случает транзакция блокирует все строчки, которые затрагивают операции UPDATE и SELECT.<\/li>\n
- serializable<\/b> — исключает проблему «фантомных чтений», которые возникают при вставке новой строки между двумя операциями SELECT внутри одной транзакции. Больше всего эта проблема влияет на агрегационные запросы. Такой уровень изоляции является самым строгим, все транзакции выполняются так, будто других параллельных транзакций не существует.<\/li>\n<\/ul>\n",
"date_published": "2022-05-06T10:20:27-04:00",
"date_modified": "2022-04-30T10:27:31-04:00",
"tags": [
"бази даних",
"програмування"
],
"_date_published_rfc2822": "Fri, 06 May 2022 10:20:27 -0400",
"_rss_guid_is_permalink": "false",
"_rss_guid": "265",
"_e2_data": {
"is_favourite": false,
"links_required": [],
"og_images": []
}
},
{
"id": "266",
"url": "https:\/\/www.stefaniuk.website\/all\/folder-by-type-and-folder-by-feature\/",
"title": "Folder by Type и Folder by Feature",
"content_html": "
ASP.NET, как и большинство других фреймворков, предлагают использовать свою структуру организации файлов в проекте. Почти всегда используется folder by type подход. Он предполагает разделение файлов по типу. Так все контроллеры лежать в одной папке, вьюхи в другой и т. д.<\/p>\n
com.example\r\n├── Domain\r\n│ ├── User.cs\r\n│ └── Pet.cs\r\n├── Controllers\r\n│ ├── UserController.cs\r\n│ └── PetController.cs\r\n├── Repositories\r\n│ ├── UserRepository.cs\r\n│ └── PetRepository.cs\r\n├── Services\r\n│ ├── UserService.cs\r\n│ └── PetService.cs\r\n│ \/\/ and everything else in the project\r\n└── Startup.cs<\/code><\/pre>Такой подход неплохо работает на небольших проектах, когда файлов немного и фичи состоят из ограниченного количества классов. Проблемы возникают при росте проекта. Когда разрабатываешь большую фичу нужно постоянно держать в голове что в какой папке лежит, постоянно переключаясь между ними. Частично эту проблему решают IDE, но только частично.<\/p>\n
Альтернативой является folder by feature подход, при котором все файлы одной фичи лежат в отдельной папке. В таком случае все необходимое для конкретной фичи лежит под рукой и нет ничего лишнего.<\/p>\n
Это позволяет:<\/p>\n
\n- Упростить навигацию в проекте.<\/li>\n
- Построить высокоуровневую абстракцию — открываешь проект и сразу понятно что он из себя представляет, из чего состоит.<\/li>\n
- Выделить вертикальные слои.<\/li>\n<\/ul>\n
com.example\r\n├── Pet\r\n│ ├── Pet.cs\r\n│ ├── PetController.cs\r\n│ ├── PetRepository.cs\r\n│ └── PetService.cs\r\n├── User\r\n│ ├── User.cs\r\n│ ├── UserController.cs\r\n│ ├── UserRepository.cs\r\n│ └── UserService.cs\r\n│ \/\/ and everything else in the project\r\n└── Startup.cs<\/code><\/pre>Обычно проблемы возникают когда появляется общий код, который нужно использовать в нескольких частях приложения. Но, в принципе, это известная проблема и ее можно решить грамотной нарезкой на вертикальные слои. Вторая проблема достаточно банальная — привычки, большинство программистов привыкли к классической компоновки.<\/p>\n
Ссылки:
\nFolder-by-type or Folder-by-feature<\/a><\/p>\n",
"date_published": "2022-04-30T09:59:29-04:00",
"date_modified": "2022-05-01T11:15:12-04:00",
"tags": [
"код",
"програмування"
],
"_date_published_rfc2822": "Sat, 30 Apr 2022 09:59:29 -0400",
"_rss_guid_is_permalink": "false",
"_rss_guid": "266",
"_e2_data": {
"is_favourite": false,
"links_required": [
"system\/library\/highlight\/highlight.js",
"system\/library\/highlight\/highlight.css"
],
"og_images": []
}
},
{
"id": "267",
"url": "https:\/\/www.stefaniuk.website\/all\/links-24-04-2022\/",
"title": "Интересные статьи",
"content_html": "Решил вернуться к своему блогу после столь долгой паузы. Начну с небольшой подборки статей, которые я недавно прочитал и которые мне очень понравились.<\/p>\n
Choose Boring Technology<\/a> — статья-презентация от одного из первых разработчиков Etsy. Рассказывает про выбор технологий для проекта. Основная идея в том чтобы выбирать «скучные», а если быть точнее, то хорошо изученные и устоявшиеся технологии. Горячо советую почитать.<\/p>\nIntroduction to architecting systems for scale<\/a> — кратко о том из чего состоят приложения, которые рассчитаны для масштабирование.<\/p>\nCelebrate tiny learning milestones<\/a> — не совсем техническая статья. Вместо того чтобы придумывать себе большие цели на год, лучше придумать набор небольших целей «майлстоунов» и идти по ним.<\/p>\nGet your work recognized: write a brag document<\/a> — очень частая проблема это распознавание того что ты сделал на проекте. Когда приходит перформанс ревью, то бывает сложно вспомнить все что ты сделал за год. Автор советует завести документ в который нужно записывать результаты своей работы, а именно то, что было сделано и к чему это привело.<\/p>\nGood Logging<\/a> — коротко о том какими должны быть логи чтобы ими было удобно пользоваться. Ну и сразу еще две статьи от этого же автора: Great Programmers Write Debuggable Code<\/a> и Finding Bugs: Debugger versus Logging<\/a><\/p>\n",
"date_published": "2022-04-24T05:39:07-04:00",
"date_modified": "2023-06-02T20:18:58-04:00",
"tags": [
"system-design",
"лінки",
"програмування"
],
"_date_published_rfc2822": "Sun, 24 Apr 2022 05:39:07 -0400",
"_rss_guid_is_permalink": "false",
"_rss_guid": "267",
"_e2_data": {
"is_favourite": false,
"links_required": [],
"og_images": []
}
},
{
"id": "256",
"url": "https:\/\/www.stefaniuk.website\/all\/repository-pattern\/",
"title": "Паттерн «Репозиторий»",
"content_html": "Репозиторий один из самых популярных паттернов для доступа к данным. Он используется для абстрагирования от конкретной реализации и нюансов работы с источником данных, внешних сервисов, файловой системой и т. д.<\/p>\n
С одной стороны, это очень простой паттерн, который позволяет скрыть сложность работы с БД. Но с другой стороны, спросите 10 программистов описать этот шаблон и вы получите 10 разных реализаций.<\/p>\n
Самая большая проблема этого шаблона — множество вопросов, которые возникают при его реализации и дальнейшей поддержки.<\/p>\n
Изначально хотел сам расписать проблемы, но за меня это уже сделали, поэтому настоятельно советую прочитать статью: «Проблемы паттерна Репозиторий».<\/a><\/p>\nЕсли кратно, то:<\/p>\n
\n- Что делать если репозиториям нужно использовать закрытые методы друг друга?<\/li>\n
- Можно ли использовать один репозиторий на весь проект или делать репозиторий на каждую сущность?<\/li>\n
- Нужно ли дублировать методы репозитория в сервис или мы можем напрямую использовать репозиторий в контроллерах?<\/li>\n
- Нужно ли возвращать IQueryable и как это повлияет на дизайн системы в случае с .NET кодом? Если нет, то как правильно изменять сущности без использования Change Tracking?<\/li>\n
- Как правильно объединить репозиторий и UoW?<\/li>\n<\/ul>\n
Отдельно также хочу отметить доклад: Денис Цветцих «Repository и UnitOfWork в 2020 году, must have или антипаттерн?»<\/a>. В нем также поднимаются проблемы репозитория, способы их решения и варианты замены этот шаблона на другой.<\/p>\nРепозиторий — хороший паттерн, который должен быть в арсенале любого программиста, но стоит использовать его с умом и учитывать проблемы, которые он может вызвать.<\/p>\n
Для себя я решил что репозиторий хорошо подходит, когда вся логика приложения вписывается в CRUD модель. Но если логика более сложная или приложение подразумевает Task Base UI, тогда лучше прибегнуть к подходу CQRS. Он позволяет разбить сложную бизнес логику включая репозитории на независимые объекты, каждый из которых выполняет только одну бизнес задачу или use case.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/repository-pattern-orm-db.png\")
\n<\/div>\n<\/div>Я кроме все прочего не люблю репозитории за:<\/p>\n
\n- Ограничение функциональности ORM, большенство специфических операций недоступны. В зависимости от реализации можем потерять Change Tracking.<\/li>\n
- Дополнительный мапинг из доменных объектов в DTO.<\/li>\n
- Дополнительный слой абстракции, который зачастую просто не нужен. Особенно если речь идет о небольших сервисах где логику нужно делать максимально простой и незамысловатой.<\/li>\n
- Работает только в простых CRUD сценариях.<\/li>\n<\/ul>\n",
"date_published": "2021-07-08T08:50:13-04:00",
"date_modified": "2023-06-02T20:19:28-04:00",
"tags": [
"system-design",
"код",
"програмування"
],
"image": "https:\/\/www.stefaniuk.website\/pictures\/repository-pattern-orm-db.png",
"_date_published_rfc2822": "Thu, 08 Jul 2021 08:50:13 -0400",
"_rss_guid_is_permalink": "false",
"_rss_guid": "256",
"_e2_data": {
"is_favourite": true,
"links_required": [],
"og_images": [
"https:\/\/www.stefaniuk.website\/pictures\/repository-pattern-orm-db.png"
]
}
},
{
"id": "253",
"url": "https:\/\/www.stefaniuk.website\/all\/message-queues\/",
"title": "Очереди сообщений",
"content_html": "
При работе с большими системами, которые состоят из множества компонентов, возникает вопрос: «Как интегрировать несколько приложений для работы друг с другом?». Для этого нужен надёжный, асинхронный и быстрый способ передачи данных, который также позволит передавать информацию в разных форматах.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/queue-general.png\")
\n<\/div>\n<\/div>Все эти свойства есть в системе обмена сообщениями. Они полезны когда:<\/p>\n
\n- Нужно отправить данные из точки А в точку Б.<\/li>\n
- Нужно интегрировать несколько систем.<\/li>\n
- Нужно масштабирование.<\/li>\n
- Нужна возможность мониторить потоки данных.<\/li>\n
- Нужна асинхронная обработка.<\/li>\n
- Нужна буферизация.<\/li>\n<\/ul>\n
Концепт обмена сообщениями<\/h2>\n
Обмен сообщениями неновое изобретение. Он активно используется внутри операционной системы для обмена информацией между несколькими процессами (inter-process communication) и для обмена между несколькими потоками внутри процесса (inter-thread communication).<\/p>\n
Самый простой способ представить очередь сообщений как длинную трубу в которую можно помещать шарики. Мы можем написать сообщение на шаре и закинуть его в трубу и кто-то получит его на другой стороне. Из такой концепции можно понять несколько вещей.<\/p>\n
\n- Отправитель не имеет представления о том кто именно примет сообщение.<\/li>\n
- Отправитель не переживает о том когда его сообщение будет получено.<\/li>\n
- Отправитель может засовывать сколько угодно сообщений с удобной ему скорость.<\/li>\n
- Это не повлияет на получателя, ведь он сам решает сколько сообщений ему удобно доставать.<\/li>\n
- Ни отправитель, ни получатель не знают об устройстве друг друга.<\/li>\n
- Ни отправитель, ни получатель не переживают про нагрузку и вместительность друг друга.<\/li>\n
- Также они не знаю о том где каждый из них находиться. Они могут быть в одной комнате, в разных комнатах или зданиях.<\/li>\n<\/ul>\n
Все эти свойства позволяют разделить две системы с точки зрения ответственности, времени, пропускной способности, внутреннего устройства, нагрузки и географии. Само по себе разделение является очень важной частью большой распределенной системы. Чем больше независимых компонентов, тем проще их разрабатывать, тестировать и запускать независимо от других.<\/p>\n
Также очереди работают по модели «издатель-подписчик». В ней издатель оправляет сообщение в очередь, а подписчик смотрит в очередь и извлекает интересные ему сообщения, после чего занимается их обработкой. Благодаря этой концепции, осуществляется асинхронная коммуникация.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/queue-pub-sub.png\")
\n<\/div>\n<\/div>Причины использовать очереди сообщений<\/h2>\n
Избыточность и поддержка транзакций<\/b>
\nПеред тем как сообщение будет удалено может потребоваться подтверждение, что приложение, которое прочитало сообщение, успешно его обработало. В случае возникновения проблем, сообщение не потеряется, что позволит повторно его обработать.<\/p>\n
Масштабирование<\/b>
\nОчереди распределяют процессы обработки информации. Это дает возможность гибко реагировать на нагрузку и добавлять или убирать дополнительные обработчики.<\/p>\n
Эластичность<\/b>
\nОчереди сообщений позволяют выровнять нагрузку на приложение за счет буферизации данных. В случае большой нагрузки на систему очередь будет накапливать сообщения, а сами обработчики будут работать в нормальном режиме самым облегчая обработку данных и не допуская отказа системы.<\/p>\n
Отказоустойчивость<\/b>
\nВ случае отказа обработчиков, очередь продолжит сохранять все сообщения, что позволит обработать их когда система поднимется, тем самым не потеряв никаких данных.<\/p>\n
Decoupling and coupling<\/b>
\nС помощью очередей можно достичь двух противоположных целей.<\/p>\n\n- Decoupling. Если у нас большой монолит, то будет сложно интегрировать новые фичи. В таком случае очередь сообщений позволяет разъединить одно приложения на несколько независимых компонентов и настроить коммуникацию между ними.<\/li>\n
- Coupling. Иногда нужно, чтобы несколько систем работали как одно целое, очередь позволяют создать промежуточный слой для коммуникации между разными элементами системы.<\/li>\n<\/ul>\n
Понимание потоков данных<\/b>
\nПо сути, очереди накладывают ограничения на передачу данных между компонентами, что позволяет очень легко мониторить как обрабатываются данные. Благодаря этой информации можно понять как работает система и ее компоненты. Например, некоторые очереди могут простаивать, а некоторые всегда забиты, тем самым показывая где у нас есть проблемы с обработкой.<\/p>\nГарантированная доставка<\/h2>\n
Гарантированная доставка является одной из ключевых характеристик системы обмена сообщений. Всего есть три типа доставки:<\/p>\n
\n- at least once<\/li>\n
- at most once<\/li>\n
- exactly once<\/li>\n<\/ul>\n
At least once<\/b>
\nСамый простой способ доставки при котором обработчик получает одно и то же сообщение до тех пор, пока не удалит его из очереди или не подтвердит получение. Это значит что возможны ситуации, когда приложение обрабатывает одно сообщение несколько раз.<\/p>\n
Такая особенность подразумевает, что обработчик будет корректно работать в случае дублирования сообщений. А такое может случаться часто. Например, упала сеть в момент, когда приложение подтверждало получение — оно получит его ещё раз.<\/p>\n
Если в сообщениях хранятся результаты каких-то измерений, у которых есть временная метка, то ничего страшного не произойдёт, если мы получим хоть миллион дубликатов. Но если в сообщениях храниться информация о финансовых транзакциях то будет совсем не круто обработать его дважды. Но такую ситуацию можно решить используя уникальные идентификаторы для сообщений и хранить список сообщений, которые мы уже обработали.<\/p>\n
С другой стороны, такой подход гарантирует 100% получение сообщения. Даже если получатель сообщения упадёт, до того как подтвердит обработку, то он просто ещё раз его обработает после перезапуска.<\/p>\n
At most once<\/b>
\nОчень редкий сценарий, к нему прибегают когда двойная обработка сообщения может привести к серьезным проблемам. В таких очередях мы предпочтем потерять сообщение чем обработать его дважды.<\/p>\n
Если приложение упадет во время обработки сообщения, то мы его повторно не получим и оно будет считаться утерянным.<\/p>\n
Exactly Once<\/b>
\nИдеальный сценарий работы очереди, но проблема в том что его нереально воплотить в жизнь из-за множества проблема, которые сами по себе решить сложно, не говоря уже об их совокупности.<\/p>\n
Все они происходят из двух утверждений:<\/p>\n
\n- Отправители и получатели не идеальны<\/li>\n
- Сеть не идеальна.<\/li>\n<\/ul>\n
Что порождает такие проблемы как:<\/p>\n
\n- Отправитель может забыть отправить сообщение<\/li>\n
- Сеть между отправителем и очередью может упасть<\/li>\n
- Сеть между очередью и получателем может упасть<\/li>\n
- База данных самой очереди может не сохранить сообщение<\/li>\n
- Подтверждение что сообщение обработано может не дойти до очереди и отправителя<\/li>\n<\/ul>\n
Именно поэтому очень сложно гарантировать одноразовую доставку сообщения. Намного проще сделать систему устойчивой к дубликатам сообщений и использовать подход at-least-once.<\/p>\n
Компоненты очереди сообщений<\/h2>\n
Система обмена сообщениями состоит из нескольких компонентов, которые позволяют ей нормально функционировать и выполнять свои задачи.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/queue-components.png\")
\n<\/div>\n<\/div>Сообщения<\/b> — любые данные, которые нужно передать через очередь конвертируются в сообщение, которые состоят из двух частей:<\/p>\n\n- Заголовки (headers) — в них расположена служебная информация, которая используется самой очередью для правильной обработки сообщения.<\/li>\n
- Тело (body) — информация, которую мы передаем с помощью очереди.<\/li>\n<\/ul>\n
Каналы (channels)<\/b> — логические соединения между приложениями и системой очередей, которые предоставляют изолированную коммуникацию. Каналы позволяют передавать сообщение в одном из двух режимов:<\/p>\n\n- point-to-point — протокол, который обеспечивает прямую коммуникацию между двумя приложениями.<\/li>\n
- publish-subscribe — протокол, в котором отправитель сообщения не знает конкретного получателя, а просто отправляет сообщение в очередь, на которую могут быть подписаны потребители.<\/li>\n<\/ul>\n
Маршрутизатор (router)<\/b> — помещает сообщения из каналов по разным очередям используя ключ маршрутизации из заголовков сообщения.<\/p>\n
Очередь (queue)<\/b> — хранилище для наших сообщений, которое может находиться как в оперативной памяти так и на диске.<\/p>\nВиды очередей<\/h2>\n
Очереди сообщений можно разделить на несколько видов. Обычно несколько видом могут быть реализованы в одном продукте.<\/p>\n
broadcast (fanout) exchange<\/b>
\nВ таком случае отправляется копия сообщения во все доступные очереди, ключ маршрутизации игнорируется.<\/p>\n\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/queue-fanout-exchange.png\")
\n<\/div>\n<\/div>direct exchange<\/b>
\nВсе сообщения имеют свой ключ маршрутизации, который определяет в какую очередь нужно положить сообщение. В дальнейшем сообщения будут переданы по принципу Round Robin подписанным обработчикам. Это значит что только один обработчик получит сообщение.<\/p>\n\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/queue-direct-exchange.png\")
\n<\/div>\n<\/div>topic exchange (multicast)<\/b>
\nТакие очереди подписаны на получение сообщений чей ключ подпадает под определенный паттерн. Если ключ маршрутизации подходит для нескольких очередей, то каждая получит по своей копии.<\/p>\n
Обычно ключи маршрутизации стараются делать в иерархическом виде. Это достигается за счет разделения логических частей (слов) точками. Например вот так:<\/p>\n
[region].[availability-zone].[service].[instance]\r\n\r\neu-east.az1.computer.homepc<\/code><\/pre>Сами же паттерны создаются с использованием специальных символов:<\/p>\n
\n- * — заменитель только для одного слова.<\/li>\n
- # — заменитель для нескольких слов<\/li>\n<\/ul>\n
Что позволяет сделать такие шаблоны:<\/p>\n
\n- *.*.computer.* — очередь, которая может обработать сообщения только от компьютеров без разницы где они находятся.<\/li>\n
- eu-east.# — очередь, которая может обрабатывать сообщения только из зоны eu-east<\/li>\n<\/ul>\n\n
![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/queue-topic-exchange.png\")
\n<\/div>\n<\/div>Протоколы<\/h2>\n
Исторически сложилось так, что почти все существующие протоколы для работы с очередями были проприетарными. Это накладывало массу ограничений, потому что не все языки поддерживали тот или иной протокол.<\/p>\n
Спустя какое-то время появились три открытых стандарта, которые сейчас повсеместно используются:<\/p>\n
\n- Advanced Message Queuing Protocol (AMQP)<\/b> — бинарный протокол, который проектировался для взаимодействия между различными вендорами и стал заменой существующих проприетарных протоколов. Основными особенностями AMQP является надежности и совместимость.<\/li>\n
- Streaming Text Oriented Messaging Protocol (STOMP)<\/b> — простой текстовый протокол обмена сообщениями, который очень похож на HTTP и работает поверх TCP.<\/li>\n
- MQTT (formerly MQ Telemetry Transport)<\/b> — очень простой и легковесный протокол, который разрабатывался для минимального использования трафика и работы в нестабильной сети. Все эти качества идеально подошли для использования протокола для общения между устройствами.<\/li>\n<\/ul>\n
Материалы<\/h2>\n\n- Message queues<\/a> — отличная статья, которая описывает основные концепты работы очередей.<\/li>\n
- The Big Little Guide to Message Queues<\/a> — большой гайд в котором описано про причины создания очередей их свойства и особенности работы, а также кратный разбор самых популярных реализаций.<\/li>\n<\/ul>\n",
"date_published": "2021-05-18T02:17:40-04:00",
"date_modified": "2021-05-18T02:17:55-04:00",
"tags": [
"system-design",
"програмування"
],
"image": "https:\/\/www.stefaniuk.website\/pictures\/queue-general.png",
"_date_published_rfc2822": "Tue, 18 May 2021 02:17:40 -0400",
"_rss_guid_is_permalink": "false",
"_rss_guid": "253",
"_e2_data": {
"is_favourite": true,
"links_required": [
"system\/library\/highlight\/highlight.js",
"system\/library\/highlight\/highlight.css"
],
"og_images": [
"https:\/\/www.stefaniuk.website\/pictures\/queue-general.png",
"https:\/\/www.stefaniuk.website\/pictures\/queue-pub-sub.png",
"https:\/\/www.stefaniuk.website\/pictures\/queue-components.png",
"https:\/\/www.stefaniuk.website\/pictures\/queue-fanout-exchange.png",
"https:\/\/www.stefaniuk.website\/pictures\/queue-direct-exchange.png",
"https:\/\/www.stefaniuk.website\/pictures\/queue-topic-exchange.png"
]
}
},
{
"id": "252",
"url": "https:\/\/www.stefaniuk.website\/all\/collection-in-csharp\/",
"title": "Коллекции в C#",
"content_html": "
В C# для хранения набора однотипных данных можно использовать массивы. Но с ними не всегда удобно работать потому, что они имеют фиксированный размер и часто бывает сложно угадать, какого размера нужен массив.<\/p>\n
Для решения этих задач в C# есть коллекции. Они позволяют динамически изменять свой размер. Также они удобны тем что некоторые из них представляют из себя готовые реализации стандартных структур данных, таких как список, хеш таблица, стек, очередь.<\/p>\n
Все коллекции лежат в нескольких пространствах имен:<\/p>\n
\n- System.Collections — простые необобщенные коллекции.<\/li>\n
- System.Collections.Generic — обобщенные коллекции.<\/li>\n
- System.Collections.Specialized — специальные коллекции.<\/li>\n
- System.Collections.Concurrent — коллекции для работы в многопоточной среде.<\/li>\n<\/ul>\n
Устройство коллекций<\/h2>\n
Все коллекции, так или иначе, реализую интерфейс ICollection, некоторые реализуют интерфейсы IList и IDictionary (которые внутри наследуют ICollection). Этот интерфейс предоставляет минимальный набор методов, которые позволяют реализовать коллекцию.<\/p>\n
В свою очередь, ICollection расширяет интерфейс IEnumerable. Он предоставляет нумератор, который позволяет обходить коллекции элемент за элементом. Именно этот интерфейс позволяет использовать коллекции в цикле foreach.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/collections-interfaces.png\")
\n<\/div>\n<\/div>Вместительность коллекций<\/h2>\n
Одна из ключевых особенностей коллекций это изменяемый размер. Когда создается экземпляр коллекции она внутри себя инициализирует какую-то структуру данных, зачастую это массив. По умолчанию этот массив имеет определённую вместительность, которую можно просмотреть с помощью свойства Capacity.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/collections-capacity.png\")
\n<\/div>\n<\/div>После активного наполнения коллекции наступает момент, когда внутренний массив заполнен и мы не можем добавить новый элемент. В таком случае коллекция создаёт новый массив с большей вместительностью (обычно в два раза больше) и копирует туда данные со старого массива.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/collections-capacity-copy.png\")
\n<\/div>\n<\/div>Поэтому коллекции, которые основаны на массивах имеют сложность вставки:<\/p>\n
\n- O(1) — когда вместительности достаточно.<\/li>\n
- O(n) — когда вместительности недостаточно и нужно копировать данные в массив побольше.<\/li>\n<\/ul>\n
Чтобы избежать уменьшения производительности нужно при создании коллекции указать необходимую нам вместительности. Это позволит уменьшить количество копирований.<\/p>\n
Сравнивание и сортировка элементов коллекций<\/h2>\n
Сравнение<\/b>
\nТакие методы как Contains, IndexOf, LastIndexOf, and Remove используют сравнение элементов для свое работы. Если коллекция является обобщенной, то используются два механизма сравнения:<\/p>\n\n- Если тип реализует интерфейс IEquatable тогда механизм сравнения использует метод Equals этого интерфейса.<\/li>\n
- Если тип не реализует интерфейс IEquatable тогда для сравнения используется Object.Equals<\/li>\n<\/ul>\n
Некоторые коллекции имеют конструктор, который принимает имплементацию IEqualityComparer который используется для сравнения.<\/p>\nСортировка<\/b>
\nСортировка работает похожим образом, как и сравнение, но делиться на два вида: явную сортировку и сортировка по умолчанию.<\/p>\n
Сортировка по умолчанию подразумевает, что типы хранящиеся в коллекции реализуют интерфейс IComparable, чьи методы под капотом используют коллекции для сравнения.<\/p>\n
Явная сортировка подразумевает, что наши элементы не реализуют интерфейс IComparable, поэтому в качестве параметра метода сортировки нужно передать объект, который реализует интерфейс IComparer.<\/p>\n
Если тип не реализует интерфейс IComparable и мы не передали явно тип, который реализует IComparer, то при вызове метода сортировки вылетит исключение.<\/p>\n
System.InvalidOperationException: Failed to compare two elements in the array.\r\n\tSystem.ArgumentException: At least one object must implement IComparable.<\/code><\/pre>Алгоритмическая сложность коллекций<\/h2>\n
![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/collection-compexity-4.png\")
\n