class HeartbeatMonitor:
    def __init__(self, interval=5, timeout=1, max_failures=3):
        self.interval = interval
        self.timeout = timeout
        self.max_failures = max_failures
        self.failure_count = defaultdict(int)
    
    def check_node(self, node):
        try:
            response = self.send_heartbeat(node, timeout=self.timeout)
            if response:
                self.failure_count[node] = 0
                return True
        except TimeoutError:
            self.failure_count[node] += 1
            
        if self.failure_count[node] >= self.max_failures:
            return False  # ノード障害と判定
        
        return True  # まだ障害とは判定しない

def can_form_quorum(total_nodes, available_nodes):
    quorum_size = (total_nodes // 2) + 1
    return available_nodes >= quorum_size

# 偶数ノードでの問題
# 4ノードクラスタが2+2に分断された場合
# クォーラム = 3なので、両側ともサービス停止
# 解決策：Witness（投票のみ行う軽量ノード）の追加

class VectorClock:
    def __init__(self, node_id):
        self.node_id = node_id
        self.clock = defaultdict(int)
    
    def increment(self):
        """自ノードのクロックをインクリメント"""
        self.clock[self.node_id] += 1
    
    def update(self, other_clock):
        """他ノードのクロックを受信して更新"""
        for node, timestamp in other_clock.items():
            self.clock[node] = max(self.clock[node], timestamp)
        self.increment()
    
    def happens_before(self, other):
        """因果関係の判定"""
        for node in set(self.clock.keys()) | set(other.clock.keys()):
            if self.clock.get(node, 0) > other.clock.get(node, 0):
                return False
        return True

class GCounter:
    def __init__(self, node_id):
        self.node_id = node_id
        self.counts = defaultdict(int)
    
    def increment(self, value=1):
        """カウンターをインクリメント"""
        self.counts[self.node_id] += value
    
    def merge(self, other):
        """他ノードのカウンターとマージ"""
        for node, count in other.counts.items():
            self.counts[node] = max(self.counts[node], count)
    
    def value(self):
        """現在の合計値を取得"""
        return sum(self.counts.values())

class ReadRepair:
    def __init__(self, nodes, quorum_size):
        self.nodes = nodes
        self.quorum_size = quorum_size
    
    def read(self, key):
        # 複数のノードから読み取り
        responses = []
        for node in self.nodes[:self.quorum_size + 1]:
            try:
                value, version = node.get(key)
                responses.append((node, value, version))
            except:
                continue
        
        if len(responses) < self.quorum_size:
            raise Exception("Quorum not reached")
        
        # 最新バージョンを特定
        latest_version = max(r[2] for r in responses)
        latest_value = next(r[1] for r in responses if r[2] == latest_version)
        
        # 古いノードを修復
        for node, value, version in responses:
            if version < latest_version:
                node.put(key, latest_value, latest_version)
        
        return latest_value

class TwoPhaseCommit:
    def __init__(self, coordinator, participants):
        self.coordinator = coordinator
        self.participants = participants
    
    def execute_transaction(self, transaction):
        transaction_id = generate_unique_id()
        
        # Phase 1: Prepare
        prepare_results = []
        for participant in self.participants:
            try:
                result = participant.prepare(transaction_id, transaction)
                prepare_results.append((participant, result))
            except Exception as e:
                # 準備失敗、全体をアボート
                self._abort_all(transaction_id, prepare_results)
                raise e
        
        # すべての参加者が準備完了を確認
        if all(result == "READY" for _, result in prepare_results):
            # Phase 2: Commit
            try:
                for participant, _ in prepare_results:
                    participant.commit(transaction_id)
                return "COMMITTED"
            except Exception as e:
                # コミット中の障害、リカバリが必要
                self._recovery_protocol(transaction_id)
                raise e
        else:
            # Phase 2: Abort
            self._abort_all(transaction_id, prepare_results)
            return "ABORTED"

class SemiSyncReplication:
    def __init__(self, timeout_ms=1000, min_replicas=1):
        self.timeout_ms = timeout_ms
        self.min_replicas = min_replicas
    
    def write(self, data):
        # プライマリに書き込み
        primary_result = self.primary.write(data)
        
        # レプリカへの非同期送信を開始
        replica_futures = []
        for replica in self.replicas:
            future = self.send_async(replica, data)
            replica_futures.append(future)
        
        # タイムアウトまで、最小数のレプリカからの応答を待つ
        confirmed_replicas = 0
        start_time = time.time()
        
        while confirmed_replicas < self.min_replicas:
            if (time.time() - start_time) * 1000 > self.timeout_ms:
                # タイムアウト、非同期モードに切り替え
                break
            
            for future in replica_futures:
                if future.done() and future.result() == "ACK":
                    confirmed_replicas += 1
        
        return {
            "status": "success",
            "mode": "semi-sync" if confirmed_replicas >= self.min_replicas else "async",
            "confirmed_replicas": confirmed_replicas
        }

class LastWriteWins:
    def resolve_conflict(self, value1, timestamp1, value2, timestamp2):
        if timestamp1 > timestamp2:
            return value1
        elif timestamp2 > timestamp1:
            return value2
        else:
            # タイムスタンプが同じ場合は、決定的な方法で選択
            return max(value1, value2)  # または、ノードIDで判定

class ApplicationSpecificResolver:
    def resolve_conflict(self, conflicts):
        # 例：ショッピングカートの場合
        if self.object_type == "shopping_cart":
            # すべてのアイテムをマージ
            merged_items = {}
            for version in conflicts:
                for item_id, quantity in version.items():
                    merged_items[item_id] = max(
                        merged_items.get(item_id, 0), 
                        quantity
                    )
            return merged_items
        
        # 例：カウンターの場合
        elif self.object_type == "counter":
            # 増分の合計を計算
            return sum(v.increment for v in conflicts)

class ReplicationLoop Prevention:
    def __init__(self, node_id):
        self.node_id = node_id
        self.processed_changes = set()
    
    def apply_change(self, change):
        # 変更の一意識別子を生成
        change_id = f"{change.origin_node}:{change.timestamp}:{change.sequence}"
        
        # すでに処理済みの変更は無視
        if change_id in self.processed_changes:
            return False
        
        # 変更を適用
        self.apply_to_local_db(change)
        
        # 処理済みとしてマーク
        self.processed_changes.add(change_id)
        
        # 他のノードに転送（元のノードは除外）
        for peer in self.peers:
            if peer.node_id != change.origin_node:
                peer.replicate(change)
        
        return True

class ReplicationLagMonitor:
    def measure_lag(self):
        # プライマリの現在位置を取得
        primary_position = self.primary.get_replication_position()
        
        lag_metrics = {}
        for replica in self.replicas:
            # レプリカの現在位置を取得
            replica_position = replica.get_replication_position()
            
            # 遅延を計算（バイト数または時間）
            lag_bytes = primary_position.lsn - replica_position.lsn
            lag_time = primary_position.timestamp - replica_position.timestamp
            
            lag_metrics[replica.name] = {
                'lag_bytes': lag_bytes,
                'lag_seconds': lag_time,
                'is_critical': lag_time > self.critical_threshold
            }
        
        return lag_metrics

class ConsistentRead:
    def __init__(self, primary, replicas):
        self.primary = primary
        self.replicas = replicas
    
    def read(self, key, consistency_level="eventual"):
        if consistency_level == "strong":
            # 常にプライマリから読む
            return self.primary.read(key)
        
        elif consistency_level == "bounded_staleness":
            # 許容される遅延内のレプリカから読む
            for replica in self.replicas:
                if replica.lag_seconds < self.max_staleness_seconds:
                    return replica.read(key)
            
            # 条件を満たすレプリカがない場合はプライマリから
            return self.primary.read(key)
        
        elif consistency_level == "read_your_writes":
            # セッションごとに最後の書き込みタイムスタンプを追跡
            last_write_ts = self.session.last_write_timestamp
            
            for replica in self.replicas:
                if replica.has_replicated_up_to(last_write_ts):
                    return replica.read(key)
            
            return self.primary.read(key)
        
        else:  # eventual consistency
            # 任意のレプリカから読む
            return random.choice(self.replicas).read(key)

class CircuitBreaker:
    def __init__(self, failure_threshold=5, timeout=60, half_open_requests=3):
        self.failure_threshold = failure_threshold
        self.timeout = timeout
        self.half_open_requests = half_open_requests
        
        self.failure_count = 0
        self.last_failure_time = None
        self.state = "CLOSED"  # CLOSED, OPEN, HALF_OPEN
        self.half_open_count = 0
    
    def call(self, func, *args, **kwargs):
        if self.state == "OPEN":
            if time.time() - self.last_failure_time > self.timeout:
                self.state = "HALF_OPEN"
                self.half_open_count = 0
            else:
                raise CircuitOpenException("Circuit breaker is OPEN")
        
        try:
            result = func(*args, **kwargs)
            
            # 成功時の処理
            if self.state == "HALF_OPEN":
                self.half_open_count += 1
                if self.half_open_count >= self.half_open_requests:
                    self.state = "CLOSED"
                    self.failure_count = 0
            
            return result
            
        except Exception as e:
            self.failure_count += 1
            self.last_failure_time = time.time()
            
            if self.failure_count >= self.failure_threshold:
                self.state = "OPEN"
            
            raise e

class BackpressureQueue:
    def __init__(self, max_size=1000, high_watermark=0.8, low_watermark=0.6):
        self.queue = Queue(maxsize=max_size)
        self.max_size = max_size
        self.high_watermark = high_watermark
        self.low_watermark = low_watermark
        self.accepting = True
    
    def put(self, item, timeout=None):
        current_usage = self.queue.qsize() / self.max_size
        
        # 高水準に達したら受付を停止
        if current_usage >= self.high_watermark:
            self.accepting = False
        
        # 低水準まで下がったら受付を再開
        elif current_usage <= self.low_watermark:
            self.accepting = True
        
        if not self.accepting:
            raise BackpressureException("System overloaded")
        
        self.queue.put(item, timeout=timeout)
    
    def get_pressure_signal(self):
        """上流システムへの圧力シグナル"""
        usage = self.queue.qsize() / self.max_size
        if usage < 0.5:
            return "GREEN"  # 正常
        elif usage < 0.8:
            return "YELLOW"  # 注意
        else:
            return "RED"  # 危険

class RecoveryController:
    def __init__(self, max_attempts=3, backoff_base=2, max_backoff=300):
        self.max_attempts = max_attempts
        self.backoff_base = backoff_base
        self.max_backoff = max_backoff
        self.recovery_history = defaultdict(list)
    
    def should_attempt_recovery(self, component_id):
        history = self.recovery_history[component_id]
        
        # 最大試行回数のチェック
        recent_attempts = [
            attempt for attempt in history
            if time.time() - attempt['timestamp'] < 3600  # 1時間以内
        ]
        
        if len(recent_attempts) >= self.max_attempts:
            return False, "Max recovery attempts reached"
        
        # バックオフ時間の計算
        if recent_attempts:
            last_attempt = recent_attempts[-1]
            backoff_time = min(
                self.backoff_base ** len(recent_attempts),
                self.max_backoff
            )
            
            if time.time() - last_attempt['timestamp'] < backoff_time:
                return False, f"In backoff period ({backoff_time}s)"
        
        return True, "Recovery allowed"
    
    def record_recovery_attempt(self, component_id, success):
        self.recovery_history[component_id].append({
            'timestamp': time.time(),
            'success': success
        })
        
        # 古い履歴の削除
        cutoff_time = time.time() - 86400  # 24時間
        self.recovery_history[component_id] = [
            attempt for attempt in self.recovery_history[component_id]
            if attempt['timestamp'] > cutoff_time
        ]

class EscalationManager:
    def __init__(self):
        self.escalation_rules = {
            'data_corruption': {
                'auto_recovery': False,
                'reason': 'Potential data loss requires manual verification'
            },
            'security_breach': {
                'auto_recovery': False,
                'reason': 'Security incidents require investigation'
            },
            'repeated_failures': {
                'threshold': 5,
                'timeframe': 3600,
                'reason': 'Pattern suggests underlying issue'
            },
            'cascade_risk': {
                'affected_components': 3,
                'reason': 'Multiple component failure requires coordination'
            }
        }
    
    def requires_human_intervention(self, incident):
        # データ破損やセキュリティ侵害は即座にエスカレーション
        if incident.type in ['data_corruption', 'security_breach']:
            return True, self.escalation_rules[incident.type]['reason']
        
        # 繰り返し障害のチェック
        if incident.failure_count > self.escalation_rules['repeated_failures']['threshold']:
            return True, self.escalation_rules['repeated_failures']['reason']
        
        # カスケード障害のリスク評価
        if len(incident.affected_components) >= self.escalation_rules['cascade_risk']['affected_components']:
            return True, self.escalation_rules['cascade_risk']['reason']
        
        return False, None

class AutomatedRunbook:
    def __init__(self):
        self.procedures = {}
    
    def register_procedure(self, incident_type, steps):
        """インシデントタイプに対する復旧手順を登録"""
        self.procedures[incident_type] = steps
    
    def execute_recovery(self, incident):
        if incident.type not in self.procedures:
            raise Exception(f"No procedure defined for {incident.type}")
        
        steps = self.procedures[incident.type]
        recovery_log = []
        
        for step in steps:
            try:
                # 前提条件のチェック
                if not self.check_preconditions(step.preconditions):
                    recovery_log.append({
                        'step': step.name,
                        'status': 'SKIPPED',
                        'reason': 'Preconditions not met'
                    })
                    continue
                
                # ステップの実行
                result = step.execute()
                
                # 成功条件の確認
                if self.verify_success(step.success_conditions):
                    recovery_log.append({
                        'step': step.name,
                        'status': 'SUCCESS',
                        'result': result
                    })
                else:
                    recovery_log.append({
                        'step': step.name,
                        'status': 'FAILED',
                        'result': result
                    })
                    
                    # 失敗時のロールバック
                    if step.rollback:
                        step.rollback()
                    
                    break
                    
            except Exception as e:
                recovery_log.append({
                    'step': step.name,
                    'status': 'ERROR',
                    'error': str(e)
                })
                break
        
        return recovery_log

# Webサーバー障害の復旧手順
web_server_recovery = [
    Step(
        name="Check process status",
        execute=lambda: subprocess.check_output(['systemctl', 'status', 'nginx']),
        preconditions=lambda: True,
        success_conditions=lambda: 'active (running)' in result
    ),
    Step(
        name="Restart web server",
        execute=lambda: subprocess.call(['systemctl', 'restart', 'nginx']),
        preconditions=lambda: disk_space_available() > 1024 * 1024 * 100,  # 100MB
        success_conditions=lambda: service_responding('http://localhost:80'),
        rollback=lambda: subprocess.call(['systemctl', 'stop', 'nginx'])
    ),
    Step(
        name="Verify configuration",
        execute=lambda: subprocess.check_output(['nginx', '-t']),
        preconditions=lambda: True,
        success_conditions=lambda: 'syntax is ok' in result
    ),
    Step(
        name="Clear cache if needed",
        execute=lambda: clear_nginx_cache(),
        preconditions=lambda: cache_corruption_detected(),
        success_conditions=lambda: verify_cache_cleared()
    )
]