Интервьюер: Я вижу в вашем резюме, что оно используется в вашем проектеRedis, и использовать его для кэширования, можете ли вы сказать мнеRedisПять основных типов данных ?
Собеседник подумал про себя: я видел это вчера
FrancisQизОсновные статьи Redis, я все еще боюсь тебя? Это настолько просто, что меня это не смущает!
Поэтому он сказал: эммм,Redisимеютstringнить,hashхэш,listсписок,setнеупорядоченный сбор,zsetОтсортированная коллекция этих пяти типов данных.
Интервьюер: В дополнение к этим пяти основным типам данных вы также узнали о другихRedisПредусмотрены ли дополнительные типы данных? ты говоришь, что используешьRedisКэширование, например, теперь я опрашиваю пользователей с кешем, которого изначально не существует.IDдля вызова вашего интерфейса, как этопроникновение в кешКак это предотвратить?
Собеседник подумал про себя: я видел это вчера
FrancisQизОсновные статьи Redis, кажется, в начале написано bitMap? Что ч??Журнал? ГЭФ? ? Я не могу вспомнить что, какое проникновение в кеш? Какого черта? ? ЭтотFrancisQЯвно изменяет мне, он сказал мне пять основных типов данных, и я ничего не могу сделать сейчас
Я не могу не стиснуть зубы и подняться: эмм, я понимаюbitMap, проникновение в кеш я не трогал.
Интервьюер: Тогда вы использовали егоbitMapДля достижения какой функции?
Интервьюер подумал про себя: все кончено, все холодно, все виноваты
FrancisQ, вернитесь и найдите его, чтобы свести счеты.
Мое сердце уже остыло: нет. . .
слова, написанные впереди
фактическиFrancisQЯ всего лишь новичок, который никогда не участвовал в интервью, я учусь на третьем курсе и хочу пройти стажировку следующим летом, поэтому я напишу несколько статей, чтобы поделиться и подвести итоги (не для зарабатывания денег) в свободное время. .FrancisQЕсли текст неплох, пожалуйста, поставьте мне лайк (#^.^#), на самом деле я просто хочу поскорее добраться до LV4. Конечно, я также делюсь другими статьями, такими какПринципиальный анализ и реализация структуры SSM,MySQLПодождите, если вам интересно, вы также можете подписаться на меня.
Конечно, если у вас есть стажировка, вы можете мне помочь, хахаха.
Без дальнейших церемоний, то, что я приношу вам сегодня,RedisЧетыре специальные структуры данных вbitmap,hyperLogLog,bloomFilter,GeoHash. Эти четыре структуры данных на самом деле чем-то похожи на уровень алгоритма, напримерGeoHashНа самом делеzset,bitmapэтоstring, просто разные используемые методы приводят к большему количеству функций.
BloomFilter
Введение и использование сцены
правильноBloomFilterЕсли вы не знакомы, вы должны быть знакомы с картинками ниже, верно? не говори мне, что ты только игралкоролевский пестицид.
BloomFilterКитайское имяФильтр Блума, в качестве фильтра, похоже ли это на умение Браума E (Несокрушимый) в LOL?
Фильтр Блума – этоцвестипредложенныйБольшой битовый массив и несколько различных хеш-функцийДля этого мы можем понимать фильтр Блума какнеточный набор. мы все знаемsetможно дедуплицировать, использоватьsetЭто может помочь нам определить, существуют ли уже определенные элементы в коллекции, или помочь нам реализовать функцию дедупликации.
но,setОбеспечение точной дедупликации также приносит нам более серьезную проблему —потребление пространства.
Например, в настоящее время, когда мы выполняем веб-сканирование, нам нужноurlДля дедупликации, чтобы избежать сканирования уже просканированных сайтов, если мы используемsetЗначит, нам нужно поставить все просканированныеurlв коллекцию, предполагаяurl64 байта, затем 100 миллионовurlЗначит нам надо занять 6гб, миллиард это около 60гб.
Обратите внимание, что это память.
Например, в настоящее время нам необходимо отфильтровать спам или текстовые сообщения со спамом. Если мы используем это времяsetПоэтому мне не нужно больше говорить о занимаемом им пространстве.Уровень сотен ГБиз.
Я упоминал в интервью вышепроникновение в кеш,Пользователь намеренно запрашивает, чтобы база данных вообще не существовала.(Например, ID=-1), если вы не будете заниматься обработкой в это время, вы обязательно проникнете в кеш, чтобы запросить базу данных.Один запрос — это хорошо, но если одновременно приходят тысячи или десятки тысяч ? Выдержит ли ваша база данных? Затем мы используемsetКак вы думаете, стоит ли занимать столько места в памяти для обработки? ? ? Или есть лучший способ?
Три типичных сценария, упомянутых выше,Дедупликация веб-сайтов, фильтрация спама, проникновение в кеш, эти три просто используютBloomFilterможно решить отлично.
Заметили ли вы, что приведенные выше три сценария не требуют очень высокой точности, особенно фильтрации спама.На самом деле, не имеет значения, если вы время от времени получаете несколько писем со спамом. Как и проникновение в кеш, это как раз подходитBloomFilterособенностьОн сказал, что у некоторых может и не быть, и сказал, что точно нет, я говорю тебе этоIDЕсли базы данных не существует, то ее действительно не существует. Я вас отфильтровал, и вы так уверены. Почему, вы ударили меня? ? ?
Принципиальный запрос
После стольких разговоров о концепциях и сценариях применения это правильно?BloomFilterКак я могу провести похудение и все еще быть в замешательстве? Давайте поговорим оBloomFilterпринцип реализации. Во-первых, позвольте мне дать вам структурную схему.
Среди них F, G, H несколькоБеспристрастная хеш-функция, внизу естьбольшой битовый массив, когда мыBloomFilterПри добавлении данных он сначала выполнит несколько хэш-операций над нашими данными (ключом) (здесь FGH).Каждая хеш-операция получит неиспользуемый индекс индекса битового массива.В это время мы вычислим несколько Просто изменим значение индекса положение до 1. Если вы определяете, существует ли элемент, покаЗначение всех индексных индексов, в которых находится суждение, равно 1.Вот и все.
На самом деле, вы также обнаружили, что вBloomFilterБудут повторяющиеся индексы, рассчитанные по разным ключам, как показано на рисунке выше, это и есть источник ошибки (Вы можете настроить начальный размер и частоту ошибок, чтобы контролировать ошибку)СлишкомОн сказал, что у некоторых может и не быть, и сказал, что точно нетОсновная причина этой характеристики, потому чтоЕсли это все 0 или существует 0, то его определенно не существует.Если это все 1, это может быть 1, вставленная другими ключами..
основное использование
так какBloomFilterдаRedisмодуль расширения, поэтому требуется дополнительная загрузка, вы можете использоватьDockerСделайте тягу. Я не буду подробно объяснять этапы установки, вы можете перейти на его гитхаб, чтобы узнать, как установитьGitHub.com/Редис Блум/….
После установки мы можем использовать его с удовольствием.
-
bf.add key elementДобавить к -
bf.exists key elementопределить, есть ли -
bf.madd key element1 element2 ...Массовое добавление -
bf.mexists key element1 element2 ...Пакетное решение
Команда проста, можете попробовать сами.
HyperLogLog
Введение и использование сцены
существуетRedisТакже существует структура данных, в которой будут ошибкиHyperLogLog.
Сначала мы думаем о сценарии, когда начальник просит нас рассчитать стоимость страницы.UVчто нам делать?
Используйте, если трафика малоsetВыполнить дедупликацию пользователей вполне возможно, но если посещений миллионы или десятки миллионов, то вы столкнетесь с вышеописаннымпустая трата местаПроблема. Если у нас естьДедупликация и подсчетСтруктура данных в порядке.
В настоящее времяHyperLogLogЭто на шоу! это может обеспечитьНеточная схема подсчета дедупликации(Значение ошибки составляет около 0,81%), если это не точно, это не точно.UVНасколько точно вы хотите? 0,81% приемлемо для нас. самое главное этоHyperLogLogзанимать только12KBпамяти.
Как использовать и практиковать
-
pfadd key elementДобавить к -
pfcount keyрассчитать -
pfmerge destkey sourcekey1 sourcekey2 ...сливаться
Все команды начинаются с pf, потому что он был изобретен профессором Филиппом Флажоле.
Вы можете видеть, что эти три основные команды очень просты и их легко освоить. Итак, давайте попробуем.
BitMap
Введение и сценарии использования
Во-первых, давайте подумаем о более интересном сценарии. Начальник хочет, чтобы вы подсчитали количество дней, в течение которых несколько пользователей одновременно находятся в сети. Что вы должны делать в это время?
Вы можете подумать об использованииhashХранилище, это пустая трата места, есть ли лучший способ? Ответ - да,Redisиспользуется вbitmapбитовая карта.
Мы знаем, что символ в строке представлен 8 битами (как показано выше), вRedisсерединаbitmapдноstring,Также известен какstringдноbitmap.
Если у нас есть это, можем ли мы использовать его для подсчета количества раз, когда пользователь регистрировался в течение определенного времени? То есть местоположение представляет собой день, 0 означает отсутствие регистрации, 1 означает регистрацию, на приведенном выше рисунке пользователь зарегистрировался четыре раза за восемь дней.
RedisсерединаbitmapТакже предоставляет несколькоbitmapКоманды для AND, OR, XOR и, конечно же, одногоbitmapоперация НЕ. Это дало вам небольшое представление о том, что нам нужно в первую очередь?
Основное использование команды
-
setbit key index 0/1установить значение бита -
getbit key indexполучить значение бита -
bitcount key start endПолучить количество единиц в указанном диапазоне
Следует отметить, что начало и конец здесь относятся к положению символа, а не к положению бита! ! ! включая следующие битпо
-
bitpos key bit start endПолучить позицию первого диапазона индексов символов от начала до конца, значение которого равно биту -
bitop and/or/xor/not destkey key1 key2несколькоbitmapвыполнять логические операции.
Еще одна интересная команда для работы с растровыми изображениями — это битовое поле, я не буду подробно о ней рассказывать, заинтересованные студенты могут изучить ее самостоятельно.
Руки
Давайте сначала реализуем функцию подсчета количества чекинов пользователей.
Помните наш первый вопрос? Подсчитайте количество дней, в течение которых несколько пользователей находятся в сети одновременно в течение года, у нас естьbitmapЧего вы боитесь.
GeoHash
Введение и использование сценария
GeoHashобычно используется для расчетарядом люди, магазины рядом.
Представьте, что мы используем реляционную базу данных для хранения адреса (идентификатор, долгота, широта) элемента. Как мы считаем людей поблизости в это время? Собираемся ли мы перебирать все позиции элементов и вычислять расстояния? Это явно невозможно.
Конечно, вы можете разделить область и использовать оператор SQL, чтобы обвести область, а затем создатьдвунаправленный составной индексЧтобы повысить производительность, но возможности параллелизма базы данных в конце концов ограничены, можем ли мы использоватьRedisсделать это?
Ответ - да,Redisиспользуется вGeoHashдает хорошее решение. Конкретный принцип заключается вПредставьте землю как плоскость и сопоставьте двумерные координаты с одномерными.(причина потери точности). Если вам интересен алгоритм, вы можете узнать о нем больше самостоятельно, а место ограничено и не будет объяснено слишком много.
Основные команды и использование в реальном бою
-
geoadd key longitude latitude element(后面可配置多个三元组)добавить элемент -
geodist key element1 element2 unitВычислить расстояние между двумя элементами -
geopos key element [element]Получить позицию элемента -
geohash key elementполучить хэш элемента -
georadiusbymember key element distanceValue unit count countValue ASC/DESC [withdist] [withhash] [withcoord]Получить элементы рядом с элементом можно добавить со следующими параметрами [расстояние][хэш][координаты] -
georadius key longitude latitude distanceValue unit count countValue ASC/DESC [withdist] [withhash] [withcoord]То же, что и выше, за исключением того, что элемент изменяется на указанное значение координаты
Суммировать
В этой статье я хочу, чтобы вы представилиRedisЕсть еще четыре специальные структуры данных, ониBloomFilter,HyperLogLog,BitMapиGeoHash. И я также хочу, чтобы вы представили, как их использовать, каковы их сценарии применения, я надеюсь помочь вам.
Большое спасибо за то, что увидели это, если вам это нравится или помогает вам, не забудьте поставить лайк. Вы также можете подписаться на меня, я часто буду учиться, чтобы поделиться с вами.
Ниже приводится краткое изложение карты знаний этой статьи.Если вам понравилось, ставьте палец вверх, не проституируйте меня зря ┭┮﹏┭┮.