負荷分散アルゴリズムの設計

[TodorokiKohei]

どのような負荷分散アルゴリズムを実装するかを考察する。

• [x] WEBサーバの負荷分散に関する論文調査
• [x] 候補となる負荷分散アルゴリズムを比較

[TodorokiKohei]

一般的な負荷分散方式について

負荷分散の方式には静的負荷分散と動的負荷分散がある。以下にそれぞれの特徴と具体的な実装を示す。 参考文献：負荷分散入門

静的負荷分散

あらかじめ定められたルールに従って配信先を選択する。

特徴

• すべてのサーバが同じ性能の場合に有効
• リクエストの処理時間が一定の場合に有効
• 実装が比較的容易

種類

• ラウンドロビン 順番に配信先を選択する。
• 静的な重み付きラウンドロビン 重みに従って順番に配信先を選択する。

動的負荷分散

サーバリソースなどをリアルタイムに監視しながら配信先を選択する。

特徴

• 各サーバの性能が異なる場合に有効
• リクエストごとに処理時間が異なる場合に有効
• 実装が複雑

種類

• 最小コネクション数 現在TCPコネクションが少ないサーバを優先的に選択する。
• 最小応答時間 レスポンスが早いサーバを優先的に選択する。
• 最小データ通信量 通信量が少ないサーバを優先的に選択する。
• 最小サーバ負荷 CPU負荷・メモリ使用率などのサーバリソースから配信先を選択する。

[TodorokiKohei]

一般的な動的負荷分散をより拡張した論文(読む候補)

以下の論文で挙げられていた論文が中心

• 「Web Server Performance Improvement Using Dynamic Load Balancing Techniques: A Review, Asian Journal of Research in Computer Science, Volume 10, Issue 1, Page 47-62, 22 June 2021」

• 「A State Of Art Survey For Web Server Performance Measurement And Load Balancing Mechanisms, International Journal of Scientific & Technology Research, Volume 8 - Issue 12, December 2019」

• [ ] 「A Client Proximity Based Load Balance Algorithm in Web Sever Cluster , WCNE 2017」 詳しいことは分からないけど、クライアントとサーバの近傍性(ネットワーク的な近さ？物理的な近さ？)を考慮した負荷分散アルゴリズムっぽい。MQTTのユースケースに近いのではないか？

• [ ] 「A Modified Round-Robin Load Balancing Algorithm Based on Content of Request, 2018 5th International Conference on Information Science and Control Engineering (ICISCE), 20-22 July 2018」 サーバの負荷とリソース性能(実行中の負荷とサーバの性能のこと？)、リクエストの種類を考慮した負荷分散アルゴリズム。リクエストの種類とかはUserPropertyを利用できないか？ただ、基本的にあるトピックに送信されるデータは全て同じと考えているので。。。

• [ ] 「Research and Realization of Nginx-based Dynamic Feedback Load Balancing Algorithm, 2018 IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), 12-14 October 2018」 動的フィードバックアルゴリズムをNginxのプラグイン機構を通して実装。どのようなフィードバックを受け取って処理しているのかが気になる。

• [ ] 「Response Time Based Balancing of Load in Web Server Clusters, 2018 7th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions) (ICRITO), 29-31 August 2018」 レスポンスの時間とサーバで保留中のジョブ数から動的に重み付けを行うアルゴリズムっぽい。これならMQTTのACKとPINGREQで実現可能な気がする。

• [ ] 「Research on web server cluster load balancing algorithm in web education system, The Journal of Supercomputing volume 76, pages3364–3373 (2020), 03 September 2018」 リクエストの影響度を分類し、対応する重み付けを行うアルゴリズム。UserPropertyと組み合わせるられないか？

• [ ] 「Request Distribution for Heterogeneous Database Server Clusters with Processing Time Estimation, 2018 IEEE 16th International Conference on Industrial Informatics (INDIN), 18-20 July 2018」 リクエストの処理時間を機械学習により推定し、リクエストの内容とサーバ特性(性能の高さやコストとか？)がマッチするように分散するアルゴリズム。日本の人が書いたものなので、日本語で近い内容を発表してくれていると嬉しい。

• [ ] 「Research on Nginx Dynamic Load Balancing Algorithm, 2020 12th International Conference on Measuring Technology and Mechatronics Automation (ICMTMA), 28-29 February 2020」 Nginxにリアルタイムのサーバ負荷情報を収集し、動的加重ラウンドロビンアルゴリズムを実装している。

[TodorokiKohei]

「Response Time Based Balancing of Load in Web Server Clusters」で紹介されていた配信先のキュー内にある未処理のメッセージ数を追跡した分散配信手法がMQTTに適していると考えた。

SubscrberはPINGREQに"未処理のキュー内のメッセージ数"と"1メッセージあたりの処理時間"をJSONに格納してBrokerに送信する。Brokerはこの情報を管理し、配信時に最も未処理のメッセージ数が少ないSubscriberにメッセージを配信し、未処理のメッセージ数をインクリメントする。未処理のメッセージ数が同じ場合はメッセージ処理時間が早いものを優先的に採用する。

{
  “msgsInQueue”: x,
  “processsingTimePerMsg”: y
}