Understanding the high-contention-allocator

Diggsey · November 17, 2021, 8:28pm

I was reading the HCA code in various implementation to get a better understanding of FDB, and came across this line:

apple/foundationdb/blob/master/bindings/python/fdb/directory_impl.py#L103

    
      
                      # subsequent risk of conflict for this transaction.
                      candidate = random.randrange(start, start + window)
          
          
            with tr_state.lock:
                          latest_counter = tr.snapshot.get_range(self.counters.range().start, self.counters.range().stop, limit=1, reverse=True)
                          candidate_value = tr[self.recent[candidate]]
                          tr.options.set_next_write_no_write_conflict_range()
                          tr[self.recent[candidate]] = b''
          
          
            latest_counter = [self.counters.unpack(k)[0] for k, _ in latest_counter]
                      if len(latest_counter) > 0 and latest_counter[0] > start:
                          break
          
          
            if candidate_value == None:
                          tr.add_write_conflict_key(self.recent[candidate])
                          return fdb.tuple.pack((candidate,))
          
          
def _window_size(self, start):
              # Larger window sizes are better for high contention, smaller sizes for
              # keeping the keys small.  But if there are many allocations, the keys
              # can't be too small.  So start small and scale up.  We don't want this

I was a bit confused because AIUI, all reads within the same transaction see a consistent snapshot of the database. How is it possible that latest_counter[0] > start could ever be True, when start is initialized using the same range query as latest_counter[0] and within the same transaction?

I was also wondering what the trade-offs of the HCA are, compared to eg. creating 256 counters and picking a random counter to increment and generate an ID (with the index of the counter shifted into the low bits).

ajbeamon · November 18, 2021, 6:41pm

I think the reason for that line is that another thread could use the same transaction and advance the window, in which case this may not become apparent until later in this allocation attempt. Any writes to the a transaction would be visible to later reads in that transaction, so you could see the counter advance here.

I haven’t thought about this extensively, but I guess one thing I notice is that the HCA uses a window quite a bit larger than 256. You could equally run more counters, though if the counter index becomes the low order bits we may have a reduced ability to generate shorter prefixes when the number of directories is small. That said, you should be able to easily get a good amount of concurrency while still starting at 2-byte integers.

Diggsey · November 18, 2021, 7:16pm

I see, that does make sense… Although that would be a slightly horrifying way to use a database transaction.