競合解決：戦略、マージ、動作原理

モバイルアプリケーションにおける競合解決とは？

競合解決とは、矛盾する変更を検出した後、分散データを単一の一貫した状態に導くプロセスです。集中型システムでは、競合は発生しません。サーバーはリクエストを順次処理します。オフラインモードのモバイルアプリケーションでは、クライアントはデータをローカルで変更し、後でサーバーと同期します。2つのクライアントが同じオブジェクトを変更した場合、サーバーは同じ識別子を持つが内容が異なる2つのバージョンを受信します。

疎結合レプリケーション（結果整合性）では、競合は避けられません。システムは可用性とパフォーマンスのために即時整合性を犠牲にします。プリンストン大学の研究者（Aggarwal et al.、GEO論文、KDD 2024）によると、遅延レプリケーションを使用するシステムは、ピーク負荷時に28%高いパフォーマンスを示しますが、正しい動作のために競合解決メカニズムが必要です。

解決戦略は、競合が検出されたときにシステムが自動的に適用するアルゴリズムです。データベースやフレームワークによって異なる戦略が実装されています。Firebase Realtime DatabaseはLWWを使用し、CouchDBはマージサポートを追加し、FigmaやNotionはCRDT上にアーキテクチャを構築しています。

データ同期中に競合が発生する理由

競合の主な原因は、データのローカルコピーで作業する2つ以上のクライアントによる同じリソースの同時変更です。典型的なシナリオ：ユーザーAがTrelloでオフライン中にタスクを編集し、同時にユーザーBが別のデバイスで同じタスクの説明を変更します。両方とも自分のバージョンをローカルに保存します。デバイスがネットワークに接続すると、サーバーは同じフィールドに対して2つの異なる値を受け取ります。

追加要因として、ネットワーク遅延やネットワーク分割があります。RaftやPaxosプロトコルを使用する分散データベースでは、クラスターリーダーが一時的に利用できず、リクエストが異なるノードで処理される場合に競合が発生することがあります。Amazon DynamoDBのホワイトペーパー（2025）によると、スケーラブルなNoSQLシステムにおける全書き込み操作の約0.3%が検出可能な競合を引き起こします。

不適切なデータ構造からも競合が発生します。アプリケーションが操作カウンターや参加者リストを保存する場合、2つのオフラインクライアントが順序的に互換性のない操作を実行する可能性があります。たとえば、クライアントAがリストの末尾にアイテムを追加し、クライアントBが中央からアイテムを削除する場合、同期中にサーバーはどちらのアクションを先に適用すべきかわかりません。

Last Write Wins — 時間ベースの勝者戦略

Last Write Wins（LWW）は、競合するバージョンの中で最新のタイムスタンプを持つエントリを選択する戦略です。システムは各バージョンのタイムスタンプを比較し、新しい方を受け入れ、古い方を破棄します。これは決定論的なメカニズムであり、同じタイムスタンプのセットでは結果が常に同じになり、不確実性が排除されます。LWWはFirebase Realtime Database、Apache Cassandra、Riak KVで実装されています。

モバイルアプリケーションでは、LWWは実装の単純さから特に魅力的です。クライアントはバージョン間の差異を分析したり、変更履歴を保存したり、ユーザーに選択ダイアログを表示したりする必要がありません。サーバーはミリ秒で決定を下します。ただし、LWWには根本的な欠点があります — データ損失です。2人のユーザーが同時にフォームの異なるフィールドに入力した場合、一方のバージョンが完全に破棄されます。

REST APIを介した同期を行うモバイルメモアプリでのLWWの動作例：

data class Note(
    val id: String,
    val title: String,
    val content: String,
    val updatedAt: Long
)

fun resolveWithLWW(
    local: Note,
    remote: Note
): Note {
    return if (local.updatedAt >= remote.updatedAt) local
    else remote
}

resolveWithLWW関数はタイムスタンプを比較し、現在のバージョンを返します。タイムスタンプが等しい場合（高い書き込み頻度で発生）、通常はローカルバージョンが優先されます。

マージ戦略 — 競合バージョンの統合

マージ戦略は、システムが一方のバージョンを完全に破棄するのではなく、両方の変更を一貫した状態に結合しようとするアプローチです。これはGitでのブランチのマージに類似しています。各競合は個々のフィールドまたは操作のレベルで解決されます。マージ戦略は、自動（CRDT、OT）と手動（ユーザーがオプションを選択）に分類されます。

最もよく知られている実装はスリーウェイマージです。システムは3つのバージョン（ローカル、リモート、およびそれらの共通の祖先（分岐前のベースバージョン））を保存します。1つのクライアントのみがフィールドを変更した場合、その変更は自動的に受け入れられます。両方のクライアントが同じフィールドを変更した場合、解決が必要な競合が記録されます。CouchDBとPouchDBは、ドキュメント同期にこのモデルを積極的に使用しています。

ユーザープロファイルのスリーウェイマージ実装例：

data class Profile(
    val name: String,
    val email: String,
    val avatarUrl: String
)

fun threeWayMerge(
    base: Profile,
    local: Profile,
    remote: Profile
): Profile {
    return Profile(
        name = if (local.name != base.name) local.name
                else remote.name,
        email = if (local.email != base.email) local.email
                else remote.email,
        avatarUrl = if (remote.avatarUrl != base.avatarUrl) remote.avatarUrl
                    else local.avatarUrl
    )
}

スリーウェイマージは、データ構造が十分に安定している場合に効果的です。フィールド名の変更、型の変更、配列操作を行う際に問題が発生します — これらの場合、より複雑なロジックが必要です。

CRDT — 競合のない複製データ型

CRDT（Conflict-Free Replicated Data Type）は、中央コーディネーターなしでデータの収束を保証する数学的モデルです。CRDTはすべての操作が可換になるように設計されており、適用順序が最終結果に影響を与えません。これは代数的性質によって達成されます。CRDTのマージは、変更を受信する順序に関係なく常に同じ結果を生成します。

CRDTの主なタイプには、G-Counter（インクリメントのみをサポートするカウンター）、PN-Counter（インクリメントとデクリメントを備えたカウンター）、LWW-Register（バージョニング付きレジスター）、OR-Set（追加と削除を追跡するセット）があります。各タイプは、2つのレプリカのマージが競合を生成しないことを保証します。INRIAの研究（Marc Shapiro et al.、2024）によると、CRDTは一般的なデータタイプの95%に対して決定論的な収束を提供します。

G-Counterの例 — インクリメントのみ可能なカウンター：

class GCounter {
    private val counts = mutableMapOf<String, Int>()

    fun increment(nodeId: String) {
        counts[nodeId] = (counts[nodeId] ?: 0) + 1
    }

    fun value(): Int = counts.values.sum()

    fun merge(other: GCounter) {
        other.counts.forEach { (node, count) ->
            counts[node] = maxOf(counts[node] ?: 0, count)
        }
    }
}

GCounterは、各ノードが自身のカウンターのみを保存し、マージがノードごとに最大値を取るため、正しいマージを保証します。これは、分散システムで使用される競合のない構造の典型的な例です。

競合解決戦略の選び方

戦略の選択は、データの性質と使用シナリオに依存します。LWWは最新バージョンが常に優先されるアプリケーション（ニュースフィード、通知、ステータス）に最適です。マージ戦略は、各フィールドが独立している構造化ドキュメント（ユーザープロファイル、フォーム、設定）に適しています。CRDTは、分散システムでの共同編集、リスト、カウンターに理想的です。

戦略を選択する際、3つの要因が評価されます：データの一貫性、パフォーマンス、実装の複雑さ。LWWは最大のパフォーマンスと最小の複雑さを提供しますが、データを失う可能性があります。マージは高い精度を提供しますが、フィールドレベルでの変更検出メカニズムが必要です。CRDTは数学的な正確性を保証しますが、データタイプとメタデータサイズに制限を課します。

実際には、組み合わせアプローチがよく使用されます。システムはメタデータにLWW、ドキュメントコンテンツにマージ、リスト構造にCRDTを使用します。たとえばFirebase Firestoreは、トップレベルのフィールドにLWWを適用し、アトミック更新のためのトランザクションをサポートしています。CouchDBは変更履歴ストレージとともにマージを使用します。FigmaとNotionは、リアルタイムのマルチユーザー編集のためにCRDT上にアーキテクチャを構築しています。