Дедупликация URL-адресов часто встречается в нашей повседневной работе и на собеседованиях, например:Можно увидеть, что известные интернет-компании, включая Alibaba, NetEase Cloud, Youku и Homework Group, представили аналогичные вопросы для интервью, и они похожи на дедупликацию URL-адресов, например, решение о черном/белом списке IP-адресов и т. д., которые часто появляются в нашей работе. , поэтому в этой статье мы обсудим проблему дедупликации URL "диск один".
Идея дедупликации URL
Без учета бизнес-сценария и объема данных мы можем использовать следующую схему для реализации повторного суждения об URL:
- Используйте коллекцию Set Java, чтобы определить, дублируется ли URL-адрес, в соответствии с результатом добавления (успешное добавление означает, что URL-адрес не дублируется);
- Используйте коллекцию Set в Redis, чтобы определить, дублируется ли URL-адрес в соответствии с результатом добавления;
- Сохраните все URL-адреса в базе данных, а затем используйте операторы SQL, чтобы определить, существуют ли повторяющиеся URL-адреса;
- Установите столбец URL в базе данных как уникальный индекс и оцените, повторяется ли URL-адрес, по результату добавления;
- Используйте фильтр Блума Guava для реализации взвешивания URL-адресов;
- Используйте фильтр Redis Bloom для реализации взвешивания URL-адресов.
Конкретная реализация вышеописанной схемы заключается в следующем.
Схема реализации дедупликации URL
1. Используйте коллекцию Set Java, чтобы оценить вес
Коллекция Set по своей природе неповторяема. В ней могут храниться только элементы с разными значениями. Если значение одинаковое, добавление завершится ошибкой. Поэтому мы можем определить, повторяется ли URL-адрес, по результату добавления коллекции Set. код реализации выглядит следующим образом:
public class URLRepeat {
// 待去重 URL
public static final String[] URLS = {
"www.apigo.cn",
"www.baidu.com",
"www.apigo.cn"
};
public static void main(String[] args) {
Set<String> set = new HashSet();
for (int i = 0; i < URLS.length; i++) {
String url = URLS[i];
boolean result = set.add(url);
if (!result) {
// 重复的 URL
System.out.println("URL 已存在了：" + url);
}
}
}
}
Результат выполнения программы:
URL-адрес уже существует:www.apigo.cn
Из приведенных выше результатов видно, что функция взвешивания URL-адресов может быть реализована с использованием коллекции Set.
2. Дедупликация коллекции Redis Set
Идея использования коллекции Set в Redis такая же, как и в коллекции Set в Java, обе из которых реализуются за счет неповторяемости Set. Давайте сначала воспользуемся клиентским Redis-cli Redis для реализации примера оценки веса URL:Как видно из приведенных выше результатов, успешное добавление означает, что URL-адрес не повторяется, а неудачное добавление (результат равен 0) означает, что URL-адрес уже существует.
Давайте используем метод кода для реализации дедупликации Redis Set, Код реализации выглядит следующим образом:
// 待去重 URL
public static final String[] URLS = {
"www.apigo.cn",
"www.baidu.com",
"www.apigo.cn"
};
@Autowired
RedisTemplate redisTemplate;
@RequestMapping("/url")
public void urlRepeat() {
for (int i = 0; i < URLS.length; i++) {
String url = URLS[i];
Long result = redisTemplate.opsForSet().add("urlrepeat", url);
if (result == 0) {
// 重复的 URL
System.out.println("URL 已存在了：" + url);
}
}
}
Результат выполнения вышеуказанной программы:
URL-адрес уже существует:www.apigo.cn
В приведенном выше коде мы используем Spring DataRedisTemplateРеализовано для использования в проекте Spring Boot.RedisTemplateОбъект, который нам нужно импортировать первымspring-boot-starter-data-redisFramework информация о конфигурации выглядит следующим образом:
<!-- 添加操作 RedisTemplate 引用 -->
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
Затем вам нужно настроить информацию о подключении Redis в проекте и настроить следующее в application.properties:
spring.redis.host=127.0.0.1
spring.redis.port=6379
#spring.redis.password=123456 # Redis 服务器密码，有密码的话需要配置此项
После двух вышеуказанных шагов мы можем использовать его в обычном режиме в проекте Spring Boot.RedisTemplateобъект для работы с Redis.
3. Дедупликация базы данных
Мы также можем использовать базу данных для реализации повторной оценки URL-адресов.Во-первых, давайте создадим таблицу хранения URL-адресов, как показано на следующем рисунке:SQL, соответствующий этой таблице, выглядит следующим образом:
/*==============================================================*/
/* Table: urlinfo */
/*==============================================================*/
create table urlinfo
(
id int not null auto_increment,
url varchar(1000),
ctime date,
del boolean,
primary key (id)
);
/*==============================================================*/
/* Index: Index_url */
/*==============================================================*/
create index Index_url on urlinfo
(
url
);
вidявляется автоматически увеличивающимся первичным ключом, иurlПоле задано как индекс, и установка индекса может ускорить запрос.
Сначала мы добавляем в базу данных два тестовых данных, как показано на следующем рисунке:
Мы используем оператор SQL для запроса, как показано на следующем рисунке:Если результат больше 0, это означает, что уже есть повторяющиеся URL-адреса, в противном случае это означает, что повторяющихся URL-адресов нет.
4. Дедупликация уникальных индексов
Мы также можем использовать уникальный индекс базы данных для предотвращения дублирования URL.Идея его реализации очень похожа на идею предыдущей коллекции Set.
Сначала мы устанавливаем уникальный индекс для поля URL, а затем добавляем данные URL, Если он может быть добавлен успешно, это означает, что URL не повторяется, в противном случае это означает, что он повторяется.
Реализация SQL для создания уникального индекса выглядит следующим образом:
create unique index Index_url on urlinfo
(
url
);
5. Дедупликация фильтра Блума гуавы
Фильтр Блума был предложен Блумом в 1970 году. На самом деле это длинный двоичный вектор и ряд функций случайного отображения. Фильтры Блума можно использовать для определения того, находится ли элемент в коллекции. Его преимущество заключается в том, что эффективность использования пространства и время запроса намного больше, чем у общего алгоритма, а недостаток заключается в том, что существует определенная частота неправильного распознавания и сложность удаления.
Основная реализация фильтра Bloom - очень большой битовый массив и несколько хэш-функций. Предположим, что длина битового массива M и количество функций хеша есть k.Приведенный выше рисунок взят в качестве примера конкретного рабочего процесса: Предположим, что в наборе есть 3 элемента {x, y, z}, а количество хеш-функций равно 3. Сначала инициализируйте битовый массив и установите каждый бит в 0. Для каждого элемента в наборе сопоставьте элементы через 3 хэш-функции по очереди, каждое сопоставление будет генерировать хеш-значение, это значение соответствует точке над битовым массивом, а затем пометить позицию, соответствующую битовому массиву, как 1 , когда запрашивая, существует ли элемент W в коллекции, тот же метод сопоставляет W с 3 точками битового массива путем хэширования. Если одна из трех точек не равна 1, можно сделать вывод, что элемент не должен существовать в множестве. И наоборот, если все 3 точки равны 1, элемент может существовать в наборе. Примечание. Здесь невозможно судить о том, должен ли элемент существовать в наборе, и может быть определенная доля ошибочных оценок. Это видно из рисунка: Предположим, что элемент соответствует трем точкам 4, 5 и 6 посредством отображения. Хотя все эти три точки равны 1, очевидно, что эти три точки являются позициями, полученными разными элементами после хеширования, поэтому эта ситуация показывает, что, хотя элементы не входят в набор, они могут соответствовать 1, что является коэффициентом неправильной оценки. причина существования.
Мы можем использовать структуру Guava, предоставленную Google, для работы с фильтром Блума, поэтому сначала мы добавляем ссылку на Guava в pom.xml, конфигурация выглядит следующим образом:
<!-- 添加 Guava 框架 -->
<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.2-jre</version>
</dependency>
Код реализации оценки URL:
public class URLRepeat {
// 待去重 URL
public static final String[] URLS = {
"www.apigo.cn",
"www.baidu.com",
"www.apigo.cn"
};
public static void main(String[] args) {
// 创建一个布隆过滤器
BloomFilter<String> filter = BloomFilter.create(
Funnels.stringFunnel(Charset.defaultCharset()),
10, // 期望处理的元素数量
0.01); // 期望的误报概率
for (int i = 0; i < URLS.length; i++) {
String url = URLS[i];
if (filter.mightContain(url)) {
// 用重复的 URL
System.out.println("URL 已存在了：" + url);
} else {
// 将 URL 存储在布隆过滤器中
filter.put(url);
}
}
}
}
Результат выполнения вышеуказанной программы:
URL-адрес уже существует:www.apigo.cn
6. Фильтр Redis Bloom для дедупликации
В дополнение к фильтру Блума Guava мы также можем использовать фильтр Блума Redis для реализации взвешивания URL-адресов. Прежде чем использовать его, мы должны убедиться, что версия сервера Redis выше 4.0 (только эта версия поддерживает фильтры цветения), и функцию фильтра цветения Redis можно использовать в обычном режиме.
На примере Docker продемонстрируем установку и открытие фильтра Блума Redis.Сначала загрузите фильтр Блума Redis, а затем включите фильтр Блума при перезапуске службы Redis, как показано на следующем рисунке:
Использование фильтра БлумаПосле того, как фильтр Блума включен нормально, мы сначала используем клиент Redis redis-cli для реализации оценки URL-адреса фильтра Блума.Команда реализации выглядит следующим образом:
В Redis не так много рабочих команд для фильтров Блума, в основном это следующие:
- bf.add добавить элемент;
- bf.exists, чтобы определить, существует ли элемент;
- bf.madd добавляет несколько элементов;
- bf.mexists определяет, существуют ли несколько элементов;
- bf.reserve устанавливает точность фильтра Блума.
Далее мы используем код для демонстрации использования фильтра Блума Redis:
import redis.clients.jedis.Jedis;
import utils.JedisUtils;
import java.util.Arrays;
public class BloomExample {
// 布隆过滤器 key
private static final String _KEY = "URLREPEAT_KEY";
// 待去重 URL
public static final String[] URLS = {
"www.apigo.cn",
"www.baidu.com",
"www.apigo.cn"
};
public static void main(String[] args) {
Jedis jedis = JedisUtils.getJedis();
for (int i = 0; i < URLS.length; i++) {
String url = URLS[i];
boolean exists = bfExists(jedis, _KEY, url);
if (exists) {
// 重复的 URL
System.out.println("URL 已存在了：" + url);
} else {
bfAdd(jedis, _KEY, url);
}
}
}
/**
* 添加元素
* @param jedis Redis 客户端
* @param key key
* @param value value
* @return boolean
*/
public static boolean bfAdd(Jedis jedis, String key, String value) {
String luaStr = "return redis.call('bf.add', KEYS[1], KEYS[2])";
Object result = jedis.eval(luaStr, Arrays.asList(key, value),
Arrays.asList());
if (result.equals(1L)) {
return true;
}
return false;
}
/**
* 查询元素是否存在
* @param jedis Redis 客户端
* @param key key
* @param value value
* @return boolean
*/
public static boolean bfExists(Jedis jedis, String key, String value) {
String luaStr = "return redis.call('bf.exists', KEYS[1], KEYS[2])";
Object result = jedis.eval(luaStr, Arrays.asList(key, value),
Arrays.asList());
if (result.equals(1L)) {
return true;
}
return false;
}
}
Результат выполнения вышеуказанной программы:
URL-адрес уже существует:www.apigo.cn
Суммировать
В этой статье представлены 6 схем дедупликации URL-адресов,Среди них четыре решения Redis Set, Redis Bloom Filter, Database и Unique Index подходят для распределенных систем.Если это массивная распределенная система, рекомендуется использовать Redis Bloom Filter для дедупликации URL-адресов.Данные рекомендуют использовать Guava's Bloomer реализовать дедупликацию URL.
Подпишитесь на официальный аккаунт «Java Chinese Community» и отправьте «Интервью», чтобы получить последние материалы обзора интервью, которые я собрал.