title: Concurrently Pair Matches
body: <p>I'm looking for a java concurrency idiom to pair matches with a large number elements with the highest throughput.</p>
  
  <p>Consider I have "people" coming in from multiple threads. Each "person" is looking for a match. When it finds another waiting "person" it matches with they are both assigned to each other and removed for processing.</p>
  
  <p>I don't want to lock a big structure to change states. Consider Person has getMatch and setMatch. Before being submitted each person's #getMatch is null. But when they unblocked (or are fished) they either have expired because they waited to long for a match or #getMatch is non null.</p>
  
  <p>Some problems with keeping high through put is that if PersonA is submitted at the same time as PersonB. They match each other but PersonB also matches already waiting PersonC. PersonB's state changes to "available" when they are submitted. But PersonA needs to not accidentally get PersonB while PersonB is being matched with PersonC. Make sense? Also, I want to do this in a way that works asynchronously. In other words, I don't want each submitter to have to hold on to a Person on a thread with a waitForMatch type thing.</p>
  
  <p>Again, I dont want requests to have to run on separate threads, but it's okay if there is one additional match maker thread.</p>
  
  <p>Seems like there should be some idioms for this as it appears to be a pretty common thing. But my google searches have come up dry (I may be using the wrong terms). </p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>There are a couple of things that make this problem hard for me. One is that I don't want to have objects in memory, I'd like to have all waiting candidates in redis or memcache or something like that. The other is that any person could have several possible matches. Consider an interface like the following:</p>
  
  <pre><code>person.getId();         // lets call this an Integer
  person.getFriendIds();  // a collection of other person ids
  </code></pre>
  
  <p>Then I have a server that looks something like this:</p>
  
  <pre><code>MatchServer:
     submit( personId, expiration ) -&gt; void // non-blocking returns immediately
     isDone( personId ) -&gt; boolean          // either expired or found a match
     getMatch( personId ) -&gt; matchId        // also non-blocking
  </code></pre>
  
  <p>This is for a rest interface and it would use redirects until you got to the result. My first thought was to just have a Cache in MatchServer that was backed by something like redis and has a concurrent weak value hash map for objects that were currently locked and being acted on. Each personId would be wrapped by a persistent state object with states like submitted, matched, and expired. </p>
  
  <p>Following so far? Pretty simple, the submit code did the initial work, it was something like this:</p>
  
  <pre><code>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&lt;Integer&gt; 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();
      }
  }
  </code></pre>
  
  <p>So the problem here is that if two people come in at the same time and they are their only matches they wont find each other. A race condition right? The only way I could see to solve it was to synchronize "tryMatch()". But that kills my throughput. I can't have tryMatch indefinitely loop because I need these to be very short calls. </p>
  
  <p>So what is a better way to approach this? Every solution I come up with forces people in one at a time which isn't great for throughput. For example, creating a background thread and using a blocking queue for putting and taking incoming one at a time.</p>
  
  <p>Any guidance would be greatly appreciated.</p>