Firebase：如何在游戏中匹配对手？

Question

我将会尽力进行翻译，以下是需要翻译的内容：

我正在实现一个社交棋类游戏。每个用户都可以创建新的游戏，他们需要等待系统找到对手。

当用户创建一个游戏时，他们需要指定一些限制条件，例如：他们想玩哪种颜色，并且对手的最低棋力。

对手可以匹配或不匹配。例如下面的这两个对手是匹配的：

// User 1 with rating 1700              // User 2 with rating 1800
// creates this game                    // creates this game
game: {                                 game: { 
  color: 'white',                         minRating: 1650
  minRating: 1600                       }
}                                       // User did not specify a preferred color,
                                        // meaning they do not care which color to play

如果用户1是系统中的第一个用户，并创建了他们的游戏，则他们需要等待。一旦用户2创建他们的游戏，他们应该立即与用户1匹配。

另一方面，下面的两个对手不会匹配，因为他们都想玩白棋。在这种情况下，他们都应该等待，直到有人创建一个带有color：'black'（或未指定颜色）和minRating的游戏，以满足要求。

// User 1 with rating 1700              // User 2 with rating 1800
// creates this game                    // creates this game
game: {                                 game: { 
  color: 'white',                         color: 'white'  
  minRating: 1600                         minRating: 1650
}                                       }

我关注的是当成千上万的用户同时创建新游戏时的情况。如何确保我在匹配对手时不会出现死锁？也就是说，如何防止 User 1、User 2 和 User 3 同时尝试找到对手并且他们的匹配算法返回了 User 99 的情况。如何从这种情况中恢复，并将 User 99 分配给其中一个用户？

您会如何利用 Firebase 的强大功能来实现这样的匹配系统？

- Misha Moroshko

---

你可能需要将你的问题分成两个部分，一是如何找到最佳对手，二是如何制作实际的技术匹配系统，以避免死锁问题。 - Lasse V. Karlsen

听起来你需要使用用户的评分和颜色作为他们的“优先级”，可以在主users节点中或专门的usersByRating或usersByRatingAndColor节点中实现。有了这个，您就可以使用 startAt 和 endAt 查找具有相似评分的用户。为了防止启动多个冲突的游戏，您需要使用 transaction。 - Frank van Puffelen

Answer 1

显然，起点应该是颜色，因为这是一个独特的要求。其他的似乎更像是加权结果，所以可以简单地增加或减少权重。

利用优先级进行最小/最大范围，并将每个范围保留在单独的“索引”中。然后获取每个范围的匹配项并创建一个联合。考虑这个结构：

/matches
/matches/colors/white/$user_id
/matches/ranking/$user_id (with a priority equal to ranking)
/matches/timezones/$user_id (with a priority of the GMT relationship)

现在需要查询，我只需获取每个类别中的匹配项，并通过匹配数量进行排名。我可以从颜色开始，因为这可能不是一个可选或相对评分：

var rootRef = new Firebase('.../matches');

var VALUE = {
   "rank": 10, "timezone": 5, "color": 0
}

var matches = []; // a list of ids sorted by weight
var weights = {}; // an index of ids to weights

var colorRef = rootRef.child('colors/black');
colorRef.on('child_added', addMatch);
colorRef.child('colors/black').on('child_removed', removeMatch);

var rankRef = rootRef.child('ranking').startAt(minRank).endAt(maxRank);
rankRef.on('child_added', addWeight.bind(null, VALUE['rank']));
rankRef.on('child_removed', removeWeight.bind(null, VALUE['rank']));

var tzRef = ref.child('timezone').startAt(minTz).endAt(maxTz);
tzRef.on('child_added', addWeight.bind(null, VALUE['timezone']));
tzRef.on('child_removed', removeWeight.bind(null, VALUE['timezone']));

function addMatch(snap) {
   var key = snap.name();
   weights[key] = VALUE['color'];
   matches.push(key);
   matches.sort(sortcmp);
}

function removeMatch(snap) {
   var key = snap.name();
   var i = matches.indexOf(key);
   if( i > -1 ) { matches.splice(i, 1); }
   delete weights[key]; 
}

function addWeight(amt, snap) {
   var key = snap.name();
   if( weights.hasOwnProperty(key) ) {
      weights[key] += amt;
      matches.sort(sortcmp);
   }
}

function removeWeight(amt, snap) {
   var key = snap.name();
   if( weights.hasOwnProperty(key) ) {
      weights[key] -= amt;
      matches.sort(sortcmp);
   }
}

function sortcmp(a,b) {
   var x = weights[a];
   var y = weights[b];
   if( x === y ) { return 0; }
   return x > y? 1 : -1;
}

好的，现在我给出了每个人在此用例中都会询问的内容-如何创建一个基本的where子句。然而，在这里适当的答案是应该由搜索引擎执行搜索。这不是简单的where条件。这是一种加权搜索，以找到最佳匹配，因为像颜色这样的字段是不可选的或仅仅是最佳匹配，而其他东西-例如排名-则是两个方向上最接近的匹配，而有些只是影响匹配的质量。

请查看闪光灯以进行简单的ElasticSearch集成。通过这种方法，您应该能够利用ES的出色加权工具、动态排序以及您需要进行正确匹配算法的所有其他内容。

关于死锁。我不会过多关注这一点，直到您每秒拥有数百个事务（即数十万用户竞争匹配）。将我们要写入以接受连接的路径拆分出来，并执行事务以确保只有一个人成功获取它。将其与读取数据分开，以使该路径上的锁定不会减慢处理速度。尽可能将事务保持在最小范围内（如果可能，则为单个字段）。

- Kato

---

嗨Kato，我觉得我没有解释清楚。不存在“最佳/最优对手”这样的东西。对手要么匹配，要么不匹配。你能否告诉我当多个客户端的匹配算法返回相同用户时应该如何处理呢？请参见我的更新问题。希望这样能让事情变得更容易些。 - Misha Moroshko

以上情况仍然可以进行一些轻微的调整来实现。我会给每个项目分配1个权重，并显示符合所有条件（例如具有3个权重）的那些项目。ElasticSearch仍然可以更好/更快地完成此任务，但这可以支持同时处理数千个匹配项。 - Kato

我增加了一些关于死锁的额外想法。 - Kato

谢谢Kato，感谢您的反馈！ - Misha Moroshko

Answer 2

在NoSQL环境下，特别是当你想匹配多个字段时，这将是一项具有挑战性的任务。对于您的情况，我建议设置一个简单的按颜色索引，并在颜色内存储参考游戏，优先级设置为最小评分。这样，您就可以按首选颜色查询游戏，并优先考虑最低评分。

indexes: {
  color:{
     white:{
        REF_WITH_PRIORITY_TO_RATING: true
     },
     black:{
        REF_WITH_PRIORITY_TO_RATING: true
     }
  }
}

如果您想在比赛开始时获得信息：

ref = new(Firebase)('URL');
query =ref.child('color_index/white/').startAt(minPriority);
query.on('child_added',function(snapshot){
  //here is your new game matching the filter
});

然而，如果您引入多个用于过滤游戏的字段，例如dropRate、timeZone、gamesPlayed等，则会变得更加复杂... 在这种情况下，您可以将索引嵌套得更深：

indexes: {
  GMT0: {
    color:{
       white:{
          REF_WITH_PRIORITY_TO_RATING: true
       },
       black:{
          REF_WITH_PRIORITY_TO_RATING: true
       },
  }
  GMT1: {
       // etc
  }
}

- webduvet