Создание отчетов, когда пользователь превысил лимит нажатий кнопок

Question

У меня есть функция, которая упоминалась в одном из моих предыдущих вопросов: Функция для расчета того, как часто пользователи нажимают кнопку

void onNewButtonPress(int64_t nanoseconds_timestamp, int32_t user_id);

Эта функция будет вызываться каждый раз пользователь с user_id нажимает кнопку. Где параметр nanoseconds_timestamp - это время в наносекундах с начала эпохи.

Моя задача - выполнить проверку ограничения скорости для каждого пользователя. У каждого пользователя свой лимит кликов. Предел скорости для каждого пользователя может быть получен с помощью следующей функции:

const struct rate_limit* getLimit(uint32_t userId);

getlimit вернет указатель на структуру Rate_limit

struct rate_limit
{
    uint32_t max;
    uint32_t milliseconds;
};

Где max - максимальное количество кликов, сделанных пользователем может составлять в интервале миллисекунд значение. Например, если max = 400 и миллисекунды = 200, то пользователь может сделать только 400 кликов в интервале 200 мс.

Когда пользователь нарушает ограничение, функция должна сообщить об этом, используя функцию отчета с прототипом следующим образом.

void report(uint32_t user_id);

Как бы вы, ребята, определяли, когда пользователь нарушает свой лимит. Ниже мое решение с комментариями. Я по-прежнему считаю, что может быть гораздо более умное и лучшее решение, и хотел бы услышать ваше мнение.

Детали моей реализации следующие

Я создал структуру, которая будет содержать информацию о каждой истории пользователя .

struct UserTrackingInfo
{
    /* Limit which is returned when a user clicks for the first time */
    const rate_limit* limit;

    /* Variable which will get incremented each time a user is making a click */
    uint32_t breachCount{0};

    /* Timestamp in nanoseconds of when breachPeriod started. Whenever a user clicks for the first time
     * this timestamp will be initialized
     * Time will be sliced in breach periods whose duration is equal to the max of the rate_limit */
    uint64_t breachPeriodStartTs{0};
};

Я создал карту, где ключом является user_id, а значением - UserTrackingInfo

std::map<int32_t, struct UserTrackingInfo > tInfo;

Это моя предлагаемая реализация функции onNewButtonPress.

void onNewButtonPress(uint64_t& nanoseconds_timestamp, int32_t user_id)
{
    auto &tref = tInfo[user_id];


    if (tref.breachPeriodStartTs == 0){
        /* if a user hasnt clicked before, get the limit for the user and initialize a breach period start time stamp */
        tref.limit = getLimit(user_id);
        tref.breachPeriodStartTs = nanoseconds_timestamp;
    }
    else
    {
        /* Increment how many times used clicked a button */
        tref.breachCount++;

        /* Get number of ns passed since the time when last period started */
        int64_t passed = nanoseconds_timestamp - tref.breachPeriodStartTs;

        /* If we reached a limit, report it */
        if (passed < (tref.limit->milliseconds * 1000)){
            if (tref.breachCount > tref.limit->max){
                report(user_id);
            }
            /* we dont start a new period yet */
        }
        else{
            /* If the limit hasnt been reached yet */
            /* User may have pressed after the end of the breach period. Or he didnt make any clicks for the duration of a couple of breach periods */

            /* Find number of breach measure periods that may have been missed */
            uint64_t num_periods = passed / (tref.limit->milliseconds * 1000);

            /* Get duration of the passed periods in nanoseconds */
            uint64_t num_periods_ns = num_periods * (tref.limit->milliseconds * 1000);

            /* Set the the start time of the current breach measure period */
            /* and reset breachCount */
            tref.breachPeriodStartTs = tref.breachPeriodStartTs + num_periods_ns;
            tref.breachCount = 1;
        }
    }
}

Answer 1

Я бы посчитал, сколько кликов пользователь делает за астрономическую секунду (так что не нужно сохранять и проверять начало периода кликов). Преимуществом является простота, но недостатком является то, что если пользователь начинает щелкать в конце секунды, то у него, скажем, будет 1000 кликов в течение оставшейся секунды плюс 1000 кликов в течение следующей секунды (т.е. он может сделать, например, 2000 кликов за 1,1. второй, но работает только первую секунду, следующие секунды будут правильно ограничены). Итак:

• Запишите количество кликов в std::map, это будет O (logN) для обновления, но может быть O (1) с std::unordered_map (требуется реализация хеширования) или std::vector ( требует, чтобы идентификаторы пользователей были непрерывными, но их было легко реализовать)
• Запишите, какие пользователи были активны в последнюю секунду в std::set (O (logN) вставить и удалить) или std::unordered_set (O (1) вставить и delete)
• Запишите наносекунду начала следующей секунды из текущей

В обработчике кликов вы сначала проверяете, началась ли новая секунда (это легко, проверьте, соответствует ли ваша временная метка после отметки времени следующей секунды). Если да, то сбросьте счетчики всех активных пользователей (это отслеживание активных пользователей предназначено для того, чтобы не тратить время на повторение всего std::map). Затем очистите активных пользователей.

Затем обработайте фактический щелчок. Получите запись с карты и обновите счетчик, проверьте, не превышен ли предел, и сделайте отчет, если это так.

Обратите внимание, что обработка начала следующей секунды - довольно сложная операция, и щелчок пользователя не будет обработан до тех пор, пока обрабатывается следующая секунда (может привести к задержке, если у вас много активных пользователей). Чтобы предотвратить это, вы должны создать новую функцию, которая обрабатывает новые секунды и создает некоторые события для начала новой секунды, вместо того, чтобы обрабатывать все в обработчике кликов.

struct ClicksTrackingInfo {
    uint32_t clicksCount;
    uint32_t clicksQuotaPerSec;
};

using UserId_t = int32_t; // user id type
std::set<UserId_t> activeUsers; // users who ever clicked in this second -- O(logN) to update

std::map<UserId_t, ClicksTrackingInfo> clicksPerCurrentSecond; // clicks counts -- O(logN) to update

uint64_t nextSecondTs; // holds nanosecond for beginning of the next second, e.g. if it's a 15th second then nextSecondTs == 16*1000*1000*1000

void onNewButtonPress(uint64_t& nanosecondsTimestamp, UserId_t userId)
{
    // first find out if a new second started
    if (nanosecondsTimestamp > nextSecondTs) {
        nextSecondTs = (nanosecondsTimestamp / 1000000000 + 1) * 1000000000; // leave only seconds part of next second
        // clear all records from active users of last second
        for (auto userId : activeUsers) {
             clicksPerCurrentSecond[userId].clicksCount = 0;   
        }
        activeUsers.clear(); // new second, no users yet
    }
    // now process current click by the user
    auto& [clicksCount, clicksLimit] = clicksPerCurrentSecond[userId]; // C++17 syntax
    ++clicksCount;
    if (clicksCount > clicksLimit) {
        report(userId);
        // return; // possibly deny this click
    }
    activeUsers.emplace(userId); // remember this user was active in current second
    // doClick(); // do the click action
}