Эта статья написанаyanglbmeОригинал, впервые опубликованный в публичном аккаунте"Сообщество открытого исходного кода Doocs", добро пожаловать на перепечатку.
Если вы разрабатываете приложение, основанное на «событиях», которое обрабатывает множество запросов от разных пользователей, скорее всего, вы захотите иметь возможность вычислять скользящие окна или различные действия пользователя в течение определенного периода времени.
Один из самых быстрых способов подсчета различных действий пользователя — написатьSELECT COUNT(DISTINCT user)SQL. Однако, если объем данных в реальном времени исчисляется миллионами, это может быть дорого. Другой способ, который вы можете придумать, — сохранить пользователей в коллекции наборов Redis, поскольку наборы, естественно, имеют функцию дедупликации.
Однако это решение также приносит присущие ему проблемы. Если приложение, которое подсчитывает разные пользовательские записи, работает с несколькими экземплярами, нам нужно решение для кэширования в памяти с огромным объемом ОЗУ. Если мы хотим обработать 10 миллионов различных записей, выделяя по 10 байтов для каждой, то нам потребуется как минимум 100 МБ памяти только для одного временного интервала. Так что это не эффективное решение для памяти.
В этой статье я хочу показать вам, как обрабатывать миллион различных пользовательских записей, выделяя менее 2 МБ памяти на сервере Redis Cache.
Все мы знаем, что Redis имеет несколько структур данных, таких как:String,BitMap,Set,Sorted SetЖдать. Здесь я хотел бы подчеркнутьHyperloglog, поскольку он лучше всего подходит для подсчета различных действий пользователя за счет снижения потребления памяти.
Hyper LogLog
Имена счетчиков Hyper LogLog говорят сами за себя. вы можете просто использоватьloglog(Nmax)+ O(1)битов для оценки мощности набора мощности Nmax.
Операции Hyperloglog в Redis
Для работы Redis Hyperloglog мы можем использовать следующие три команды:
PFADDPFCOUNTPFMERGE
Мы объясним эти команды на практическом примере. Например, есть сценарий, когда пользователи входят в систему, и нам нужно посчитать разных пользователей в течение часа. Поэтому нам нужен такой ключ, как USER:LOGIN:2019092818. Другими словами, мы хотим подсчитать количество отдельных пользователей, которые вошли в систему с 18:00 до 19:00 28 сентября 2019 года. В будущем нам также нужно использовать соответствующий ключ для представления, например 2019111100, 2019111101, 2019111102 и т. д.
Предположим, что пользователи A, B, C, D, E и F вошли в систему между 18:00 и 19:00.
127.0.0.1:6379> pfadd USER:LOGIN:2019092818 A
(integer) 1
127.0.0.1:6379> pfadd USER:LOGIN:2019092818 B C D E F
(integer) 1
127.0.0.1:6379>
При подсчете вы получите ожидаемые 6.
127.0.0.1:6379> pfcount USER:LOGIN:2019092818
(integer) 6
Если A и B войдут в систему несколько раз в течение этого времени, вы также получите тот же результат, потому что мы держим только разных пользователей.
127.0.0.1:6379> pfadd USER:LOGIN:2019092818 A B
(integer) 0
127.0.0.1:6379> pfcount USER:LOGIN:2019092818
(integer) 6
Если пользователи A~F и еще один пользователь G входят в систему с 19:00 до 20:00:
127.0.0.1:6379> pfadd USER:LOGIN:2019092819 A B C D E F G
(integer) 1
127.0.0.1:6379> pfcount USER:LOGIN:2019092819
(integer) 7
Теперь у нас есть два ключа USER:LOGIN:2019092818 и USER:LOGIN:2019092819, если мы хотим узнать, сколько разных пользователей вошли в систему с 18:00 до 20:00 (2 часа), мы можем напрямую использоватьpfcountКоманда выполняет комбинированный подсчет двух клавиш:
127.0.0.1:6379> pfcount USER:LOGIN:2019092818 USER:LOGIN:2019092819
(integer) 7
Если нам нужно сохранить значение ключа и избежать его повторного подсчета, мы можем объединить ключи в один ключ USER:LOGIN:2019092818-19 и выполнить прямую операцию с этим ключом.pfcountоперации, как показано ниже.
127.0.0.1:6379> pfmerge USER:LOGIN:2019092818-19 USER:LOGIN:2019092818 USER:LOGIN:2019092819
OK
127.0.0.1:6379> pfcount USER:LOGIN:2019092818-19
(integer) 7
Далее давайте напишем программу для сравнения использования памяти при использовании SET и Hyperloglog для хранения различных действий пользователей при входе в систему.
import redis.clients.jedis.Jedis;
public class RedisTest {
private static final int NUM = 1000000; // 100万用户
private static final String SET_KEY = "SET:USER:LOGIN:2019082811";
private static final String PF_KEY = "PF:USER:LOGIN:2019082811";
public static void main(String[] args) {
Jedis client = new Jedis();
for (int i = 0; i < NUM; ++i) {
System.out.println(i);
client.sadd(SET_KEY, "USER" + i);
client.pfadd(PF_KEY, "USER" + i);
}
}
}
Давайте посмотрим на результаты: для 1 миллиона пользователей Set может храниться точно, в то время как Hyperloglog немного отклоняется, с дополнительными 7336. Частота ошибок составляет около0.7%. С точки зрения использования памяти Set потребляет 10888895B≈10MB, а Hyperloglog потребляет только 10481B≈10KB памяти, что составляет почти 1/1000 от Set.
127.0.0.1:6379> scard SET:USER:LOGIN:2019082811
(integer) 1000000
127.0.0.1:6379> pfcount PF:USER:LOGIN:2019082811
(integer) 1007336
127.0.0.1:6379> debug object SET:USER:LOGIN:2019082811
Value at:00007FD74F841940 refcount:1 encoding:hashtable serializedlength:10888895 lru:9308508 lru_seconds_idle:53
127.0.0.1:6379> debug object PF:USER:LOGIN:2019082811
Value at:00007FD74F7A5940 refcount:1 encoding:raw serializedlength:10481 lru:9308523 lru_seconds_idle:50
Параметр serializedlength указывает количество байтов памяти, занимаемых содержимым, хранимым ключом.
Различные значения для раздвижных окон
Для подсчета разных пользователей в скользящем окне нужно указать меньшую гранулярность, в этом случае достаточно минут, сохраняем поведение пользователя в ключе формата ггггММддЧЧмм, например USER:LOGIN: 201909281820.
Когда мы хотим подсчитать различные пользовательские операции за последние 5 минут, нам нужно всего лишь объединить 5 ключей:
127.0.0.1:6379> pfcount 201909281821 201909281822 201909281823 201909281824 201909281825
(integer) 6
Отсюда нам нужно 60 ключей для подсчета последнего часа, 1440 ключей для подсчета последнего дня и 10080 ключей для подсчета последних 7 дней. Чем больше у нас ключей, тем больше времени требуется для вычисления при их слиянии. Поэтому мы должны уменьшить количество ключей и сохранить не только ключи в формате ггггММддЧЧмм, но и интервалы часов, дней и месяцев и использовать ггггММ, ггггММдд, ггггММддЧЧ.
С этими новыми ключами операции pfcount могут занимать меньше времени, например:
Если вы хотите посчитать действия пользователя за последние сутки и использовать только минутный ключ, вам нужно объединить все 1440 ключей. Однако, если вы используете часовой ключ в дополнение к минутному, вам понадобятся только 60-минутные ключи и 24-часовые ключи, поэтому нам нужно только 84 ключа.
package utils;
import org.apache.commons.lang3.time.DateUtils;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.stream.Collectors;
public class HLLUtils {
private static String TIME_FORMAT_MONTH_DAY = "MMdd";
private static String TIME_FORMAT_DAY_MINUTES = "MMddHHmm";
private static String TIME_FORMAT_DAY_HOURS = "MMddHH";
private static SimpleDateFormat FORMAT_MONTH_DAY = new SimpleDateFormat(TIME_FORMAT_MONTH_DAY);
private static SimpleDateFormat FORMAT_DAY_HOURS = new SimpleDateFormat(TIME_FORMAT_DAY_HOURS);
private static SimpleDateFormat FORMAT_DAY_MINUTES = new SimpleDateFormat(TIME_FORMAT_DAY_MINUTES);
/**
* 获取两个日期之间的键
*
* @param d1 日期1
* @param d2 日期2
* @return 键列表
*/
public static List<String> parse(Date d1, Date d2) {
List<String> list = new ArrayList<>();
if (d1.compareTo(d2) == 0) {
return list;
}
long delta = d2.getTime() - d1.getTime();
if (delta == 0) {
return list;
}
if (delta < DateUtils.MILLIS_PER_HOUR) { // 若时间差小于 1 小时
int minutesDiff = (int) (delta / DateUtils.MILLIS_PER_MINUTE);
Date date1Increment = d1;
while (d2.compareTo(date1Increment) > 0 && minutesDiff > 0) {
list.add(FORMAT_DAY_MINUTES.format(date1Increment));
date1Increment = DateUtils.addMinutes(date1Increment, 1);
}
} else if (delta < DateUtils.MILLIS_PER_DAY) { // 若时间差小于 1 天
Date dateLastPortionHour = DateUtils.truncate(d2, Calendar.HOUR_OF_DAY);
list.addAll(parse(dateLastPortionHour, d2));
long delta2 = dateLastPortionHour.getTime() - d1.getTime();
int hoursDiff = (int) (delta2 / DateUtils.MILLIS_PER_HOUR);
Date date1Increment = DateUtils.addHours(dateLastPortionHour, -1 * hoursDiff);
while (dateLastPortionHour.compareTo(date1Increment) > 0 && hoursDiff > 0) {
list.add(FORMAT_DAY_HOURS.format(date1Increment));
date1Increment = DateUtils.addHours(date1Increment, 1);
}
list.addAll(parse(d1, DateUtils.addHours(dateLastPortionHour, -1 * hoursDiff)));
} else {
Date dateLastPortionDay = DateUtils.truncate(d2, Calendar.DAY_OF_MONTH);
list.addAll(parse(dateLastPortionDay, d2));
long delta2 = dateLastPortionDay.getTime() - d1.getTime();
int daysDiff = (int) (delta2 / DateUtils.MILLIS_PER_DAY); // 若时间差小于 1 个月
Date date1Increment = DateUtils.addDays(dateLastPortionDay, -1 * daysDiff);
while (dateLastPortionDay.compareTo(date1Increment) > 0 && daysDiff > 0) {
list.add(FORMAT_MONTH_DAY.format(date1Increment));
date1Increment = DateUtils.addDays(date1Increment, 1);
}
list.addAll(parse(d1, DateUtils.addDays(dateLastPortionDay, -1 * daysDiff)));
}
return list;
}
/**
* 获取从 date 往前推 minutes 分钟的键列表
*
* @param date 特定日期
* @param minutes 分钟数
* @return 键列表
*/
public static List<String> getLastMinutes(Date date, int minutes) {
return parse(DateUtils.addMinutes(date, -1 * minutes), date);
}
/**
* 获取从 date 往前推 hours 个小时的键列表
*
* @param date 特定日期
* @param hours 小时数
* @return 键列表
*/
public static List<String> getLastHours(Date date, int hours) {
return parse(DateUtils.addHours(date, -1 * hours), date);
}
/**
* 获取从 date 开始往前推 days 天的键列表
*
* @param date 特定日期
* @param days 天数
* @return 键列表
*/
public static List<String> getLastDays(Date date, int days) {
return parse(DateUtils.addDays(date, -1 * days), date);
}
/**
* 为keys列表添加前缀
*
* @param keys 键列表
* @param prefix 前缀符号
* @return 添加了前缀的键列表
*/
public static List<String> addPrefix(List<String> keys, String prefix) {
return keys.stream().map(key -> prefix + key).collect(Collectors.toList());
}
}
Давайте взглянем на список примеров ключей, рассчитанных между двумя датами. Как вы уже поняли, количество ключей должно быть как можно меньше, чтобы затраты на слияние ключей для статистики были относительно небольшими. Поэтому будем делить временной диапазон не только на минуты, но и на часы, дни, месяцы и т.д.
- BEGIN=201909281800&END=201909281920
[USER:LOGIN:09281900, USER:LOGIN:09281901, USER:LOGIN:09281902, USER:LOGIN:09281903, USER:LOGIN:09281904, USER:LOGIN:09281905, USER:LOGIN:09281906, USER:LOGIN:09281907, USER:LOGIN:09281908, USER:LOGIN:09281909, USER:LOGIN:09281910, USER:LOGIN:09281911, USER:LOGIN:09281912, USER:LOGIN:09281913, USER:LOGIN:09281914, USER:LOGIN:09281915, USER:LOGIN:09281916, USER:LOGIN:09281917, USER:LOGIN:09281918, USER:LOGIN:09281919, USER:LOGIN:092818]
- BEGIN=20190928191100&END=20190930163800
[USER:LOGIN:09301600, USER:LOGIN:09301601, USER:LOGIN:09301602, USER:LOGIN:09301603, USER:LOGIN:09301604, USER:LOGIN:09301605, USER:LOGIN:09301606, USER:LOGIN:09301607, USER:LOGIN:09301608, USER:LOGIN:09301609, USER:LOGIN:09301610, USER:LOGIN:09301611, USER:LOGIN:09301612, USER:LOGIN:09301613, USER:LOGIN:09301614, USER:LOGIN:09301615, USER:LOGIN:09301616, USER:LOGIN:09301617, USER:LOGIN:09301618, USER:LOGIN:09301619, USER:LOGIN:09301620, USER:LOGIN:09301621, USER:LOGIN:09301622, USER:LOGIN:09301623, USER:LOGIN:09301624, USER:LOGIN:09301625, USER:LOGIN:09301626, USER:LOGIN:09301627, USER:LOGIN:09301628, USER:LOGIN:09301629, USER:LOGIN:09301630, USER:LOGIN:09301631, USER:LOGIN:09301632, USER:LOGIN:09301633, USER:LOGIN:09301634, USER:LOGIN:09301635, USER:LOGIN:09301636, USER:LOGIN:09301637, USER:LOGIN:093000, USER:LOGIN:093001, USER:LOGIN:093002, USER:LOGIN:093003, USER:LOGIN:093004, USER:LOGIN:093005, USER:LOGIN:093006, USER:LOGIN:093007, USER:LOGIN:093008, USER:LOGIN:093009, USER:LOGIN:093010, USER:LOGIN:093011, USER:LOGIN:093012, USER:LOGIN:093013, USER:LOGIN:093014, USER:LOGIN:093015, USER:LOGIN:0929, USER:LOGIN:092820, USER:LOGIN:092821, USER:LOGIN:092822, USER:LOGIN:092823, USER:LOGIN:09281911, USER:LOGIN:09281912, USER:LOGIN:09281913, USER:LOGIN:09281914, USER:LOGIN:09281915, USER:LOGIN:09281916, USER:LOGIN:09281917, USER:LOGIN:09281918, USER:LOGIN:09281919, USER:LOGIN:09281920, USER:LOGIN:09281921, USER:LOGIN:09281922, USER:LOGIN:09281923, USER:LOGIN:09281924, USER:LOGIN:09281925, USER:LOGIN:09281926, USER:LOGIN:09281927, USER:LOGIN:09281928, USER:LOGIN:09281929, USER:LOGIN:09281930, USER:LOGIN:09281931, USER:LOGIN:09281932, USER:LOGIN:09281933, USER:LOGIN:09281934, USER:LOGIN:09281935, USER:LOGIN:09281936, USER:LOGIN:09281937, USER:LOGIN:09281938, USER:LOGIN:09281939, USER:LOGIN:09281940, USER:LOGIN:09281941, USER:LOGIN:09281942, USER:LOGIN:09281943, USER:LOGIN:09281944, USER:LOGIN:09281945, USER:LOGIN:09281946, USER:LOGIN:09281947, USER:LOGIN:09281948, USER:LOGIN:09281949, USER:LOGIN:09281950, USER:LOGIN:09281951, USER:LOGIN:09281952, USER:LOGIN:09281953, USER:LOGIN:09281954, USER:LOGIN:09281955, USER:LOGIN:09281956, USER:LOGIN:09281957, USER:LOGIN:09281958, USER:LOGIN:09281959]
пример
Фактически, с помощью описанного выше метода генерации ключей мы можем легко применить HyperLoglog Redis для статистики данных в реальных сценариях.Например, мы хотим подсчитать UV, сдвинутые вперед на один час, один день и одну неделю с этого момента.
Код реализован следующим образом:
import redis.clients.jedis.Jedis;
import utils.JedisUtils;
import java.util.Date;
import java.util.List;
import static utils.HLLUtils.addPrefix;
import static utils.HLLUtils.getLastDays;
import static utils.HLLUtils.getLastHours;
public class UVCounter {
private Jedis client = JedisUtils.getClient();
private static final String PREFIX = "USER:LOGIN:";
public UVCounter() {
}
/**
* 获取周UV
*
* @return UV数
*/
public long getWeeklyUV() {
List<String> suffixKeys = getLastDays(new Date(), 7);
List<String> keys = addPrefix(suffixKeys, PREFIX);
return client.pfcount(keys.toArray(new String[0]));
}
/**
* 获取日UV
*
* @return UV数
*/
public long getDailyUV() {
List<String> suffixKeys = getLastHours(new Date(), 24);
List<String> keys = addPrefix(suffixKeys, PREFIX);
return client.pfcount(keys.toArray(new String[0]));
}
/**
* 获取小时UV
*
* @return UV数
*/
public long getHourlyUV() {
List<String> suffixKeys = getLastHours(new Date(), 1);
List<String> keys = addPrefix(suffixKeys, PREFIX);
return client.pfcount(keys.toArray(new String[0]));
}
}
Как дела, выучились?
Добро пожаловать в мою общедоступную учетную запись WeChat «Сообщество открытого исходного кода Doocs». Оригинальные технические статьи будут опубликованы как можно скорее.