我正在寻找一个 java 并发习语来匹配具有最高吞吐量的大量元素。
考虑一下我有来自多个线程的“人”。每个“人”都在寻找匹配项。当它找到另一个等待匹配的“人”时，它们都被分配给彼此并被删除以进行处理。
我不想锁定一个大结构来改变状态。考虑 Person 有 getMatch 和 setMatch。在提交之前，每个人的#getMatch 为空。但是，当它们解锁（或被钓）时，它们要么已经过期，因为它们等待匹配的时间太长，要么#getMatch 不为空。
保持高吞吐量的一些问题是，如果 PersonA 与 PersonB 同时提交。它们相互匹配，但 PersonB 也匹配已经等待的 PersonC。PersonB 的状态在提交时更改为“可用”。但是当 PersonB 与 PersonC 匹配时，PersonA 需要不意外地得到 PersonB。说得通？另外，我想以一种异步工作的方式来做到这一点。换句话说，我不希望每个提交者都必须在具有 waitForMatch 类型事物的线程上保留一个 Person。
同样，我不希望请求必须在单独的线程上运行，但如果有一个额外的 match maker 线程也没关系。
似乎应该有一些成语，因为它似乎是很常见的事情。但是我的谷歌搜索已经干涸（我可能使用了错误的术语）。
更新
有几件事让我很难解决这个问题。一个是我不想在内存中有对象，我希望所有等待的候选人都在 redis 或 memcache 或类似的东西中。另一个是任何人都可以有几个可能的匹配项。考虑如下接口：
person.getId(); // lets call this an Integer
person.getFriendIds(); // a collection of other person ids
然后我有一个看起来像这样的服务器：
MatchServer:
submit( personId, expiration ) -> void // non-blocking returns immediately
isDone( personId ) -> boolean // either expired or found a match
getMatch( personId ) -> matchId // also non-blocking
这是一个休息界面，它会使用重定向，直到你得到结果。我的第一个想法是在 MatchServer 中有一个缓存，它由诸如 redis 之类的东西支持，并为当前被锁定并被操作的对象有一个并发的弱值哈希映射。每个 personId 都将被一个具有已提交、匹配和过期等状态的持久状态对象包装。
追到现在？很简单，提交代码完成了最初的工作，它是这样的：
public void submit( Person p, long expiration ) {
MatchStatus incoming = new MatchStatus( p.getId(), expiration );
if ( !tryMatch( incoming, p.getFriendIds() ) )
cache.put( p.getId(), incoming );
}
public boolean isDone( Integer personId ) {
MatchStatus status = cache.get( personId );
status.lock();
try {
return status.isMatched() || status.isExpired();
} finally {
status.unlock();
}
}
public boolean tryMatch( MatchStatus incoming, Iterable<Integer> friends ) {
for ( Integer friend : friends ) {
if ( match( incoming, friend ) )
return true;
}
return false;
}
private boolean match( MatchStatus incoming, Integer waitingId ) {
CallStatus waiting = cache.get( waitingId );
if ( waiting == null )
return false;
waiting.lock();
try {
if ( waiting.isMatched() )
return false;
waiting.setMatch( incoming.getId() );
incoming.setMatch( waiting.getId() );
return true
} finally {
waiting.unlock();
}
}
所以这里的问题是，如果两个人同时进来并且他们是他们唯一的匹配项，他们就不会找到对方。比赛条件对吗？我能看到解决它的唯一方法是同步“tryMatch()”。但这会扼杀我的吞吐量。我不能让 tryMatch 无限循环，因为我需要这些调用非常短。
那么有什么更好的方法来解决这个问题呢？我想出的每一个解决方案都一次次迫使人们集中在一起，这对吞吐量来说并不是很好。例如，创建一个后台线程并使用一个阻塞队列来一次放置和接收一个传入的队列。
任何指导将不胜感激。