Simple matchmaking algorithm for 2 player online game

Question

I am looking for a simple matchmaking algorithm for 2 player online game. Which one has better performance? (I use vps, centos and php)

1. User one sends a request to server for game and because there is no previous request there, it puts his username in a cached variable.Then user two sends a request and reads the cached variable, so user two clean that variable for the next request and starts a game with user one.

Cons of algorithm 1 : In simultaneous requests it is possible that two users pick the same user.

2. All users are added to a queue. Then a script that is executed every second matches the users.

Cons of algorithm 2 : Can cause performance issues as it is executed every second.

3. Is there a better algorithm?