Как спроектировать окно времени подсчета
Временное окно обычно используется для отображения некоторой информации в реальном времени.Например, чтобы поддерживать пятиминутное временное окно сведений о транзакции, вам необходимо записать текущее время, все сведения о транзакции до пяти минут, а данные до пяти минут будут потеряны. .
Простая реализация заключается в использовании очереди, и новые данные добавляются в голову; в то же время запускается поток, чтобы непрерывно спрашивать, истек ли срок действия данных в конце очереди, и если он истекает, он будет отброшен.
Другой сценарий требует использования данных в этом временном окне для расчета, например, для расчета суммы притока и оттока средств в пятиминутной транзакции, Если вышеописанный метод все еще используется, в чем будет проблема?
- Если временное окно велико, необходимо хранить большое количество подробных данных.
- Нашей главной заботой является приток и отток средств; сохранение этих подробных данных перевешивает прибыль.
- Каждый раз, когда просроченные данные добавляются или удаляются, производительность потребления входящих и исходящих потоков рассчитывается в режиме реального времени.
Есть ли сложная реализация для этого специального сценария?
I. Схематический дизайн
1. Метод удаления опроса на основе очереди
Разделите временное окно на временные отрезки один за другим и запишите общий приток и отток средств в каждом временном отрезке, и тогда общий приток и отток будет суммой притока и оттока всех временных отрезков.
Добавлены данные:
- Если он не пересекает квант времени, обновить значение заголовка очереди
- Если он охватывает временные интервалы, добавьте заголовок очереди
удалить данные:
- Опрос задач, чтобы определить, истек ли срок действия хвоста очереди
- Если срок действия хвоста очереди истекает, хвост очереди будет удален.В это время, если данные головы очереди не добавляются в расчет, его также необходимо добавить в расчет.
2. Удаление на основе очереди при добавлении
По сравнению с предыдущим методом опроса, этот сценарий применения отличается: только при добавлении новых данных может быть обеспечена точность данных, а задача опроса не требуется для удаления просроченных данных.
Проще говоря, в некоторых сценариях (например, чтобы гарантировать, что данные не поступают с перерывами, то есть по крайней мере одни данные приходят в каждый временной срез), я надеюсь, что данные моего временного окна управляются вновь добавленными данными. .продлить
Добавлены данные:
- Если кванта времени нет, обновите значение заголовка очереди.
- Через временные срезы вставьте новый и удалите старые данные
II. Реализация временного окна на основе массива
Для второго типа выше дана простая реализация на основе массивов.В этой статье в основном представлены базовые схемы временного окна и метод реализации.Конечно, также требуются сложные случаи.Например, приток и отток средств выше, I It необходимо рассчитать временные окна 5 минут, 10 минут, 30 минут, 1 час, 3 часа, 6 часов, 12 часов и 24 часа соответственно Как этого добиться? Можно ли использовать одну очередь для удовлетворения всех расчетов временного окна? О них будет рассказано в следующей статье
1. Калькулятор колеса времени
Легче понять предыдущий способ использования очереди, почему здесь используется метод массива?
- Фиксированная длина, чтобы избежать частого добавления и удаления объектов
- Легко найти и обновить данные
Во-первых, реализовать калькулятор колеса времени для получения данных с истекшим сроком действия, которые необходимо удалить в соответствии с поступающим временем.
@Data
public class TimeWheelCalculate {
private static final long START = 0;
private int period;
private int length;
/**
* 划分的时间片个数
*/
private int cellNum;
private void check() {
if (length % period != 0) {
throw new IllegalArgumentException(
"length % period should be zero but not! now length: " + length + " period: " + period);
}
}
public TimeWheelCalculate(int period, int length) {
this.period = period;
this.length = length;
check();
this.cellNum = length / period;
}
public int calculateIndex(long time) {
return (int) ((time - START) % length / period);
}
/**
* 获取所有过期的时间片索引
*
* @param lastInsertTime 上次更新时间轮的时间戳
* @param nowInsertTime 本次更新时间轮的时间戳
* @return
*/
public List<Integer> getExpireIndexes(long lastInsertTime, long nowInsertTime) {
if (nowInsertTime - lastInsertTime >= length) {
// 已经过了一轮，过去的数据全部丢掉
return null;
}
List<Integer> removeIndexList = new ArrayList<>();
int lastIndex = calculateIndex(lastInsertTime);
int nowIndex = calculateIndex(nowInsertTime);
if (lastIndex == nowIndex) {
// 还没有跨过这个时间片，则不需要删除过期数据
return Collections.emptyList();
} else if (lastIndex < nowIndex) {
for (int tmp = lastIndex; tmp < nowIndex; tmp++) {
removeIndexList.add(tmp);
}
} else {
for (int tmp = lastIndex; tmp < cellNum; tmp++) {
removeIndexList.add(tmp);
}
for (int tmp = 0; tmp < nowIndex; tmp++) {
removeIndexList.add(tmp);
}
}
return removeIndexList;
}
}
Реализация этого калькулятора относительно проста, во-первых, указать длину временного окна (длину), временной интервал (период), который в основном обеспечивает два метода.
-
calculateIndexПо текущему времени определить индекс просроченных данных в массиве -
getExpireIndexesВ соответствии с последним временем вставки и текущим временем вставки вычислите индекс всех просроченных данных между двумя временами вставки.
2. Контейнер колеса времени
Данные под временным окном сохраняются в контейнере, включая данные реального времени, и массив из n временных срезов в прошлом, основным ядром которого является необходимость оценки при добавлении новых данных.
- Если он охватывает временные интервалы, удалите данные с истекшим сроком действия, обновите данные в реальном времени и обновите общее количество
- Если временной интервал отсутствует, просто обновите данные в реальном времени напрямую.
@Data
public class TimeWheelContainer {
private TimeWheelCalculate calculate;
/**
* 历史时间片计数，每个时间片对应其中的一个元素
*/
private int[] counts;
/**
* 实时的时间片计数
*/
private int realTimeCount;
/**
* 整个时间轮计数
*/
private int timeWheelCount;
private Long lastInsertTime;
public TimeWheelContainer(TimeWheelCalculate calculate) {
this.counts = new int[calculate.getCellNum()];
this.calculate = calculate;
this.realTimeCount = 0;
this.timeWheelCount = 0;
this.lastInsertTime = null;
}
public void add(long now, int amount) {
if (lastInsertTime == null) {
realTimeCount = amount;
lastInsertTime = now;
return;
}
List<Integer> removeIndex = calculate.getExpireIndexes(lastInsertTime, now);
if (removeIndex == null) {
// 两者时间间隔超过一轮，则清空计数
realTimeCount = amount;
lastInsertTime = now;
timeWheelCount = 0;
clear();
return;
}
if (removeIndex.isEmpty()) {
// 没有跨过时间片，则只更新实时计数
realTimeCount += amount;
lastInsertTime = now;
return;
}
// 跨过了时间片，则需要在总数中删除过期的数据，并追加新的数据
for (int index : removeIndex) {
timeWheelCount -= counts[index];
counts[index] = 0;
}
timeWheelCount += realTimeCount;
counts[calculate.calculateIndex(lastInsertTime)] = realTimeCount;
lastInsertTime = now;
realTimeCount = amount;
}
private void clear() {
for (int i = 0; i < counts.length; i++) {
counts[i] = 0;
}
}
}
3. Тест
Главное убедиться, что явных проблем с приведенной выше реализацией нет, а почему явные проблемы есть?
- Глубоко укоренившиеся ошибки легче выявить при реальном использовании.
public class CountTimeWindow {
public static void main(String[] args) {
TimeWheelContainer timeWheelContainer = new TimeWheelContainer(new TimeWheelCalculate(2, 20));
timeWheelContainer.add(0, 1);
Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 0, "first");
timeWheelContainer.add(1, 1);
Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 0, "first");
timeWheelContainer.add(2, 1);
Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 2, "second");
Assert.isTrue(timeWheelContainer.getCounts()[0] == 2, "second");
for (int i = 3; i < 20; i++) {
timeWheelContainer.add(i, 1);
System.out.println("add index: " + i + " count: " + timeWheelContainer.getTimeWheelCount());
}
// 刚好一轮
timeWheelContainer.add(20, 3);
Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 20, "third");
timeWheelContainer.add(21, 3);
Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 20, "third");
// 减去过期的那个数据
timeWheelContainer.add(22, 3);
Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 26 - 2, "fourth");
Assert.isTrue(timeWheelContainer.getCounts()[0] == 6, "fourth");
timeWheelContainer.add(26, 3);
Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 24 - 2 - 2 + 3, "fifth");
System.out.println(Arrays.toString(timeWheelContainer.getCounts()));
timeWheelContainer.add(43, 3);
System.out.println(Arrays.toString(timeWheelContainer.getCounts()));
Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 6, "six");
}
}
III. Другое
1. Серый блог: https://juneb.GitHub.IO/hex блог
Серый личный блог, записывающий все посты блога по учебе и работе, приглашаю всех в гости
2. Заявление
Это не так хорошо, как письмо веры.Контент уже написан, и это чисто из семьи.Из-за ограниченных личных возможностей неизбежно будут упущения и ошибки.Если вы найдете ошибки или лучше предложения, вы можете критиковать и исправлять их. Спасибо
- Адрес вейбо:Маленький серый блог
- QQ: серо-серый / 3302797840