Akamai Diversity
Home > September 2016

September 2016 Archives

IoT 時代に求められるネットワーク要件

Internet of Things は新しい概念ではないと思っている方は多いでしょう。私もその一人です。ただし、周りの環境の変化を考慮すると違った見方ができるのではないでしょうか。特にクラウド基盤を安価に使えるようになったことや、アプリを提供するプラットフォームを容易に利用できるようになったことは IoT の可能性を高めています。IoT ではデバイスがサーバに接続するようなケースが想定されますが、送信されたデータを加工して付加価値として提供することに意味があると個人的に思っています。

IoT_network_01_01.gif

今回ご紹介する"Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web"(一貫したハッシングとランダムなツリー: ワールド・ワイド・ウェブでのホットスポットを緩和するための分散キャッシングプロトコル)は、アカマイの提供するCacheについて説明した初期の文献です。

内容は、アクセスが集中するインターネットのサーバの負荷軽減を分散したCacheを利用して解決するということです。ここにアカマイの超分散型アーキテクチャを通じてコンテンツを配信するのに必要なアルゴリズムの原点が記述されています。

本文を読む上で、木(閉路を持たない複数の枝をもつ)による表現と、検索について、ハッシュ法(ここでは、Consistent Hasingと呼んでいます。)の知識があると理解しやすいです。

木については、例として2分木(本文ではN分木です。)を紹介します。木は、節点とそれらを結ぶ枝から構成されています。木には根と呼ばれる特別な節点が一つだけあり、通常、一番上に描かれています。根に近い節点を親節点、親節点で根から遠い節点を子節点と呼びます。2分木なので子節点はちょうど2つ存在します。節点から根までの距離をレベルと呼びます。任意の節点以下の節全体も木となり、これを部分木と呼びます。
2分木の続きとして、ヒープを説明します。
ヒープ:
(1) 根の節点の番号は1とします。
(2) ある節点の番号がiならば、その節点の2つの子節点は2*iと2*i+1とします。
(3) 親の節点は子の節点より大きなデータを持つとします。
ヒープにデータを追加してする操作と最大の要素を取り出す要素の実行時間は、O(logn)となります。

ハッシュ法は、任意に与えられた数に最も近い要素を集合の中から選ぶ問題に適用可能です。任意の数が集合に含まれるかどうかだけが知りたい場合には、ハッシュ法が平均的には最も効率が良いと考えられます。
ハッシュ法では、n個のデータを蓄えるのにその1.5〜2倍のサイズmを持つ配列を用います。ハッシュ法では、データを配列のなかに切り刻んで蓄えます。データxを蓄える場所を決めるために、実数値xを0からm−1までの整数値に変換する関数hash(x)を定めます。関数hash(x)を用いてn個のデータをサイズmの配列に蓄えます。ここでは、正の数のみを考えることにし、0.0というデータは存在しないと仮定します。いろいろなハッシュ関数を考えることができます。

このような木とハッシュ関数の概念によって本文の理解が進むと思います。

興味のある方は、こちらから御覧ください。

https://www.akamai.com/jp/ja/multimedia/documents/technical-publication/consistent-hashing-and-random-trees-distributed-caching-protocols-for-relieving-hot-spots-on-the-world-wide-web-technical-publication.pdf

アカマイでは、他にも様々な基本技術についても「技術関連出版物」(https://www.akamai.com/jp/ja/our-thinking/technical-publications.jsp)でご紹介しています。

(参考)
(1)「計算幾何学」(第2刷)、1992年、浅野哲夫、朝倉書店、ISBN4-254-11053-7 C 3041