6

我正在实施一个社交国际象棋游戏。每个用户都可以创建一个新游戏，他们会等到系统为他们找到对手。

当用户创建游戏时，他们会指定约束：他们想玩的颜色，以及对手的最低国际象棋等级。

对手可以匹配也可以不匹配。例如，以下两个对手将匹配：

// 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
}                                       }

我的担忧与成千上万的用户同时创建新游戏的场景有关。如何确保在不造成僵局的情况下匹配对手？即当用户 1、用户 2 和用户 3 试图同时寻找对手并且他们的匹配算法返回用户 99 时，如何防止出现这种情况。如何从这种情况中恢复，仅将用户 99 分配给其中一个他们？

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

4

2 回答 2

7

起点的明显选择是颜色，因为这是一个排他性要求。其他的似乎更像加权结果，因此可以简单地增加或减少权重。

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

/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 条件。这是对最佳匹配的加权搜索，因为诸如颜色之类的字段不是可选的或仅仅是最佳匹配，而其他字段（可能排名）是任一方向上最接近的匹配，而有些字段只会影响匹配的质量。

查看flashlight以获得简单的 ElasticSearch 集成。通过这种方法，您应该能够利用 ES 强大的加权工具、动态排序以及执行正确匹配算法所需的一切。

关于死锁。在您每秒有数百个事务（即数十万用户竞争匹配）之前，我不会在这里过多关注。拆分我们将写入的路径以接受加入并进行交易以确保只有一个人成功获得它。将其与读取数据分开，以便该路径上的锁定不会减慢处理速度。将事务保持在最小大小（如果可能，单个字段）。

于 2014-07-30T14:14:11.603 回答
2

在 NoSQL 环境中这是一项具有挑战性的任务，尤其是如果您想匹配多个字段

在您的情况下，我将按颜色设置一个简单的索引，并在颜色内存储对游戏的引用，并将优先级设置为 minRating。这样您就可以按优先级为 minRating 的首选颜色查询游戏。

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
  }
}
于 2014-07-30T13:41:04.847 回答