DEIM Forum 2023 2a-8-2

データストリーム処理における近似的耐障害性保証のためのパーティショニング手法
高尾大樹†

杉浦 健人†

石川 佳治†

陸可鏡†† 東海国立大学機構名古屋大学大学院情報学研究科 〒 464–8603 愛知県名古屋市千種区不老町
Email: {takao, lu}@db.is.i.nagoya-u.ac.jp, {sugiura, ishikawa}@i.nagoya-u.ac.jp
あらましエッジコンピューティング環境を想定したデータストリーム処理の耐障害性保証のアプローチとして，近似的な耐障害性保証に基づく手法がある．この手法は障害により損失したデータを後段の機器で近似的に復元することで，障害機器の復旧を待たずに処理を継続できるが，割当センサ数が増加したときの処理性能と復元精度の両立に課題がある．そこで本稿では，復元精度と計算コストのトレードオフを考慮したパーティション制御手法を提案する．
本手法では近似的な耐障害性保証における誤差保証の枠組みを活用することで，ユーザ要求を満たして全てのセンサの処理結果を復元できる範囲で計算コストを最小化するようパーティション分割を動的に制御する．
キーワード データストリーム処理，エッジコンピューティング，耐障害性，近似処理，並列処理．
センサ

1 はじめに

𝑋𝐴

エッジ
1

𝑋𝐵

Raspberry Pi を始めとする安価なマイクロコンピュータの普𝑋𝐶及により，Internet of Things（IoT）およびそれらを活用するた

𝑋𝐷

めのエッジコンピューティングに注目が集まっている．エッジ

𝑋𝐸

コンピューティングではデータ通信量の削減や処理の負荷分散

𝑋𝐹のため，集約やフィルタリングなどの簡単なデータ処理をネッ

2

3

処理結果

欠損

ゲートウェイ

本研究の焦点スレッド
𝑨1𝑡 = 𝑋𝐴 , 𝑋𝐶 , 𝑋𝐸
𝑨𝑡2 = 𝑋𝐵 , 𝑋𝐷 , 𝑋𝐹

処理性能と復元精度を両立する
パーティション制御

問合せ・割当情報遷移モデル

障害により損失した
𝑋𝐸 , 𝑋𝐹 の処理結果を近似的に復元して出力

図 1 近似的な耐障害性保証の概要

トワークエッジで行う [1]．例えばスマートシティでの環境セン
シングであれば，各区画や建物内に設置された環境センサが無リーニングをすることなく直接分析処理などを行える．

線通信により送信した計測値を，各エッジが一定時間ごとに集しかしこの手法には処理性能と復元精度の両立に課題がある．

約することで後段のアプリケーションとの通信量を削減できる．

物理的な制約により割当センサ数に上限があるエッジとは異なしかし大量の安価なマシンを使用するエッジコンピューティン

り，全エッジの出力を受け取るゲートウェイではシステム規模

グ環境（以下，エッジ環境と略す）ではその物理的な制約の強の拡大に伴い処理対象のデータ数が増加する．特に欠損データさから余剰リソースの集中的な管理が難しく，故障機器を人手の復元に必要な行列演算のコストが大きいため，大量のデータで修理ないし交換しないと処理を継続できないという問題があを高速に処理するためには並列処理が必要になる．しかし，並る．エッジ環境において現実世界の変化に追従したサービスを列処理により各スレッドが復元に使用できるデータ量が減少す

継続して提供するためには，故障機器の復旧を待たずとも処理ることで，復元精度低下の恐れがある．以上より大規模環境へを継続できるような耐障害性保証のアプローチが求められる．

の適用のためには，全てのセンサの処理結果をユーザ要求を満

このエッジ環境における耐障害性の問題に対して，近似的たして復元できる範囲で計算コストを最小化するようなパーな耐障害性保証に基づく手法 [2, 3] がある．この手法はセンサ

ティショニングが求められる．

データ処理において必ずしも誤差のない結果が必要ではない点

そこで本稿では，復元精度と処理性能のトレードオフを考慮に注目し，クラウド環境を想定した従来手法 [4–7] とは異なりしたパーティショニング手法を提案する．本手法は大きく計算近似処理を積極的に活用して障害に対処する．システム中のあコストを最小化する初期割当の決定，および障害発生状況に応る機器に障害が発生したとき，時間的な相関およびセンサ間のじた動的な割当制御から構成される．パーティションを何度も相関を活用し，障害による損失データをその後段の機器で近似大幅に変更すると，データの再送・再処理コストが大きくなり，的に復元する．例えば図 1 においてエッジ 3 の障害によりセン処理性能が大きく低下してしまう．そこで本手法は，初期割当

サ 𝑋𝐸 , 𝑋𝐹 の処理結果を損失したとき，後段のゲートウェイでの段階から障害発生時の割当変更が最小限で済むよう調整する

他の処理結果から近似的に復元する．故障機器の復旧に時間がとともに，障害発生時に追加すべきセンサも高速に決定するこ

かかるエッジ環境下において，障害機器の復旧を待つことなくとで割当変更コストを最小限に抑えるよう工夫する．

高精度な近似処理結果を欠けることなくリアルタイムに提供で本手法はヒューリスティックスを活用して，復元精度が高くきるため，クラウドなど後段のアプリケーションではデータクなるようセンサの初期割当を決定する．環境センシングなどのあることに注目し，復元精度の近似的な評価関数を設計する．
そしてこの関数に基づいてセンサを重複なく各スレッドに均等結果を取得できたセンサ集合
𝑶𝑡

𝒁𝑡𝑖

𝑶𝑡𝑖

…

結果を損失したセンサ集合
𝒁𝑡
𝑨𝑡𝑖

…

ど同じエッジに割り当てられやすくかつ相関も強くなる傾向に

センサ割当

アプリケーションでは一般的に，物理的に近い位置のセンサほに配分することで，障害が発生していないときの計算コストを

センサ集合𝑿最小化するとともに，復元精度も高く維持できる．例えば図 1

図 2 センサ集合を表す記号の関係性

では，スレッド 1 にセンサ 𝑋 𝐴, 𝑋𝐶 , 𝑋𝐸 を，スレッド 2 にセン
サ 𝑋 𝐵 , 𝑋𝐷 , 𝑋𝐹 をそれぞれ割り当てる．このとき任意エッジの障害に対して各スレッドは 1 つのセンサの結果を残りの 2 つの2 準備

センサの結果から復元できるため，1 つのセンサの結果のみか

本章では議論の準備として，エッジ環境を想定した近似的なら復元するよりも精度が向上する．よってユーザ指定の誤差要

耐障害性保証に基づくデータストリーム処理システム [2,3] につ

求を満たす確率も高くなるため，障害発生時の割当変更を最小いて説明する．本システムは，環境センシングのような物理的限に抑えられるといえる．

に固定されたセンサから無線通信により計測値を定期的に取得

また本手法は，近似的復元における誤差保証の枠組みを活用できる環境への適用を想定する．各エッジは割当センサから得することで，障害状況に応じて効率的にセンサ割当を制御する．

られた計測値系列を時間窓で集約するなどの簡単なデータ処理

事前準備として，ユーザ要求の充足という観点から割当センサ

により，後段のアプリケーションで処理しやすい形にクリーニの優先度を計算し，各エッジに障害が発生したとき各スレッドングする．そして，ゲートウェイサーバや更に後段のクラウドへ最低限追加すべきセンサを求めておく．そして事前計算したサーバでは各エッジの処理結果に基づいて，データ分析やモニ情報に基づいて，各時刻の障害状況に対してユーザ要求を満た

タリング，シミュレーションなどの様々なサービスを提供する．

すために必要最小限のセンサを追加する．例えば図 1 において本システムはエッジ環境の障害によるダウンタイムの長期化

エッジ 3 の障害によりセンサ 𝑋𝐸 , 𝑋𝐹 の処理結果を損失したと
き，スレッド 2 はユーザ要求を満たして 𝑋𝐹 の結果を復元できるが，スレッド 1 は 𝑋𝐸 の結果を十分な精度で復元できないとする．このとき，事前に計算した情報を参考にスレッド 1 へセ
ンサ 𝑋𝐷 を追加で割り当てることで，センサ 𝑋𝐸 の結果もユー
ザ要求を満たして復元する．
本研究の貢献は以下のとおりである．

•の課題に対して，処理結果にある程度の誤差を許容する代わりに，低遅延性と可用性を高い水準に保つ．時間的な相関およびセンサ間の相関を活用し，前段機器の障害による損失データをその後段の機器で近似的に復元することで，障害機器の復旧を待たずに高精度な近似処理結果を欠けることなくリアルタイムに提供する．先行研究では誤差保証の仕組みを考慮したウォー
タマーク制御 [2] や各エッジの近似処理による不確実性の考

損失データの復元処理を並列化する際の計算コストの評慮 [3] などの様々な性能改善の工夫がある．しかし本章では議価関数を設計し，近似的な耐障害性保証における処理性能と復論の単純化のため，エッジ障害のみを想定したゲートウェイで元精度を両立する理想的なパーティショニングを定式化する．

の近似的な復元処理に焦点を当てて，処理手順の詳細と理論的•センサの初期割当を決定するパーティショニングアルゴ

な誤差保証について説明する．

リズムを提案する．センサ間の相関および各エッジへのセンサ

時刻 𝑡 ∈ N+ における 𝑛 台のセンサ 𝑿 = {𝑋1 , 𝑋2 , . . . , 𝑋𝑛 } の割当を考慮することで，復元精度と計算コストの両観点から適処理結果の真値を 𝒙 𝑡 = ⟨𝑥 1𝑡 , 𝑥 2𝑡 , . . . , 𝑥 𝑛𝑡 ⟩ と表す．ゲートウェイでしたセンサ割当を決定する．

•

は，時刻 𝑡 において障害の発生しているエッジに割り当てられ障害状況に応じたセンサ割当制御手法を提案する．理論

たセンサ 𝒁 𝑡 ⊆ 𝑿 の処理結果は全て損失し，センサ 𝑶 𝑡 = 𝑿 \ 𝒁 𝑡

的な誤差保証の枠組みを活用し割当センサの優先度を事前計算の処理結果として 𝒐 𝑡 が得られるとする．ここで時刻 𝑡 におけるすることで，任意の障害状況に対してユーザ要求を満たすためスレッド 𝑖 のセンサ割当を 𝑨𝑖𝑡 ⊆ 𝑿 とするとき，スレッド 𝑖 ではのセンサ割当を効率的に決定する．

•

処理遅延と復元精度に注目して提案手法の性能を実験により評価する．
本稿の構成は以下の通りである．2 章では議論の準備として，
エッジ環境を想定したデータストリーム処理の近似的な耐障害性保証について説明する．3 章では本研究における理想的なパーティショニングについて定式化する．そして 4 章では計算

𝑶 𝑖𝑡 = 𝑶 𝑡 ∩ 𝑨𝑖𝑡 の処理結果から 𝒁𝑖𝑡 = 𝒁 𝑡 ∩ 𝑨𝑖𝑡 の処理結果を近似的に復元する．これらセンサ集合を表す記号の関係性を図 2 に整理する．例えば図 1 ではエッジ 3 の故障により 𝒁 𝑡 = {𝑋𝐸 , 𝑋𝐹 }の処理結果を損失するため，𝑶 𝑡 = {𝑋 𝐴, 𝑋 𝐵 , 𝑋𝐶 , 𝑋𝐷 } の処理結果のみが得られる．このとき 𝑨1𝑡 = {𝑋 𝐴, 𝑋𝐶 , 𝑋𝐸 } のセンサが割り当てられているスレッド 1 では，𝑶 1𝑡 = {𝑋 𝐴, 𝑋𝐶 } の処理結果

から 𝒁1𝑡 = {𝑋𝐸 } の処理結果を近似的に復元する．なお，本章でコストを最小化する初期割当のアルゴリズム，および障害状況は各スレッドへのセンサ割当は既に与えられているものとし，に応じた動的な割当制御手法についてそれぞれ説明する．5 章

具体的なパーティショニングアルゴリズムは 4 章で述べる．

では評価実験について述べ，6 章で関連研究について概説する．
最後に，本研究のまとめと今後の課題を 7 章で述べる．

エッジ障害によるデータ損失の問題に対して，センサ間に存在する相関関係および時間的な相関を活用し，得られた一部の処理結果から欠損値を確率分布の形で復元する．本稿では，センサ 𝑿 間の相関関係を多変量正規分布 N ( 𝝁, Σ) によりモデル化する．ここで， 𝝁 と Σ はそれぞれ全センサの処理結果の期待値ベクトルと分散共分散行列を表す．また時間的な相関に関する議論の単純化のため，本稿ではマルコフ性を仮定する．すな
わち，時刻 𝑡 + 1 の各センサの処理結果 𝑿 𝑡+1 は時刻 𝑡 の処理結果 𝑿 𝑡 のみに依存し，その相関関係は遷移モデル 𝑝( 𝑿 𝑡+1 | 𝑿 𝑡 )として表現できるとする．
以上の想定のもと，ゲートウェイでは次の手順を反復的に繰り返すことで各センサの処理結果を近似的に計算する．
（ 1 ） 時刻 𝑡 で受け取った一部のセンサの処理結果を用いて，事前確率分布から全センサの処理結果の事後確率分布を計算する．
（ 2 ） 遷移モデルおよび時刻 𝑡 の事後確率分布から次の時刻

𝑡 + 1 における事前確率分布を計算する．

ある誤差上限 𝑒 を用いて以下のように求められる．
∫ 𝜇𝑋 +𝑒
𝑃 (𝑋 ∈ [𝜇 𝑋 − 𝑒, 𝜇 𝑋 + 𝑒]) =𝑝 (𝑋 = 𝑥) 𝑑𝑥
𝜇𝑋 −𝑒

(6)

ここで， 𝑝(𝑋) は正規分布 N (𝜇 𝑋 , Σ𝑋 ) に対する確率密度関数を表す．式 (6) より，ユーザ要求として要求信頼度 𝛿 が与えられたとき，𝑃(𝑋 ∈ [𝜇 𝑋 − 𝑒 ′ , 𝜇 𝑋 + 𝑒 ′ ]) = 𝛿 を解くことで，要求信頼度 𝛿 を満たす最小の復元誤差 𝑒 ′ を計算できる．このとき，𝛿 の確率で 𝑋 の真値が 𝜇 𝑋 ± 𝑒 ′ 以内に存在することを保証する．ただし，Σ𝑋 = 0 のときは処理結果の真値が得られているため，常に 𝑒 ′ = 0 であり復元結果に誤差は含まれない．

3 問題定義本章では，2 章で述べた近似的な耐障害性保証に基づくデー

以降では各処理の具体的な計算方法について述べる．

タストリーム処理システムにおける理想的なパーティショニン

時刻 𝑡 での事前確率分布として正規分布 N ( 𝝁, Σ) が与えられグを定式化する．式 (5) などの欠損データの復元に必要な行列たとき，時刻 𝑡 でスレッド 𝑖 が受け取ったセンサ 𝑶 𝑖𝑡 の処理結果

演算のコストが大きいため並列処理により処理性能を向上させ

𝒐 𝑖𝑡 からセンサ 𝒁𝑖𝑡 の事後確率を表す正規分布 N ( 𝝁 𝒁 𝑡 |𝒐 𝑡 , Σ𝒁 𝑡 |𝒐 𝑡 )𝑖 𝑖𝑖 𝑖

たいが，各スレッドで復元に使用できるデータ量減少による復は次のとおり求められる [8]．

元精度低下の恐れがある．この処理性能と復元精度のトレード(−1𝑡
𝝁 𝒁 𝑡 |𝒐 𝑡 = 𝝁 𝒁 𝑡 + Σ𝒁 𝑡 𝑶𝑡 Σ𝑶𝑡 𝑡 𝒐 𝑖 − 𝝁𝑶𝑡
𝑖 𝑖
𝑖
𝑖 𝑖
𝑖
𝑖 𝑶𝑖

)

オフに対して本稿では，全てのセンサの処理結果をユーザ要求(1)−1
Σ𝒁 𝑡 |𝒐 𝑡 = Σ𝒁 𝑡 𝒁 𝑡 − Σ𝒁 𝑡 𝑶𝑡 Σ𝑶
𝑡 𝑡 Σ𝑶𝑡 𝒁 𝑡
𝑖 𝑖
𝑖 𝑖
𝑖 𝑖
𝑖 𝑖
𝑖 𝑶𝑖

(2)

る次元を抽出したことを示す．例えば， 𝝁 𝒁 𝑡 は 𝒁𝑖𝑡 に対応する𝑖次元の値を期待値ベクトル 𝝁 から抽出したもの（ 𝒁𝑖𝑡 の期待値ベクトル）であり，Σ𝒁 𝑡 𝑶𝑡 は分散共分散行列 Σ の 𝒁𝑖𝑡 に対応す𝑖る行から 𝑶 𝑖𝑡 に対応する列を抽出したもの（ 𝒁𝑖𝑡 と 𝑶 𝑖𝑡 の共分散を表すブロック行列）である．また，時刻 𝑡 における 𝑨𝑖𝑡 の事
後確率分布として N ( 𝝁𝑨𝑡𝑖 |𝒐𝑖𝑡,Σ𝑨𝑡𝑖 |𝒐𝑖𝑡

当を理想的なパーティショニングとみなす．
理想的なパーティショニングを定式化するため，はじめにユー

ここで，各記号の添字はベクトルないし行列から添字に対応す𝑖を満たして復元できる範囲で計算コストを最小化するセンサ割) が得られる．ただし，セザ要求の充足条件を整理する．ただし，全 𝑚 個のエッジに対するセンサ割当 X = { 𝑿1 , 𝑿2 , . . . , 𝑿𝑚 }，および時刻 𝑡 の事前確率分布の分散共分散行列 Σ は既知であるとする．時刻 𝑡 のエッジ障害によりセンサ 𝒁 𝑡 ⊆ 𝑿 の処理結果を損失するとき，スレッ
ド 𝑖 ではセンサ 𝑋 ∈ 𝑨𝑖𝑡 ∩ 𝒁 𝑡 の復元にセンサ 𝑶 𝑖𝑡 = 𝑨𝑖𝑡 \ 𝒁 𝑡 が使用でき，次式のとおり復元結果の分散 𝜎𝑋 ( 𝑨𝑖𝑡 ) を求められる．
−1
𝜎𝑋 ( 𝑨𝑖𝑡 ) = Σ𝑋𝑋 − Σ𝑋𝑶𝑡 Σ𝑶
𝑡 𝑶𝑡 Σ𝑶𝑡 𝑋

ンサ 𝑶 𝑖𝑡 に対応する期待値は 𝒐 𝑖𝑡 であり，分散は全て 0 となる．
時刻 𝑡 + 1 における事前確率分布は，遷移モデルおよび時刻 𝑡
での事後確率分布を用いて次のとおり求める．

=(3)

特に時刻 𝑡 + 1 および 𝑡 の処理結果の同時確率分布 𝑝( 𝑿 𝑡+1 , 𝑿 𝑡 )が N ( 𝝁 ′′ , Σ ′′ ) として表せるとき，式 (3) を計算することで時刻

𝑡 + 1 の事前確率として次の正規分布 N ( 𝝁 𝑨𝑡+1 |𝒐 𝑡 , Σ 𝑨𝑡+1 |𝒐 𝑡 ) が得
𝑖

𝑖

𝑖

𝑖

られる [3]．

(𝝁 𝑨𝑡 |𝒐 𝑡 − 𝝁 ′′
𝐴
𝑖 𝑖

𝑖

𝑖

(7)

ここで 𝜎𝑋 ( 𝑨𝑖𝑡 ) は実際に得られる処理結果の値に依存しないた) −1 ′′( ′′ ) −1(
Σ 𝑨𝑡 |𝒐 𝑡 Σ′′
Σ𝐵 𝐴
+ Σ′′
𝐵𝐵
𝐴𝐵 Σ 𝐵𝐵𝑖

𝑖

要求信頼度 𝛿 および許容誤差 𝜖 を満たすために必要な分散の閾
値 𝜎𝜃 も事前計算できる．以上より，任意のセンサ 𝑋 に対して𝜎𝑋 ( 𝑨𝑖𝑡 ) <= 𝜎𝜃 となるようなセンサ割当を決定できれば，ユーザ要求を満たして損失データを復元できるといえる．
1
次に各スレッドの計算コストの評価関数を設計する．スレッ
ド 𝑖 は 2 章で述べたとおり，式 (1), (2) の損失データの復元と式 (4), (5) の遷移モデルの更新を毎時刻繰り返す．ここで時刻)(4)𝑡 の割当センサ数を | 𝑨𝑖𝑡 | と表すとき，データを受け取ったセン
サ数 |𝑶 𝑖𝑡 | および復元対象のセンサ数 | 𝒁𝑖𝑡 | はそれぞれ | 𝑨𝑖𝑡 | 以下′′ ( ′′ ) −1 ′′Σ 𝑨𝑡+1 |𝒐 𝑡 =Σ ′′Σ 𝐵𝐴
𝐴𝐴 − Σ 𝐴𝐵 Σ 𝐵𝐵𝑖𝑖する．また 2 章で述べたとおり，ユーザ要求として与えられた

𝑝( 𝑨𝑖𝑡+1 | 𝑨𝑖𝑡 = 𝒙) 𝑝( 𝑨𝑖𝑡 = 𝒙 | 𝒐1𝑖 , · · · , 𝒐𝑖𝑡 )𝑑𝒙( ′′ ) −1
𝝁 𝑨𝑡+1 |𝒐 𝑡 =𝝁 ′′
+ Σ′′
Σ 𝐵𝐵
𝐴
𝐴𝐵
𝑖
𝑖

𝑖

め，復元で使用するセンサが分かれば事前計算できる点に注意

𝑝( 𝑨𝑖𝑡+1 | 𝒐1𝑖 , · · · , 𝒐𝑖𝑡 )∫𝑖であるため， | 𝑨𝑖𝑡 | × | 𝑨𝑖𝑡 | 行列の計算コストでスレッド 𝑖 での最(5)

ただし，𝝁 ′′ および Σ ′′ の添字について 𝐴 は 𝑨𝑖𝑡+1 に対応する次

元を， 𝐵 は 𝑨𝑖𝑡 に対応する次元をそれぞれ抽出することを示す．
処理結果を確率分布として計算することで，誤差上限を理論的に保証できる．センサ 𝑋 ∈ 𝑿 の処理結果が 𝜇 𝑋 である確率は

悪計算量を見積もれる． | 𝑨𝑖𝑡 | × | 𝑨𝑖𝑡 | 行列の 𝐴, 𝐵 に対して逆行
列 𝐴 −1 と行列積 𝐴𝐵 の計算には共に 2| 𝑨𝑖𝑡 | 3 ステップ必要であ
1：ユーザ要求を満たせない場合のシステムの挙動として，満たせないまま近似的復元を続けるか処理自体を止めるかを決める必要はあるが，本稿では議論の対象外とする．

る [9] ことから，スレッド 𝑖 の計算量を 𝑂 (| 𝑨𝑖𝑡 | 3 ) と見積る．以Input: センサ集合 𝑿 ，各エッジへのセンサ割当 X ，上より，計算コストの評価関数 𝑓𝑐𝑜𝑠𝑡 を次のとおり定義する．

( )𝑓𝑐𝑜𝑠𝑡 𝑨𝑖𝑡 = | 𝑨𝑖𝑡 | 3

モデルの分散共分散行列 Σ，スレッド数 𝑁

Output: 各スレッドへのセンサ初期割当 A 0(8)以上を踏まえて本システムにおける時刻 𝑡 の理想的なパー/* 起点とするセンサを各スレッドへ割り当て
1
2

𝑋𝑚𝑎𝑥 ← arg max Σ𝑋𝑋

3

𝑨0𝑖 ← {𝑋𝑚𝑎𝑥 }4

𝑿 ← 𝑿 \ {𝑋𝑚𝑎𝑥 }𝑋∈ 𝑿

ティショニングを，次の最適化問題を解くことで得られるセン
サ割当 A 𝑡 = { 𝑨1𝑡 , 𝑨2𝑡 , . . . , 𝑨𝑡𝑚 } と定義する．

∑

minimizeA𝑡

𝑨𝑡𝑖 ∈ A 𝑡

( )𝑓𝑐𝑜𝑠𝑡 𝑨𝑖𝑡/* 評価関数に基づいて残りのセンサを各スレッドへ割り当て */5∀𝑨𝑖𝑡 ∈ A 𝑡 , ∀𝑋 ∈ 𝑨𝑖𝑡 , 𝜎𝑋 ( 𝑨𝑖𝑡 ) <= 𝜎𝜃subject to*/for 𝑖 = 1 to 𝑁 do

(9)6while 𝑿 ≠ 𝜙 dofor 𝑖 = 1 to 𝑁 do

7

𝑋𝑚𝑎𝑥 ← arg max 𝑓 𝑎𝑐𝑐 ( 𝑨0𝑖 ∪ {𝑋} | X, Σ)

8

𝑨0𝑖 ← 𝑨0𝑖 ∪ {𝑋𝑚𝑎𝑥 }9

𝑿 ← 𝑿 \ {𝑋𝑚𝑎𝑥 }𝑋∈ 𝑿∀𝑋 ∈ 𝑿, ∃ 𝑨𝑖𝑡 ∈ A 𝑡 , 𝑋 ∈ 𝑨𝑖𝑡
つまり各時刻において，各センサを少なくとも 1 つのスレッドに割り当て，かつユーザの誤差要求を満たす範囲で計算コスト

図 3 センサの初期割当を決定するアルゴリズム

を最小化するようなパーティショニングを求めたい．
上述の評価関数に基づく貪欲的なパーティショニングアルゴ

4 提案手法

リズムを図 3 に示す．本アルゴリズムは大きく 2 つのステップ

上述の最適化問題の厳密解を毎時刻求めるのは計算コストのから構成される．最初のステップでは，各スレッドに対して起観点から現実的でないため，本章では処理性能と復元精度の両点となるセンサを 1 つずつ割り当てる（1–4 行目）．分散が大立を目指した効率的なパーティショニング手法を提案する．現

きいセンサほどユーザ要求を満たした復元が難しいため，これ

実のアプリケーションを想定したときエッジ障害が発生しない

らセンサを割当の起点とすることで復元精度の全体的なバラン時間の方が長いと考えられるため，センサの初期割当を決める

スを取る狙いがある．次のステップでは，全センサの割当が決段階では通常時の計算コスト最小化を優先してセンサを重複な定するまで各スレッドへ 1 つずつ割り当てる（5–9 行目）．幅

く各スレッドに均等に配分する．このとき単にセンサをランダ

優先的に各スレッドへ順々に割り振ることでスレッド間のバラ

ムに割り当てるのではなく，今後障害が発生した際にセンサのンスを取っている．ただし，全ての割当パターンを検討するの追加を最小限に抑えられるよう初期配置の段階から割当を工夫

は計算コストの観点から非現実的なため，各スレッドに対するする．そして各時刻の障害状況に応じて必要最小限のセンサをセンサ割当は復元精度の評価関数に基づいて貪欲的に決定する

追加で割り当てることで，可能な限りユーザ要求を満たして損（7 行目）．

失データを復元する．以降では計算コストを最小化する初期割行列計算が必要な 7 行目の処理が本アルゴリズムのボトル

当の決定，および障害発生状況に応じた動的な割当制御の詳細

ネックとなるため，ヒューリスティックスに基づいて更なる効をそれぞれ説明する．

率化を検討する．式 (11) の定義より式 (10) が小さくなるほど復元精度も向上する．ここで式 (10) の第 1 項は事前確率分布で4. 1 計算コストを最小化する初期割当の決定ありパーティショニングによる影響は無い．一方，式 (10) の第まずはじめにセンサ割当の指針として，単一エッジ障害を想2 項は他センサの処理結果を用いることによる分散の減少度合定した復元精度に基づく評価関数を設計する．エッジ 𝑗 の障害を表しており，復元対象のセンサとの相関が強いセンサを用いにより，スレッド 𝑖 ではエッジ 𝑗 に割り当てられているセンサるほど減少度合も大きくなる．すなわち，相関の強いセンサを

𝑿 𝑗 ∈ X の処理結果を損失する．このとき，センサ 𝑋 ∈ 𝑨𝑖0 ∩ 𝑿 𝑗

同じスレッドに多く割り当てるほど復元精度が向上する傾向にの復元にはセンサ 𝑶 𝑖 𝑗 = 𝑨𝑖0 \ 𝑿 𝑗 が使用でき，復元結果の分散あるといえる．ただしエッジ障害を想定する場合，処理結果を

𝜎𝑋 は次式のとおり求められる．

損失したセンサと同一エッジへ割り当てられているセンサの処−1
𝜎𝑋 = Σ𝑋𝑋 − Σ𝑋𝑶𝑖 𝑗 Σ𝑶Σ𝑖 𝑗 𝑶𝑖 𝑗 𝑶𝑖 𝑗 𝑋(10)

理結果も共に損失する点に注意が必要である．
以上より，同一エッジに割り当てられているセンサ同士の相ここで 𝜎𝑋 およびユーザ要求充足に必要な分散の閾値 𝜎𝜃 の差

関を 0 とした相関行列 𝑅 に対して，次の関数により復元精度を

分 𝛥𝜎𝑋 = 𝜎𝜃 − 𝜎𝑋 が非負値となるようなセンサ 𝑋 は単一エッ

近似的に評価することでボトルネックの処理コストを軽減する．

ジ障害時にもユーザ要求を充足できると分かる．理想的には割
当センサ全てにおいてユーザ要求を充足したいため，スレッド

𝑖 の復元精度の評価関数 𝑓 𝑎𝑐𝑐 を差分の最小値と定義する．
(

𝑓 𝑎𝑐𝑐 𝑨𝑖0 | X, Σ)

= min 𝛥𝜎𝑋
𝑋∈ 𝑨0𝑖

(11)

𝑛 ∑
𝑎
(
) ∑
∗
𝑓 𝑎𝑐𝑐
𝑨𝑖0 | X, Σ =1l[𝑋𝑎 , 𝑋𝑏 ∈ 𝑨𝑖0 ] 𝑅 2𝑎𝑏(12)

𝑎=0 𝑏=0

ただし 1l[𝑋𝑎 , 𝑋𝑏 ∈ 𝑨𝑖0 ] はセンサ 𝑋𝑎 , 𝑋𝑏 が共にエッジ 𝑖 に割り当てられている場合 1 を，そうでない場合 0 を返す指示関数を∗ は単一エッジ障害時の復元に使用できるセンサ間の表す． 𝑓 𝑎𝑐𝑐

センサ
𝑋𝐴

エッジ

𝑋𝐵
𝑋𝐶

2

処理結果

𝑋𝐷
𝑋𝐸
𝑋𝐹

ゲートウェイ

求を満たせない可能性がある．この場合，ユーザ要求を満たす

スレッド

までリスト 𝐿 𝑖 の先頭から順にセンサを追加する．例えば図 4

1

3

欠損

𝑨1𝑡 = 𝑋𝐴 , 𝑋𝐶 , 𝑋𝐸

𝑨𝑡2 = 𝑋𝐵 , 𝑋𝐷 , 𝑋𝐹

𝑶′13 = 𝑋𝐷 を追加

𝑶′ 23 = {}なので追加なし

𝐿1 = 𝑋𝐷 , 𝑋𝐵 , 𝑋𝐹
𝑶′11 = {}𝑶′12 = {}𝑶′13 = 𝑋𝐷

𝐿2 = 𝑋𝐴 , 𝑋𝐸 , 𝑋𝐶
𝑶′21 = 𝑋𝐸
𝑶′22 = {}𝑶′ 23 = {}′ , 𝑶 ′ は共に空においてエッジ 2,3 に障害が発生したとき，𝑶 2223

集合なためスレッド 2 ではセンサを追加せず 𝑋 𝐵 の結果から

𝑋𝐷 , 𝑋𝐹 の処理結果を復元する．この復元精度がユーザ要求を満たさないとき，𝐿 2 の先頭であるセンサ 𝑋 𝐴 を追加して再度復元した結果を出力する．

図 4 動的な割当制御の例

共分散の二乗和を表しており，別々のエッジに割り当てられている相関の強いセンサを同一スレッドに割り当てるほど評価値が大きくなる．そのためこの評価関数を用いることで，エッジ障害による影響の偏りを抑制しつつ，スレッド全体の推定精度を高い水準で保つようなパーティショニングが期待できる．

4. 2 障害状況に応じた動的な割当制御
本節ではエッジの障害状況に応じた割当センサの動的な制御

障害状況やユーザ要求の厳しさ次第では，割当候補のセンサを全て追加してもユーザ要求を満たせない可能性がある点に注意する．このとき 𝐿 𝑖 の先頭から 1 つずつセンサを追加して復元結果がユーザ要求を満たすかを確かめるのは非効率的であり，各スレッドに対する割当センサ数が増えるほどこの計算コストも増加する．以上よりユーザ要求やシステムの構成機器の信頼度をふまえて，𝐿 𝑖 から 1 度にまとめて追加するセンサ数および各スレッドへのセンサ割当数の上限を設定することで，復元精度と計算コストのトレードオフを制御できる．

手法を提案する．2 節の議論より，近似的に復元した分散の値からユーザ要求を充足するかを判定できるため，基本的にはユーザ要求を充足するまで割当センサを追加すればよい．しかし，精度向上に効果のないセンサを 1 つずつ追加するのは非効

5 評価実験
本章では，処理遅延および復元精度に注目して本システムの性能を評価する．

率的なため，優先的に追加すべきセンサを事前に求めたい．
まず，スレッド 𝑖 に対する追加候補のセンサ 𝑿 \ 𝑨𝑖0 を優先順

5. 1 実 験 設 定に整列したリスト 𝐿 𝑖 を計算する．4. 1 節の議論より相関が大きa ) データセット

いセンサを割り当てるほど復元精度も向上するといえるため，様々な規模での提案システムの性能を評価するため，多次元∗ ( 𝑨0 ∪ {𝑋 } | X, Σ) の値が大きいセンサ 𝑋 から順評価関数 𝑓 𝑎𝑐𝑐𝑖

ガウス分布に従う人工データ 2880 タプルを作成した．全 𝑛 個に 𝐿 𝑖 へ格納すればよい．例えば図 4 のスレッド 1 への追加候のセンサを各エッジに対して 20 個ずつ割り当て，分散は全て

補のセンサは {𝑋 𝐵 , 𝑋𝐷 , 𝑋𝐹 } であり，センサ 𝑋𝐷 の評価値が一1 に設定し，期待値は同一エッジで共通の値とした上で時間経番大きいとき 𝐿 1 の先頭に 𝑋𝐷 を格納する．

過と共に変動させた．また，同一エッジに割り当てたセンサ同

次に，エッジ 𝑗 に障害が発生したとき，スレッド 𝑖 でユーザ士には強い相関を，別エッジに割り当てたセンサ同士には原則要求を満たすため最初に確定で追加するセンサ集合 𝑶 𝑖′ 𝑗 を計算として弱い相関をそれぞれ設定した．ただし，パーティショニ

する．4. 1 節の議論より，分散の目標値との差分 𝛥𝜎𝑋 が非負値

ングアルゴリズムの効果を見るため，別エッジに割り当てた一となればユーザ要求を充足するといえる．よって，エッジ 𝑗 の部のセンサ同士にも強い相関を設定した．センサ数の規定値は障害により処理結果を損失する全てのセンサ ∀𝑋 ∈ 𝑨𝑖0 ∪ 𝑿 𝑗 について， 𝑨𝑖0 に加えたときの 𝛥𝜎𝑋 が非負値となるまで 𝐿 𝑖 の先頭から順に 𝑶 𝑖′ 𝑗 へ追加すればよい．例として図 4 のエッジ 3 に

𝑛 = 500 とし，データ生成時に使用したモデルをそのまま実験に使用する．

b ) 実験シナリオ

障害が発生したとき，スレッド 1 では {𝑋 𝐴, 𝑋𝐶 } の処理結果の本実験ではセンサ，エッジ，およびゲートウェイから構成さみからユーザ要求を満たしてセンサ 𝑋𝐸 の処理結果を復元できれるシステムを想定する．各センサは一定間隔で計測値を割当′ へないとする．このとき， 𝐿 1 の先頭であるセンサ 𝑋𝐷 を 𝑶 13

エッジに対して送信し，エッジでは窓幅 𝑤 = 10，滑り幅 𝑙 = 2 の追加し， 𝑋𝐷 を加えて復元する場合の 𝛥𝜎𝑋𝐸 が非負値となるか設定のもと各センサの平均値を計算する．そして，ゲートウェを確かめる． 𝛥𝜎𝑋𝐸 が非負値となるとき，それ以上のセンサはイでは障害による欠損値を復元し，エッジの処理結果をまとめ′ = {𝑋 } を得る．
必要ないため 𝑶 13
𝐷

スレッド 𝑖 は上述の事前計算した情報に基づき，エッジの障害状況に応じて割当センサを動的に制御する．エッジ 𝑗 に障害て出力する．ただし各エッジに対して 20 個のセンサを，ゲー
トウェイの各スレッドに対して 50 個のセンサをそれぞれ割り
当てるものとする．

が発生したとき，まずはじめに 𝑶 𝑖′ 𝑗 を追加して損失した処理結果を復元する．ここで 𝑶 𝑖′ 𝑗 は単一エッジ障害に対してユーザ要

づき各機器の処理状況をシミュレートする．各エッジは運転状求を満たすために必要な最小限のセンサを表すため，エッジ 𝑗

態から故障状態へ確率 𝑟 𝑓 で遷移すると，これまで受け取ったのみに障害が発生している場合はこれ以上のセンサの追加なし

入力および内部状態を削除し，故障状態にある間は一切の動作に復元結果を出力できる．しかし複数エッジに同時に障害が発を停止する．そして故障状態に遷移してから 𝑡 𝑓 単位時刻後に生すると，対応する全ての 𝑶 𝑖′ 𝑗 を追加するだけではユーザ要

この構成において，エッジ故障を模倣した障害シナリオに基運転状態へと復帰すると，データ処理や出力などの処理を再開

表 1 実験用サーバの構成

OS

Ubuntu 20.04.5 LTS

CPUIntel(R) Xeon(R) Gold 6262V CPU @ 1.90GHz

メモリ

256GB

ストレージ

480GB

singleproposed
0.3
0.2
0.1
0

する．なお，規定値はそれぞれ 𝑟 𝑓 = 0.01, 𝑡 𝑓 = 10 とする．

0

0.05

c) 実

装

本システムの性能評価実験のためプロトタイプを構築した．

やゲートウェイの入力キューとして Kafka [10] などのメッセー
ジキューが一般的であるが，本実験では特定時刻のデータ削除などの障害シナリオに従った細かな制御が容易な PostgreSQLを採用した．環境センサとの通信制御などが必要なエッジ環境への適応性を鑑みて Python 3.9.0 を用いて実装しており，行列演算は全て NumPy を用いて計算する．
本実験ではデータソースのシミュレータも含め全てのプログ
ラムを 1 台のサーバ上で実行した．実験に使用したマシンの構成を表 1 に示す．エッジデバイスの実機を用いた性能評価は今後の課題とする．

d) 比 較 対 象
以上の設定のもと，以下の 5 手法の実験結果を比較すること
で提案システムの各機能が及ぼす効果を評価する．

•

single：1 スレッドのみで処理する場合の実験結果．

•

random：ランダムに初期割当を決定した場合の実験結果．

•

vanilla：図 3 のアルゴリズムに基づいて初期割当を決定した場合の実験結果．

•

proposed：図 3 のアルゴリズムにおいて復元精度を式 (12)に基づいて評価して初期割当を決定した場合の実験結果．

•

proposed+：proposed の初期割当から障害状況に応じて動的に割当を制御する場合の実験結果．ただし誤差要求の規定
値を 𝛿 = 0.9，𝜖 = 0.25 とし，各スレッドの割当数の上限を 150とした．

5. 2 処理精度の評価
理論的に求められる誤差上限およびユーザ要求の充足率の 2つの指標により本システムの復元精度を評価する．各センサ

𝑋 ∈ 𝑿 の全ての復元結果に対して誤差上限 𝑒 𝑋 を計算し，その平均二乗和を理論的な誤差量 𝑟𝑚𝑠𝑒 𝑋 として算出する．また充足率は各復元結果の誤差上限 𝑒 𝑋 がユーザ指定の許容誤差 𝜖 以下に収まる割合を指すものとする．ここで誤差上限 𝑒 𝑋 はユーザ指定の要求信頼度 𝛿 に対する誤差幅であり，充足率が 1 となっ

10

20

30

障害復帰時間𝑡𝑓

1
0.8
0.6
0.4
0.2
0
0

0.05

障害発生確率𝑟𝑓

エッジでは欠損値の復元とデータ集約を，ゲートウェイでは欠損値の復元をそれぞれマイクロバッチ形式で実行する．エッジ

0

充足率

充足率

ため，使用データセットそれぞれに対して設定した単位時刻

らのデータ送信間隔に応じてそれぞれ設定する．

0.1(a) 誤差量を使用する．実際の計測間隔では実験に時間がかかりすぎる

送信する．エッジやゲートウェイの処理間隔もシミュレータかvanilla

0.25
0.2
0.15
0.1
0.05
0

障害発生確率𝑟𝑓

また，データソースには実際のセンサではなくシミュレータ

𝑇 = 0.1[𝑠] 毎にシミュレータから対応するエッジへと計測値をrandomproposed+

RMSE

Dell PowerEdge R640

RMSE

機器名

1
0.8
0.6
0.4
0.2
0

0.1

0

(b) 充足率

10

20

30

障害復帰時間𝑡𝑓

図 5 欠損シナリオに対する RMSE の変化たとき全てのデータをユーザ要求を満たして復元できたといえる．ただし，障害による欠損が発生しなかったセンサの処理結
果は誤差ゼロのため評価対象から除く．
欠損シナリオのパラメータである障害発生確率 𝑟 𝑓 および障害復帰時間 𝑡 𝑓 を変化させたときの実験結果を図 5 に示す．実験結果より，proposed は random に比べ誤差量と充足率をともに改善できていることから，初期割当を工夫することで復元精度を改善できるとわかる．また proposed は vanilla と同等の復元精度を達成できており，ヒューリスティックスに基づいて設計した近似的な評価関数の妥当性が見て取れる．一方，proposed+の誤差量は proposed のものと大きく変わらないが，充足率を大幅に改善できている．このことから，提案手法の動的制御では復元結果がユーザ要求を充足できないときにのみ，必要最小限のセンサを追加で割り当てられているとわかる．

5. 3 処理遅延の評価
応答時間に基づいて本システムの処理遅延を評価する．各時
間窓内に割り当てられた計測値の内最小の送信時刻を入力時刻

𝑡𝑖 ，その時間窓の処理結果がゲートウェイからシンクへ出力された時刻を出力時刻 𝑡 𝑜 とそれぞれ定義し，応答時間はこれら時刻の差 𝑡 𝑜 − 𝑡 𝑖 として求める．
欠損シナリオのパラメータである障害発生確率 𝑟 𝑓 および障害復帰時間 𝑡 𝑓 を変化させたときの実験結果を図 6 に示す．な
お応答時間はデータの送信間隔や窓幅に大きく依存することから，一切の欠損がないときの理想的な応答時間を参考値として破線で示している．
実験結果より，single ではデータの欠損が増えるほど応答時間も増加するのに対して，proposed の応答時間はパラメータの変化によらずほとんど理想的な値となっている．また，proposedの応答時間は vanilla や random と変わらないことから，初期割当の違いによる応答時間への影響は無いとわかる．以上より，
シングルスレッドでは計算コストの重さから処理遅延が増大すsingleproposedrandomproposed+

んど理想的な値になっている．特にセンサ数 𝑛 = 5000 のとき，

porposed は single に比べて処理遅延を 1000 倍以上短縮できて

1000

応答時間[s]

応答時間[s]10000

して応答時間も増加傾向にあるが，proposed の応答時間はほとvanilla

1000
100
10

1

いる．また，proposed+の応答時間は増加傾向にあるものの増加
100

幅は小さく抑えられており，single に比べて処理遅延を最大で10100 倍以上短縮できている．以上より提案手法ではシステム規模が増加したとしても，ユーザの誤差要求を満たせる範囲で処

1
0

0.05

0.1

0

障害発生確率𝑟𝑓

10

20

30

障害復帰時間𝑡𝑓

6 関連研究

図 6 欠損シナリオに対する応答時間の変化

10000
1000
100
10
1
0.1
0.01

randomproposed+vanilla

本章ではデータストリーム処理システムにおける耐障害性保証およびパーティショニング制御の関連研究について概説する．

10000

応答時間[s]

前処理時間[s]singleproposed

6. 1 耐障害性保証

1000
100

既存システムの多くは耐障害性保証として at-most-once セ

10

マンティクスや at-least-once セマンティクスを提供する [6, 7]．

at-most-once セマンティクスを保証するシステムでは内部状態

1
50

500

5000

センサ数

理遅延を大きく削減できるとわかる．

50

500

5000

センサ数

などのバックアップを取らず待機ノードへの処理移譲のみを行うため，データ損失の恐れがある．一方，at-least-once セマン

図 7 システム規模に対する前処理時間および応答時間の変化

ティクスを保証するシステムでは障害復帰処理として入力デー

るような環境下でも，並列処理により処理遅延を大幅に削減でタを再送するが，同一データを複数回処理する可能性がある．

きるといえる．一方，proposed+は欠損が増えるほど応答時間がつまり，これらのセマンティクスに基づくシステムでは障害に増加しているが，その増加幅は小さく抑えられている．特に障より生じる誤差量を保証できない．

害発生確率 𝑟 𝑓 = 0.1 のとき全体の約半数のデータが欠損するこ

Flink [4] や Spark Streaming [5] などのシステムでは，誤差のとになるが，proposed+は single に比べて処理遅延を 100 倍以

ない頑健な耐障害性保証として exactly-once セマンティクスを上削減しながら，90% 以上の充足率を達成できている．以上よ提供する．これらのシステムでは内部状態の定期的なバックり，提案手法では障害状況に応じて必要最低限のセンサを追加

アップおよび復旧時の入力データの適切な再処理により，障害することで，ユーザの誤差要求を満たせる範囲で処理遅延を大発生時も入力されたデータを過不足なく 1 回処理した結果が得きく削減できているとわかる．

られる．ただし，他のセマンティクスに比べバックアップの取

proposed+の結果について詳しく見ると，障害復帰時間 𝑡 𝑓 よ

得手順は複雑であり，処理のスループットも低下する．

りも障害発生確率 𝑟 𝑓 の増加に対して応答時間の増加が大きく

また Huang らは耐障害性保証におけるコスト削減のため，結なる傾向にある．これは，障害発生確率 𝑟 𝑓 の増加により同時果の信頼性を保証した近似的な耐障害性保証を提案した [11]．

刻に多くのエッジに障害が発生しやすくなり，追加候補のセン

未処理データ数と内部状態の変量に対するしきい値を超した場

サ集合 𝑶 𝑖′ 𝑗 だけの追加ではユーザ要求を満たせないケースが増合にのみバックアップを取ることで，バックアップデータ量おえてしまったためであると考えられる．複数エッジの障害に対よびその頻度を削減できスループットが向上する．

してもより高速にユーザ要求を満たす割当の決定が今後の課題である．

これら従来型の耐障害性保証は主にクラウド環境を想定して設計されており，エッジ環境への適用には問題がある．エッジ

次に、システム規模に対する性能変化をみるため，センサ

環境ではデバイス故障に対して人手で修理ないし交換する必要

数 𝑛 を変化させたときの応答時間および前処理の所要時間をがあるため，クラウド環境のような仮想マシンの立ち上げによ図 7 に示す．ただし，前処理の所要時間として proposed およる早急な障害復帰は望めない．またエッジ環境特有の物理的制

び vanilla は初期割当決定に要した時間を，proposed+は割当優

約の強さから，システム規模が大きくなるほどデバイスの多重

先順のリスト 𝐿 𝑖 および追加候補のセンサ集合 𝑶 𝑖′ 𝑗 の計算時間化コストは増加し，かつ代替マシン活用の柔軟性もクラウド環

をそれぞれ示す．

境に劣る．すなわち，上述の待機系への処理移譲を基本とする

実験結果より，センサ数の増加に対して前処理の所要時間も増加しているものの，vanilla に比べて proposed は 5 倍ほど計

従来アプローチでは障害発生時の処理継続が困難であるといえる．

算時間を短縮できている．また proposed+の前処理時間も初期

この課題に対して，我々のグループでは近似的な耐障害性保割当決定に要する時間以内で収まっており，近似的な評価関数

証に基づくエッジストリーム処理システムを提案した [2, 3]．前により前処理での計算コストも削減できているといえる．

段機器の障害により損失したデータを後段の機器で近似的に復次に応答時間について見ると，single はセンサ数の増加に対元することで，エッジ側での物理的な多重化や処理の途中結果

の定期的なチェックポインティングなしに，故障機器の復旧を開発機構（NEDO）の委託業務（JPNP16007）の結果得られた

待たずに処理を継続できる．そのため障害によるダウンタイム

ものである．

が長期化しがちなエッジ環境においても，処理遅延と可用性を高水準に維持できる．

6. 2 パーティショニング制御
既存システムの多くは大規模ストリームを高速に処理するため，キーパーティショニングに基づく並列処理をサポートしている [4–6,12,13]．データストリーム処理システムでは一般的に，各スレッドに対して入力データをより均等に割り振るほど処理性能も向上することから，パーティショニングアルゴリズムはシステムの処理性能を決定する重要な要素の 1 つである [14]．
特に集約処理などの内部状態を伴うステートフル処理では，キーの出現頻度の偏りやワークロードの変動の影響を大きく受けることから，効率的な処理を実現するための様々な手法が提案されている [14–17]．例えば Katsipoulakis らの手法 [14] は
複数スレッドで並列に集約した結果を後で 1 つにまとめる二段階の集約処理を想定し，全体的な計算コストを考慮してキー分割することで，単純なシャッフリングやハッシュに基づく手法に比べて 10 倍以上高速に処理できる．また Zapridou らの手
法 [17] は，強化学習を活用しワークロードの変化に追従してパーティショニングポリシーを動的に制御することで，他の手法に比べて 6.7 倍高速に処理できる．しかし近似的な耐障害性保証のアプローチでは，キーの偏りやワークロード変化ではな
くパーティショニングによる処理精度低下が課題であるため，
これら既存手法は復元精度と処理性能のトレードオフの問題解
決には適さない．

7 ま と め本稿では近似的な耐障害性保証に基づくデータストリーム処理を想定し，復元精度と処理性能のトレードオフを考慮した
パーティショニング手法を提案した．本手法はヒューリスティッ
クスを活用した初期割当アルゴリズムおよび，障害発生状況に応じた動的な割当制御により，全てのセンサの処理結果をユー
ザ要求を満たして復元できる範囲で計算コストを最小化する．
実験により，提案手法は障害状況に対して必要最小限のセンサを追加することで，ユーザの誤差要求を高い確率で満たしながら処理遅延をシングルスレッドに比べて 100 倍以上削減できることを確認した．
今後の課題として，誤差要求と計算コストのトレードオフをユーザが対話的に調整できるなど，運用面まで考慮したアルゴ
リズムの改善が挙げられる．また，提案手法の各工夫点の効果をより精密に評価するとともに，実データやセンサ故障の考慮などより現実的な設定での評価実験についても取り組む予定で
ある．

謝

辞

本研究は JSPS 科研費 JP20K19804，JP21H03555，JP22H03594の助成，および国立研究開発法人新エネルギー・産業技術総合

文

献[1] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE Internet of Things Journal, vol. 3, no. 5,
pp. 637–646, 2016.
[2] 高尾大樹, 杉浦健人, 石川佳治, “エッジコンピューティングにおける低遅延かつ高信頼度なデータストリームの近似的集約処理,”
電子情報通信学会論文誌 D, vol. J104-D, no. 5, pp. 463–475, 2021.
[3] D. Takao, K. Sugiura, and Y. Ishikawa, “Approximate fault tolerance for edge stream processing,” in Database and Expert Systems
Applications - DEXA 2021 Workshops, pp. 173––183, 2021.
[4] “Apache Flink: Stateful Computations over Data Streams.” https://flink.apache.org/ (Accessed: Jan. 8, 2022).
[5] “Spark Streaming | Apache Spark.” https://spark.apache.org/
streaming/ (Accessed: Jan. 8, 2022).
[6] “Apache Storm.” https://storm.apache.org/ (Accessed: Jan.
8, 2022).
[7] L. Neumeyer, B. Robbins, A. Nair, and A. Kesari, “S4: Distributed
stream computing platform,” in 2010 IEEE Int. Conf. on Data Mining
Workshops, pp. 170–177, 2010.
[8] C. M. Bishop, Pattern Recognition and Machine Learning. Springer,
2006.
[9] D. C. Lay, S. R. Lay, and J. J. McDonald, Linear Algebra and Its
Applications. Pearson, 5th ed., 2014.
[10] “Apache Kafka.” https://kafka.apache.org/ (Accessed: Jan.
8, 2022).
[11] Q. Huang and P. P. C. Lee, “Toward high-performance distributed
stream processing via approximate fault tolerance,” Proc. VLDB,
vol. 10, no. 3, pp. 73–84, 2016.
[12] T. Akidau, R. Bradshaw, C. Chambers, S. Chernyak, R. J. FernándezMoctezuma, R. Lax, S. McVeety, D. Mills, F. Perry, E. Schmidt,
et al., “The dataﬂow model: A practical approach to balancing correctness, latency, and cost in massive-scale, unbounded, out-of-orderdata processing,” Proc. VLDB, vol. 8, pp. 1792–1803, 2015.
[13] M. Zaharia, T. Das, H. Li, S. Shenker, and I. Stoica, “Discretizedstreams: An eﬃcient and fault-tolerant model for stream processing
on large clusters,” in Proc. the 4th USENIX Conf. on Hot topics inCloud Computing, p. 10, 2012.
[14] N. R. Katsipoulakis, A. Labrinidis, and P. K. Chrysanthis, “A holistic view of stream partitioning costs,” Proc. VLDB, vol. 10, no. 11,
pp. 1286–1297, 2017.
[15] M. Anis Uddin Nasir, G. De Francisci Morales, D. Garcia-Soriano,
N. Kourtellis, and M. Seraﬁni, “The power of both choices: Practicalload balancing for distributed stream processing engines,” in Proc.
ICDE, pp. 137–148, 2015.
[16] M. Anis Uddin Nasir, G. De Francisci Morales, N. Kourtellis, and
M. Seraﬁni, “When two choices are not enough: Balancing at scale
in distributed stream processing,” in Proc. ICDE, pp. 589–600, 2016.
[17] E. Zapridou, I. Mytilinis, and A. Ailamaki, “Dalton: Learned partitioning for distributed data streams,” Proc. VLDB, vol. 16, no. 3,
pp. 491–504, 2023.