RC: W10 D5 — Creating a monotonically incrementing sequence number

April 19, 2024

Today, I wanted to add a sequence number to each entry written to my engine. Those sequence numbers will later be used to create snapshots of the database (i.e. a stable view of the database at a particular point in time) and thus need to be monotonically increasing. So I implemented a SequenceNumberGenerator to yield values incrementing by 1 every time it is called. To add the sequence number to each record, I thus did the following:

class Record:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.sequence_number = next(SequenceNumberGenerator())

However, with this method, the generator is re-instantiated with every new record and thus, every record is assigned the same sequence number: 0. One way to solve the problem would have been to have a single generator instantiated at the top level (the LsmStorage class) and passed down at every call of the Record class (and all intermediary classes), but that would have been messy and error-prone. Instead, I decided to use the singleton pattern to ensure that only one instance of the generator was created and reused for every need.

I decided to create a decorator that would encapsulate the singleton. A decorator is simply a function that is applied to the class or function that it “decorates” (SequenceNumberGenerator in the example below), and that does it with a particular syntax: when @decorator is written above a class or function, the decorator function is applied to that class or function. Therefore, writing @decorator; class Decorated is equivalent to doing decorator(Decorated). Implementing the singleton pattern is relatively easy: I proceeded by creating a dictionary of class instances and, if the class instantiated is already in the dictionary, I use it (thereby creating only a single instance).

Here is what I came up with:

def singleton(cls):
    instances = {}

    def wrapper(*args, **kwargs):
        if cls not in instances:
            instances[cls] = cls(*args, **kwargs)
        return instances[cls]

    return wrapper


@singleton
class SequenceNumberGenerator:
    def __init__(self, start=0):
        self.current = start

    def __iter__(self):
        return self

    def __next__(self):
        current = self.current
        self.current += 1
        return current

This worked well: if two generators are instantiated, their value keeps is monotonically increasing, as expected:

def test_sequence_number_generator_is_a_singleton():
    # GIVEN
    generator1 = SequenceNumberGenerator()
    assert next(generator1) == 0
    assert next(generator1) == 1
    generator2 = SequenceNumberGenerator()

    # WHEN/THEN
    assert next(generator2) == 2
    assert next(generator1) == 3

I think I could definitely have stopped there. However, I was a little troubled with this behavior for my tests: basically, since I made it a singleton, all my tests used the same instance and thus, the exact sequence number for a given test would depend on the ordering of tests (if I add one additional test that creates a record, then the values for all subsequent tests are shifted by 1). I really want my tests to be independent of one another (mostly because it would not be very fun to have to update the sequence number of the tests asserting it every time I added, deleted or modified another one). Therefore, I thought of adding a reset method on my singleton that would be called before each test.

To do this, I needed to use a slightly more complex syntax: I wrapped the logic inside a SingletonWrapper class inheriting from the decorated class (SingleNumberGenerator). I also provided it with a __new__ method to handle instantiation and with a reset method to handle resetting the generator. Hereunder is the updated implementation I came up with:

def singleton(decorated_class):
    instances = {}

    class SingletonWrapper(decorated_class):
        def __new__(cls, *args, **kwargs):
            if decorated_class not in instances:
                instances[decorated_class] = super().__new__(decorated_class)
                instances[decorated_class].__init__(*args, **kwargs)
            return instances[decorated_class]

        @classmethod
        def reset(cls):
            if decorated_class in instances:
                del instances[decorated_class]

    return SingletonWrapper


@singleton
class SingleNumberGenerator:
    ...

In this code, SingletonWrapper inherits from decorated_class. Since the @singleton decorator is applied to SingleNumberGenerator, decorated_class in this case corresponds to SingleNumberGenerator. In other words, when instantiating SingleNumberGenerator, we obtain a regular SingleNumberGenerator object incremented with the reset method defined in the SingletonWrapper class. The reset method simply deletes the instance from the dictionary of available instances. As for the __new__ method, it does the same as the previous implementation: namely returning the already existing instance or creating a new one the first time. When creating a new instance, it first calls the creator of the decorated class (with super().__new__(decorated_class)) and then initialize the instance with the correct arguments (with instances[decorated_class].__init__(*args, **kwargs)).

The behavior of the reset method can then be tested as follows:

def test_sequence_number_generator_can_be_restarted():
    SequenceNumberGenerator.reset()
    # GIVEN
    generator1 = SequenceNumberGenerator()
    assert next(generator1) == 0
    assert next(generator1) == 1
    assert next(generator1) == 2

    # WHEN
    generator2 = SequenceNumberGenerator()
    SequenceNumberGenerator.reset()
    generator3 = SequenceNumberGenerator()

    # THEN
    assert next(generator1) == 3
    assert next(generator2) == 4
    assert next(generator3) == 0

As expected, generator1 and generator2 that were instantiated before the reset carry on incrementing, whereas generator3 which was instantiated after the reset start from 0. Victory! 🎉