Firebase:Wie kombiniere ich Gegner in einem Spiel?

Question

Ich implementieren ein soziales Schachspiel.Jeder Benutzer kann ein neues Spiel erstellen und wartet, bis das System einen Gegner für ihn findet.

Wenn Benutzer ein Spiel erstellen, legen sie Einschränkungen fest:Farbe, die sie gerne spielen würden, und die minimale Schachwertung des Gegners.

Gegner können entweder übereinstimmen oder nicht übereinstimmen. Beispielsweise passen die folgenden zwei Gegner zusammen:

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

Wenn also Benutzer 1 der erste Benutzer im System ist und sein Spiel erstellt hat, wartet er.Sobald Benutzer 2 sein Spiel erstellt, sollte er sofort Benutzer 1 zugeordnet werden.

Auf der anderen Seite werden die beiden folgenden Gegner nicht zusammenpassen, weil sie beide mit Weiß spielen wollen.In diesem Fall sollten beide warten, bis jemand anderes ein Spiel damit erstellt color: 'black' (oder Farbe nicht angegeben) und minRating das würde den Anforderungen entsprechen.

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

Meine Bedenken bezogen sich auf Szenarien, in denen Tausende von Benutzern gleichzeitig neue Spiele erstellen.Wie stelle ich sicher, dass ich Gegner treffe, ohne Deadlocks zu verursachen?d.h.Wie verhindere ich Szenarien, in denen Benutzer 1, Benutzer 2 und Benutzer 3 gleichzeitig versuchen, einen Gegner zu finden, und ihre Matching-Algorithmen Benutzer 99 zurückgeben?Wie kann ich mich von diesem Szenario erholen, indem ich Benutzer 99 nur einem von ihnen zuweise?

Wie würden Sie die Leistungsfähigkeit von Firebase nutzen, um ein solches Matching-System zu implementieren?

Answer 1

In einer NoSQL-Umgebung ist dies eine anspruchsvolle Aufgabe, insbesondere wenn Sie mehrere Felder abgleichen möchten

In Ihrem Fall würde ich einen einfachen Index nach Farbe einrichten und innerhalb der Farbe den Verweis auf das Spiel speichern, wobei die Priorität auf minRating gesetzt ist.Auf diese Weise können Sie die Spiele nach der bevorzugten Farbe mit der Priorität minRating abfragen.

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

Wenn Sie Informationen erhalten möchten, wann immer das Spiel das Spiel eröffnet:

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
});

Dies würde jedoch komplexer werden, wenn Sie beispielsweise mehrere Felder zum Filtern der Spiele einführen würden dropRate, timeZone, 'gamesPlayed' etc...In diesem Fall können Sie die Indizes tiefer verschachteln:

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

Answer 2

Die naheliegende Wahl als Ausgangspunkt wäre die Farbe, da es sich dabei um eine ausschließliche Anforderung handelt.Die anderen scheinen eher gewichtete Ergebnisse zu sein, sodass diese einfach die Gewichtung erhöhen oder verringern könnten.

Nutzen Sie Prioritäten für Min/Max-Bereiche und bewahren Sie jeden in einem separaten „Index“ auf.Schnappen Sie sich dann die Streichhölzer für jeden und erstellen Sie eine Vereinigung.Betrachten Sie diese Struktur:

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

Um nun eine Abfrage durchzuführen, würde ich einfach die Übereinstimmungen in jeder Kategorie auswählen und sie nach der Anzahl der Übereinstimmungen ordnen.Ich kann mit den Farben beginnen, da dies vermutlich keine optionale oder relative Bewertung ist:

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

Okay, jetzt habe ich angegeben, was jeder in diesem Anwendungsfall verlangt – wie man eine rudimentäre Where-Klausel erstellt.Die passende Antwort hier ist jedoch, dass die Suche von einer Suchmaschine durchgeführt werden sollte.Dies ist keine einfache Where-Bedingung.Dies ist eine gewichtete Suche nach den besten Übereinstimmungen, da Felder wie die Farbe nicht optional oder einfach nur das sind am besten Übereinstimmung, während andere – vielleicht in der Rangfolge – in beide Richtungen am ehesten übereinstimmen, während andere sich einfach auf die Übereinstimmung auswirken Qualität des Spiels.

Kasse Taschenlampe für eine einfache ElasticSearch-Integration.Mit diesem Ansatz sollten Sie in der Lage sein, die großartigen Gewichtungstools, die dynamische Sortierung und alles andere, was Sie zur Durchführung eines ordnungsgemäßen Matching-Algorithmus benötigen, von ES zu nutzen.

Bezüglich Deadlocks.Ich würde hier nicht zu viel Fokus darauf legen, bis Sie Hunderte von Transaktionen pro Sekunde haben (d. h.Hunderttausende Benutzer konkurrieren um Spiele).Teilen Sie den Pfad auf, in den wir schreiben, um einen Beitritt anzunehmen und eine Transaktion durchzuführen, um sicherzustellen, dass nur eine Person erfolgreich ist, ihn zu erhalten.Halten Sie es von den gelesenen Daten getrennt, damit die Sperre auf diesem Pfad die Verarbeitung nicht verlangsamt.Halten Sie die Transaktion auf eine minimale Größe (möglichst ein einzelnes Feld).