Turn the bucket count into a knob, but keep cleaner wake-ups at a constant rate

6 files changed, 82 insertions, 19 deletions

diff --git a/DESIGN b/DESIGN
index ff37706..5abeb4a 100644
--- a/DESIGN
+++ b/DESIGN
@@ -16,7 +16,7 @@ A connection carries one request and closes. Keep-alive works and is rarely
 asked for.
 
 Statistics are approximate on purpose. Counters are per thread and summed
-when read, so a /stats read can under-report once. Nothing drifts.
+when read, so a /stats read can under-report once.
 
 
 Decisions
@@ -60,9 +60,44 @@ connections, the filter serves more requests than no filter, not fewer, so it
 is not the denial of service vector that FreeBSD-SA-02:26 once described.
 
 
+The torrent table is split into 2^OT_BUCKET_COUNT_BITS buckets, 1024 by
+default, set from the Makefile. Inserting a torrent opens a slot in a sorted
+vector, so the bytes moved grow with the bucket's occupancy. Insert cost per
+torrent, Linux:
+
+                2^10     2^12     2^14     2^16
+  200k        466 ns            439 ns
+  1M          834 ns   579 ns   529 ns
+  4M         2348 ns  1163 ns   770 ns   674 ns
+
+Re-announcing an existing torrent moves by under ten per cent over the same
+range, so the cost is paid while the torrent population is built and not in
+steady state. Below a few hundred thousand torrents there is nothing to win.
+2^14 captures most of the gain for two per cent more resident memory.
+
+The cleaner's wake rate does not follow the bucket count. A cap of ten wakes
+a second sets the sleep, and a wake cleans as many buckets as it must to
+finish a sweep in OT_CLEAN_INTERVAL_MINUTES. At the default bucket count that
+is one bucket every 117 ms.
+
+
 Paths not taken
 ---------------
 
+A keyed hash for the bucket index. Info hashes are SHA-1 output and already
+uniform, so it changes no distribution. It would buy resistance to deliberate
+bucket flooding and cost the ordering a full scrape depends on: buckets are
+ordered by hash prefix and sorted within, so walking them emits the sorted
+dictionary bencode wants, with no sort and no copy.
+
+Cache line padding for the per-bucket locks and vector headers. The
+contention it was meant to remove is not there. On glibc, where a 48-byte
+mutex straddles a line, padding gains 3 to 8 per cent, but gains as much at
+one thread where no false sharing can exist, and scaling from one to eight
+threads is identical either way. On FreeBSD, where eight 8-byte mutexes share
+a line and the risk should be highest, padding is 15 per cent slower at one
+thread and neutral to 6 per cent slower at four and eight.
+
 accf_http, the HTTP-aware accept filter. It duplicates a parser the tracker
 has anyway, puts more kernel code in the path, and holds a connection that
 sends "GET /" and stops, which accf_data hands straight over.
diff --git a/Makefile b/Makefile
index f124be8..993f0ae 100644
--- a/Makefile
+++ b/Makefile
@@ -20,6 +20,12 @@ STRIP?=strip
 #FEATURES+=-DWANT_DEV_RANDOM
 FEATURES+=-DWANT_FULLSCRAPE
 
+# Buckets the torrent table is split into, as a power of two, 8 to 16. More
+# buckets make inserting a new torrent cheaper and cost memory, which is worth
+# it for a tracker carrying millions of torrents and not for one carrying
+# thousands. DESIGN has the measurements.
+FEATURES+=-DOT_BUCKET_COUNT_BITS=10
+
 #FEATURES+=-D_DEBUG_HTTPERROR
 #FEATURES+=-D_DEBUG_RANDOMTORRENTS
 
diff --git a/ot_clean.c b/ot_clean.c
index e1d1971..f181e83 100644
--- a/ot_clean.c
+++ b/ot_clean.c
@@ -125,26 +125,34 @@ static void clean_sleep(void) {
   pthread_mutex_unlock(&g_clean_mutex);
 }
 
-/* Clean up all peers in current bucket, remove timedout pools and
- torrents */
+/* Clean up all peers in one bucket, remove timedout pools and torrents */
+static void clean_bucket(size_t bucket) {
+  ot_vector *torrents_list = mutex_bucket_lock((int)bucket);
+  size_t     toffs;
+  int        delta_torrentcount = 0;
+
+  for (toffs = 0; toffs < torrents_list->size; ++toffs) {
+    ot_torrent *torrent = ((ot_torrent *)(torrents_list->data)) + toffs;
+    if (clean_single_torrent(torrent)) {
+      vector_remove_torrent(torrents_list, torrent);
+      --delta_torrentcount;
+      --toffs;
+    }
+  }
+  mutex_bucket_unlock((int)bucket, delta_torrentcount);
+}
+
 static void *clean_worker(void *args) {
   (void)args;
   while (1) {
     size_t bucket = OT_BUCKET_COUNT;
-    while (bucket--) {
-      ot_vector *torrents_list = mutex_bucket_lock(bucket);
-      size_t     toffs;
-      int        delta_torrentcount = 0;
+    while (bucket) {
+      size_t todo = bucket < OT_CLEAN_BUCKETS_PER_WAKE ? bucket : OT_CLEAN_BUCKETS_PER_WAKE;
+
+      /* One bucket is locked at a time, however many a wake gets through */
+      while (todo--)
+        clean_bucket(--bucket);
 
-      for (toffs = 0; toffs < torrents_list->size; ++toffs) {
-        ot_torrent *torrent = ((ot_torrent *)(torrents_list->data)) + toffs;
-        if (clean_single_torrent(torrent)) {
-          vector_remove_torrent(torrents_list, torrent);
-          --delta_torrentcount;
-          --toffs;
-        }
-      }
-      mutex_bucket_unlock(bucket, delta_torrentcount);
       if (!g_opentracker_running)
         return NULL;
       clean_sleep();
diff --git a/ot_clean.h b/ot_clean.h
index e069ee0..0592791 100644
--- a/ot_clean.h
+++ b/ot_clean.h
@@ -9,8 +9,17 @@
 /* The amount of time a clean cycle should take */
 #define OT_CLEAN_INTERVAL_MINUTES 2
 
-/* So after each bucket wait 1 / OT_BUCKET_COUNT intervals */
-#define OT_CLEAN_SLEEP            (((OT_CLEAN_INTERVAL_MINUTES) * 60 * 1000000) / (OT_BUCKET_COUNT))
+/* How often the cleaner may wake. A full sweep takes OT_CLEAN_INTERVAL_MINUTES.
+   The clean operations per wake is goverend by OT_BUCKET_COUNT_BITS,
+   set by the Makefile.
+   At the default of 1024 buckets this works out at one bucket every
+   117 ms. */
+#define OT_CLEAN_MAX_WAKES_PER_SECOND 10
+
+#define OT_CLEAN_WAKE_BUDGET      ((OT_CLEAN_INTERVAL_MINUTES) * 60 * (OT_CLEAN_MAX_WAKES_PER_SECOND))
+#define OT_CLEAN_BUCKETS_PER_WAKE (((OT_BUCKET_COUNT) + (OT_CLEAN_WAKE_BUDGET) - 1) / (OT_CLEAN_WAKE_BUDGET))
+#define OT_CLEAN_WAKES            ((OT_BUCKET_COUNT) / (OT_CLEAN_BUCKETS_PER_WAKE))
+#define OT_CLEAN_SLEEP            (((OT_CLEAN_INTERVAL_MINUTES) * 60 * 1000000) / (OT_CLEAN_WAKES))
 
 void clean_init(void);
 void clean_deinit(void);
diff --git a/tests/t_mutex.c b/tests/t_mutex.c
index e54e2fa..c0c41cc 100644
--- a/tests/t_mutex.c
+++ b/tests/t_mutex.c
@@ -24,7 +24,7 @@ static void hash_for_bucket(ot_hash hash, int bucket) {
 }
 
 static void case_a_hash_names_its_bucket(void) {
-  static const int buckets[] = {0, 1, 2, 17, 511, 512, OT_BUCKET_COUNT - 1};
+  static const int buckets[] = {0, 1, 2, 17, OT_BUCKET_COUNT / 2 - 1, OT_BUCKET_COUNT / 2, OT_BUCKET_COUNT - 1};
   size_t           i;
 
   test_case("a hash is served by the bucket its leading bits name");
diff --git a/trackerlogic.h b/trackerlogic.h
index 338e4e6..7292d36 100644
--- a/trackerlogic.h
+++ b/trackerlogic.h
@@ -62,7 +62,12 @@ typedef struct {
 
 /* We maintain a list of 1024 pointers to sorted list of ot_torrent structs
  Sort key is, of course, its hash */
+/* Set from the Makefile, 8 to 16. More buckets means shorter vectors and a
+   cheaper insert, which only pays for a tracker carrying millions of
+   torrents; see DESIGN. */
+#ifndef OT_BUCKET_COUNT_BITS
 #define OT_BUCKET_COUNT_BITS          10
+#endif
 
 #define OT_BUCKET_COUNT               (1 << OT_BUCKET_COUNT_BITS)
 #define OT_BUCKET_COUNT_SHIFT         (32 - OT_BUCKET_COUNT_BITS)