Один из вариантов - хранить все данные в стандартном динамическом массиве, отсортированном по времени. Всякий раз, когда есть входящий запрос, вы добавляете его в конец массива.
Чтобы узнать, сколько запросов произошло за последний час, вы можете выполнить двоичный поиск по массиву, чтобы найти первый запрос, произошедший за час. Сравнение индекса этого элемента массива с общим количеством элементов даст вам общее количество запросов в этом временном окне.
Чтобы массив не становился слишком большим, можно использовать массив как растущий кольцевой буфер. Всякий раз, когда вам не хватает места в массиве, выполняйте двоичный поиск первого элемента в массиве, который произошел в течение последнего часа. Все элементы до этого могут быть отброшены. Если вы сохраняете массив как кольцевой буфер, вы можете эффективно за O (1) удалить все эти элементы, просто изменив начальную позицию, чтобы логически удалить их из буфера. Если вам все еще нужно больше места, вы можете удвоить размер кольцевого буфера и скопировать старые элементы. Если вы применяете политику постоянного копирования всего, если после удаления старых элементов (например, 75%) заполняется больше чем некоторая постоянная часть буфера, то это приводит к требованию амортизированного O (1) времени на вставку.
Короче говоря, вы получаете амортизированную O (1) вставку и O (log n) наихудших поисков того, сколько запросов было за последний час.
Надеюсь, это поможет!