kdb_stats.c

基于DHT的对等协议

/**
 * This program analyzes the keyauxdb files of all the vnodes of a
 * Chord ring, and outputs stats detailing how many keys each node is
 * missing in its local database, compared to all the keys that exist
 * in the network within the node's scope.
 *
 * You need to have a kdb file for each node in the ring, and you to
 * name them as follows: <node_id>.<type>.kdb.db.  Thus, the noauth
 * kdb for node fbc193dd04c4b653b878969a859b5d868a369b76 would be
 * called fbc193dd04c4b653b878969a859b5d868a369b76.n.kdb.db.
 *
 * To run it, simply run "./kdb_stats *.n.kdb.db" in the directory
 * with all the kdb files, which will produce the stats for all the
 * noauth side of things.
 *
 * The program will output (at its end) stats for each node of the form:
 *   
 * <node_id> <num_keys_in_scope> <num_keys_missing> <num_batches_of_missing_keys> <first_key_in_range_missing> <last_key_in_range_missing>
 **/

#include <async.h>
#include <itree.h>
#include <qhash.h>
#include <rxx.h>
#include <keyauxdb.h>
#include <id_utils.h>

struct node_rec {
  int pos;
  node_rec *next;
};

struct key_rec {
  chordID key;
  node_rec *nodes;
  itree_entry<key_rec> next;
};

struct node_stats {
  uint num_in_scope;
  uint num_missing;
  uint num_batch;
  bool last_missing;
  bool at_start;
  bool last_key_in_range;
};

typedef itree<chordID, key_rec, &key_rec::key, &key_rec::next> keytree;

//static const int NPREDS = 12;
static const int NPREDS = 2;

int main (int argc, char **argv) {

  if (argc <= 1) {
    warn << "Usage: kdb_stats kdbfiles\n";
    exit (0);
  }

  int num_nodes = argc-1;

  keytree sorted_nodes;
  keytree global_keys;
  keyauxdb **kdb = (keyauxdb **) malloc( sizeof(keyauxdb*)*num_nodes );
  vec<chordID> nodes;
  vec<str> nodes_str;

  for( int i = 0; i < num_nodes; i++ ) {
    str filename = argv[i+1];
    kdb[i] = New keyauxdb(filename);

    vec<str> parts;
    static const rxx slashy_rx( "\\/" );
    uint num_parts = split( &parts, slashy_rx, filename );
    rxx nodeid_rx( "(\\w+)\\.[cn]\\.kdb\\.db" );
    if( nodeid_rx.search( parts[num_parts-1] ) ) {
      chordID x;
      str2chordID( nodeid_rx[1], x );
      nodes.push_back(x);
      nodes_str.push_back(nodeid_rx[1]);
      key_rec *krec = New key_rec();
      krec->key = x;
      sorted_nodes.insert(krec);
    } else {
      fatal << "Could parse this file name: " << filename << ", " 
	    << parts[num_parts-1] << "\n";
    }

  }

  // now let's get us a sorted list of uniq-ified keys
  // (both global and per-node)
  uint num_keys = 0;
  uint num_keys_uniq = 0;
  for( int i = 0; i < num_nodes; i++ ) {
    keyauxdb *k = kdb[i];
    uint avail;
    uint at_a_time = 100000;
    const keyaux_t *keys;
    uint recno = 0;
    while( (keys = k->getkeys(recno, at_a_time, &avail)) && avail > 0 ) {
      for( uint j = 0; j < avail; j++ ) {
	key_rec *krec = New key_rec();
	krec->nodes = NULL;
	uint aux;
	keyaux_unmarshall( &(keys[j]), &krec->key, &aux );
	if( global_keys[krec->key] == NULL ) {
	  num_keys_uniq++;
	  global_keys.insert(krec);
	} else {
	  chordID k = krec->key;
	  delete krec;
	  krec = global_keys[k];
	}
	node_rec *n = New node_rec();
	n->pos = i;
	n->next = krec->nodes;
	krec->nodes = n;
	num_keys++;
      }
      recno += avail;
    }
    warn << "... " << num_keys_uniq << " " << num_keys << "\n";
    delete k;
    kdb[i] = NULL;
  }

  warn << "num_keys " << num_keys << ", num_keys_uniq " 
       << num_keys_uniq << "\n";

  // need the last one
  key_rec *last = NULL;
  key_rec *next = sorted_nodes.first();
  while( next != NULL ) {
    warn << next->key << " ";
    last = next;
    next = sorted_nodes.next(last);
  }
  warn << "\n";

  qhash<str, key_rec *> preds;
  qhash<str, node_stats *> stats;

  for( int i = 0; i < num_nodes; i++ ) {
    chordID curr_node = nodes[i];
    // find the nth predecessor
    int j = 1;
    key_rec *pred = sorted_nodes[curr_node];
    while( j < NPREDS ) {
      pred = sorted_nodes.prev(pred);
      if( pred == NULL ) {
	pred = last;
      }
      j++;
    }
    warn << "The last predecessor for " << curr_node << " is " 
	 << pred->key << "\n";

    preds.insert( nodes_str[i], pred );
    node_stats *s = New node_stats();
    s->num_in_scope = 0;
    s->num_missing = 0;
    s->num_batch = 0;
    s->last_missing = false;
    s->last_key_in_range = true;
    stats.insert( nodes_str[i], s );
  }

  key_rec *curr_key = global_keys.first();
  uint x = 0;
  while( curr_key != NULL ) {
    x++;
    for( int i = 0; i < num_nodes; i++ ) {
      chordID curr_node = nodes[i];
      str curr_node_str = nodes_str[i];
      node_stats *s = *(stats[curr_node_str]);
      // for each node, see if it belongs on the node, and if so, is it there?
      if( betweenrightincl( (*(preds[curr_node_str]))->key, curr_node, 
			    curr_key->key ) ) {
	s->num_in_scope++;
	bool found = false;
	node_rec *n = curr_key->nodes;
	while( n != NULL ) {
	  if( n->pos == i ) {
	    found = true;
	    break;
	  } else {
	    n = n->next;
	  }
	}
	if( !found ) {
	  s->num_missing++;
	  if( !s->last_missing ) {
	    s->num_batch++;
	    s->last_missing = true;
	  }
	} else {
	  s->last_missing = false;
	}

	// when this transitions from false to true, you've found the
	// beginning of the node's range
	if( !s->last_key_in_range ) {
	  s->last_key_in_range = true;
	  s->at_start = !found;
	}

      } else {
	s->last_key_in_range = false;
      }
    }
    curr_key = global_keys.next(curr_key);
  }

  for( int i = 0; i < num_nodes; i++ ) {
    node_stats *s = *(stats[nodes_str[i]]);
    warn << nodes[i] << " " << s->num_in_scope << " " 
	 << s->num_missing << " " << s->num_batch << " " << s->at_start
	 << " " << s->last_missing << "\n";
  }

}