Какая была самая интересная задача с горутинами?

Какая была самая интересная задача с горутинами

Горутины — это концепция из Go, но в Java мы работаем с потоками и асинхронностью. Расскажу о интересной задаче с многопоточностью.

Задача: Поиск соперника в реальном времени (matching algorithm)

Контекст: Приложение для онлайн-игр. Нужно быстро найти двух игроков примерно одного уровня.

Требования:

• Два игрока спарены за 5-15 секунд
• Race condition prevention
• 100K игроков одновременно

Решение через Spring

@Service
@Slf4j
public class PlayerMatchingService {
    
    private final SortedMap<Integer, Queue<SearchingPlayer>> ratingBuckets;
    private final ReentrantReadWriteLock ratingLock;
    
    public PlayerMatchingService() {
        this.ratingBuckets = Collections.synchronizedSortedMap(
            new TreeMap<>()
        );
        this.ratingLock = new ReentrantReadWriteLock();
    }
    
    public void addPlayerToQueue(SearchingPlayer player) {
        ratingLock.writeLock().lock();
        try {
            int bucket = (player.getRating() / 100) * 100;
            
            ratingBuckets.computeIfAbsent(bucket, k -> 
                new ConcurrentLinkedQueue<>()
            ).offer(player);
            
            log.info("Player {} added to rating bucket {}", 
                player.getPlayerId(), bucket);
        } finally {
            ratingLock.writeLock().unlock();
        }
    }
    
    public Optional<GameMatch> findOpponent(SearchingPlayer player) {
        ratingLock.readLock().lock();
        try {
            int targetRating = player.getRating();
            
            for (int offset = 0; offset <= 500; offset += 100) {
                if (tryMatchInBucket(targetRating + offset, player)) {
                    return Optional.of(createMatch(player));
                }
                
                if (offset > 0 && 
                    tryMatchInBucket(targetRating - offset, player)) {
                    return Optional.of(createMatch(player));
                }
            }
            
            return Optional.empty();
        } finally {
            ratingLock.readLock().unlock();
        }
    }
    
    private boolean tryMatchInBucket(int ratingBucket, SearchingPlayer player) {
        Queue<SearchingPlayer> bucket = ratingBuckets.get(ratingBucket);
        if (bucket == null || bucket.isEmpty()) {
            return false;
        }
        
        SearchingPlayer opponent = bucket.poll();
        if (opponent != null) {
            log.info("Match found: {} vs {}", 
                player.getPlayerId(), opponent.getPlayerId());
            return true;
        }
        return false;
    }
}

WebSocket контроллер

@RestController
@RequestMapping("/api/match")
@Slf4j
public class MatchController {
    
    private final PlayerMatchingService matchingService;
    private final SimpMessagingTemplate messagingTemplate;
    
    @PostMapping("/queue")
    public ResponseEntity<Void> joinQueue(@RequestBody SearchingPlayer player) {
        matchingService.addPlayerToQueue(player);
        
        Executors.newSingleThreadScheduledExecutor().schedule(() -> {
            Optional<GameMatch> match = matchingService.findOpponent(player);
            
            if (match.isPresent()) {
                messagingTemplate.convertAndSendToUser(
                    String.valueOf(player.getPlayerId()),
                    "/queue/match-found",
                    match.get()
                );
            }
        }, 5, TimeUnit.SECONDS);
        
        return ResponseEntity.ok().build();
    }
}

Проблемы и решения

1. Race Condition при поиске

Проблема: Два потока выбирают одного опонента.

Решение: SELECT FOR UPDATE в БД

public Optional<GameMatch> findOpponentWithLock(Long playerId) {
    Player player = playerRepository.findByIdForUpdate(playerId);
    
    Optional<Player> opponent = playerRepository
        .findFirstInQueue(player.getRating());
    
    if (opponent.isPresent()) {
        GameMatch match = new GameMatch(player, opponent.get());
        gameMatchRepository.save(match);
        return Optional.of(match);
    }
    
    return Optional.empty();
}

2. Потокобезопасность очереди

// Плохо
Queue<Player> queue = new LinkedList<>();
queue.add(player);

// Хорошо
Queue<Player> queue = new ConcurrentLinkedQueue<>();
queue.offer(player);

3. Deadlock при обновлении рейтинга

// Плохо
synchronized (player1) {
    synchronized (player2) {
        player1.addWin();
        player2.addLoss();
    }
}

// Хорошо — консистентный порядок
private void updateRatings(Player winner, Player loser) {
    Player first = winner.getId() < loser.getId() ? winner : loser;
    Player second = winner.getId() < loser.getId() ? loser : winner;
    
    synchronized (first) {
        synchronized (second) {
            winner.addWin();
            loser.addLoss();
        }
    }
}

Оптимизированное решение

@Service
@Slf4j
public class OptimizedMatchingService {
    
    private final NavigableMap<Integer, Queue<SearchingPlayer>> queues;
    private final ReentrantReadWriteLock lock;
    
    public OptimizedMatchingService() {
        this.queues = new ConcurrentSkipListMap<>();
        this.lock = new ReentrantReadWriteLock();
    }
    
    public void addPlayer(SearchingPlayer player) {
        lock.writeLock().lock();
        try {
            int bucket = bucketize(player.getRating());
            queues.computeIfAbsent(bucket, k -> 
                new ConcurrentLinkedQueue<>()
            ).offer(player);
        } finally {
            lock.writeLock().unlock();
        }
    }
    
    public Optional<Pair<SearchingPlayer, SearchingPlayer>> findMatch(
            SearchingPlayer player) {
        lock.readLock().lock();
        try {
            int rating = player.getRating();
            
            for (int bucket : queues.keySet()) {
                if (Math.abs(bucket - rating) <= 300) {
                    Queue<SearchingPlayer> queue = queues.get(bucket);
                    
                    SearchingPlayer opponent = queue.peek();
                    if (opponent != null && opponent.getPlayerId() != player.getPlayerId()) {
                        queue.poll();
                        return Optional.of(Pair.of(player, opponent));
                    }
                }
            }
            
            return Optional.empty();
        } finally {
            lock.readLock().unlock();
        }
    }
    
    private int bucketize(int rating) {
        return (rating / 100) * 100;
    }
}

Результаты оптимизации

До оптимизации:

• Поиск соперника: 100-200ms
• Пиковая нагрузка: 10K игроков

После оптимизации:

• Поиск соперника: 5-10ms
• Пиковая нагрузка: 100K игроков

Ключевые моменты

1. ReadWriteLock — много читают (поиск), редко пишут
2. Bucketing — уменьшить диапазон поиска
3. ConcurrentCollections — избежать явной синхронизации
4. Atomic операции — гарантировать целостность
5. WebSocket — реальное обновление UI

Почему это была интересная задача:

• Глубокое понимание многопоточности
• Performance был критичен (100K+)
• Race conditions были трудноловимы
• Оптимизация структуры данных и синхронизации