Есть некоторые вещи, которые должен знать каждый инженер-программист, но, к сожалению, этому не учат в школах. Один из них: как вставить несколько значений в одно значение.

Программная инженерия серии 101 -

  1. Вставка нескольких значений в одно 64-битное значение (вы здесь)
  2. Часовые пояса и работа с датами

Если вы не знаете об этом, возможно, вам интересно

  1. Как это помогает?
  2. Почему я не могу использовать разные переменные для каждого значения?
  3. Зачем без надобности усложнять вещи? У меня 8 ГБ ОЗУ, зачем мне экономить 8 байтов?

Основная цель помещения нескольких значений в одно большое значение - не экономия памяти или уменьшение количества переменных в программе.

Основная цель - кодировать несколько полезных значений в одно значение, чтобы в большинстве случаев однозначно идентифицировать его.

Вместо того, чтобы сначала вдаваться в вопросы «как это сделать», давайте выберем нетрадиционный путь и сначала рассмотрим вариант использования, чтобы понять, зачем он нужен и где его можно использовать. Это поможет вам интуитивно понять, «как это сделать».

Сценарий использования

Давайте рассмотрим сценарий, в котором этот метод широко используется, сегментирование базы данных на уровне приложения.

Разделение базы данных на уровне приложения означает, что само приложение знает, где находятся данные среди вашего роя экземпляров базы данных. Вместо того чтобы иметь какой-то механизм маршрутизации или хеш-таблицы для поиска данных на сервере, приложение знает, в какой базе данных есть нужные данные. Этот тип сегментирования не зависит от базы данных, которую вы используете, и не имеет значения, если в базе данных отсутствуют какие-либо функции сегментирования, такие как MySQL.

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

По прошествии 1 года ваш сервер базы данных изо всех сил пытается удовлетворить потребности в трафике. Чтобы решить эту проблему, у вас есть 2 варианта.

  1. Вертикальное масштабирование
  2. Горизонтальное масштабирование

Вертикальное масштабирование - дело затратное и конечное. Итак, вы хотите выбрать горизонтальное масштабирование, но MySQL не предоставляет функции горизонтального масштабирования. Итак, вы добавляете новый экземпляр MySQL для сегментирования данных. Теперь вам нужно найти новое сопоставление, чтобы найти сегментированные данные напрямую, а не искать во всех экземплярах.

Здесь мы можем использовать технику «вставки нескольких значений в одно 64-битное значение».

Перед этим нам нужно сделать несколько вещей:

  1. Дайте каждому сегменту базы данных уникальный идентификатор и назовите его dbID.
  2. Теперь у вас уже есть автоматически увеличивающийся postID для каждой строки в базе данных.
  3. Решите, сколько битов вы хотите выделить для каждого идентификатора, указанного выше. Например, вы выделили 10 бит для dbID и 42 бита для postID.

10 бит могут хранить 2¹⁰ = 1024 значения, 42 бита могут хранить 2⁴² = 43,98,04,65,11,104

Это означает, что вы можете создать 1024 осколка, и каждый осколок может иметь 43,98,04,65,11,104 строки.

Таким образом, вместо того, чтобы идентифицировать сообщение с помощью postID, вам также необходимо идентифицировать сегмент, то есть dbID.

Таким образом, вместо кодирования вашего URL-адреса, например, «your_domain.com/posts/postID», мы кодируем его как «your_domain.com/posts/newID». Теперь newID содержит информацию о postID и dbID, чтобы ваше приложение знало, какой сегмент запрашивать данные напрямую, без какого-либо промежуточного программного обеспечения.

Теперь мы собираемся закодировать postID и dbID в newID, например:

(Я использую Java, поэтому длина Java составляет 63 байта. Почему это важно? Мы рассмотрим это ниже в разделе «как это сделать».)

Заявление об ограничении ответственности: не пугайтесь, если вы не знаете, что это такое. О том, как это сделать, поговорим после.

long dbID = 997;
long postID = 8_04_65
0011 | 0101 = 0111
104L;
long newID = (dbID << 53) | (postID << 11);
System.out.println("newID: " + newID);
System.out.println("dbID: " + ((newID >> 53) & 0x3FF))
System.out.println("postID: " + ((newID >> 11) & 0x3FFFFFFFFFFL));

Результатом будет:

newID: 8980194136231510016
dbID: 997 
postID: 8046511104

Итак, теперь ваш новый URL-адрес может быть «your_domain.com/posts/8980194136231510016» вместо «your_domain.com/posts/8046511104».

Этот «8980194136231510016» содержит информацию об идентификаторе сегмента и идентификаторе сообщения.

Это называется сегментированием на уровне приложения, потому что ваше приложение знает, что postID: 8046511104 находится в базе данных с идентификатором: 997. Нет необходимости в промежуточном программном обеспечении, которое должно проверять, в какой базе данных находится postID: 8046511104.

Я почти уверен, что теперь вы знаете, почему это полезно в реальных условиях использования. Теперь посмотрим, как это делается

Как это сделать

Прежде всего, вам нужно быть осторожным с размером Integer на предпочитаемом вами языке.

Например,

В Javascript есть только один тип как для чисел с плавающей точкой, так и для целых чисел, то есть Number. Javascript использует только 53 бита для хранения целых чисел, но не 64 бита. В этих 53 битах 1 бит используется для знака. Таким образом, для кодирования можно использовать только 52 бита.

Java имеет тип «Long», который может хранить 64-битные целые числа. Но в отличие от C и C ++, в Java нет «беззнакового». Таким образом, вы можете использовать только 63 бита, потому что для знака используется 1 бит.

Итак, предположим, что «B» - это ваше количество бит, которое вы можете использовать. В приведенном выше примере мы использовали Java, поэтому B = 63.

ПРИМЕЧАНИЕ. Независимо от того, что вы хотите кодировать, сумма отдельных значений в битах не может превышать «B», а также допускаются только положительные числа.

Предположим, мы хотим сохранить в одном значении следующие значения:

  1. A с 15 битами - диапазон может быть от 0 до 32, 767 (2¹⁵-1)
  2. B с 35 битами - диапазон может быть от 0 до 34,35,97,38,367 (2³⁵-1)
  3. C с 10 битами - диапазон может быть от 0 до 1023 (2¹⁰-1)
  4. D с 3 битами - диапазон может быть от 0 до 7 (2³-1)
  5. E с 1 битом - диапазон может быть от 0 до 1 (2¹-1)

Сумма отдельных значений в битах составляет 15 + 35 + 10 + 3 + 1 = 64 бита.

Но наше «B» составляет всего 63. Итак, вы должны отпустить любой из них, чтобы он опустился ниже 64. Мы отпустим «E», что является 1 бит. Теперь наша сумма битов будет 63 бита, что равно «B».

Вот как мы хотим расположить все наши ценности в конце

Для этого есть 2 части.

  1. Кодирование
  2. Расшифровка

Кодировка -

Вот как «A» с 15 битами выглядит в 63-битном типе данных:

Нам нужно переместить все 15 A в крайний левый пустой бит. Нам нужно сдвинуть влево на 63–15 (A) = 48 бит.

A << 48

После сдвига влево это выглядит так:

Вот как «B» с 35 битами выглядит в 63-битном типе данных:

Если вы посмотрите на предыдущее изображение, «A» уже занимает 15 бит с левой стороны. Итак, нам нужно сдвинуть все 35 B, где заканчиваются 15 A.

Нам нужно сдвинуть влево на 63-15 (A) -35 (B) = 13 бит.

B << 13

После сдвига влево это выглядит так:

Вот как «C» с 10 битами выглядит в 63-битном типе данных:

Если вы посмотрите на предыдущее изображение, «A» уже заняло 15 бит, а «B» уже заняло 35 бит с левой стороны. Итак, нам нужно сдвинуть все 10 C, где заканчиваются 35 B

Нам нужно сдвинуть влево на 63–15 (A) –35 (B) -10 (C) = 3 бита.

C << 3

После сдвига влево это выглядит так:

Вот как «D» с 3 битами выглядит в 63-битном типе данных:

Если вы посмотрите на предыдущее изображение, «A» уже заняло 15 бит, «B» уже заняло 35 бит, а «C» уже занял 10 бит с левой стороны. Итак, нам нужно сдвинуть все 3 D, где заканчиваются 10 C

Нам нужно сдвинуть влево на 63–15 (A) –35 (B) -10 (C) -3 (D ) = 0 бит

D << 0

После сдвига влево это выглядит так:

Теперь у нас есть все биты «A», «B», «C», «D». на их соответствующих позициях, как показано ниже

Теперь мы хотим объединить их в одну переменную. Оператор | смотрит на каждый бит и возвращает 1, если бит равен 1 на любом из входов. Так:

0011 | 0101 = 0111

Если на одном входе бит равен 0, то вы получаете бит с другого входа. Посмотрев на (A << 48), (B << 13), (C << 3) и (D << 0), вы увидите, что если бит равен 1 для одного из них, это 0 для других. Так:

encodedValue = (A << 48) | (B << 13) | (C << 3) | (D << 0)

Теперь, когда мы закончили с частью «Кодирование», перейдем к части «Декодирование».

Расшифровка -

При кодировании мы использовали левый сдвиг (<<) и OR (|), но мы используем противоположное при декодировании. Мы используем сдвиг вправо (>>) и И (&).

Теперь мы хотим распаковать биты. Начнем с D. Мы хотим получить последние 3 бита и игнорировать первые 60 бит.

Для этого мы используем оператор &, который возвращает 1, только если оба входных бита равны 1. Так:

0011 & 0101 = 0001

Итак, если вы хотите распаковать только «n» битов с правой стороны, вам нужно выполнить И с «n» битами, в котором все «n» битов должны быть 1.

Чтобы получить «C», нам нужно сдвигать вправо, пока он не достигнет самого правого бита. Сдвиг вправо «C» с тем же номером, который вы использовали для сдвига влево во время кодирования, и выполнение операции И с 10 битами (поскольку «C» 10 бит) установлен в 1.

Проделайте то же самое с остальными элементами «B» и «A».

Сдвиньте вправо «B» на 13 и выполните операцию И с 35 битами (поскольку «B» - это 35 бит), установленным на 1.

Сдвиньте вправо «A» на 48 бит и выполните операцию И с 15 битами (поскольку «A» - 15 бит), установленным на 1.

Теперь мы декодировали одно закодированное значение в их собственные индивидуальные значения.

decodedD = (encodedValue >> 0)  & 0x7
decodedC = (encodedValue >> 3)  & 0x3FF
decodedB = (encodedValue >> 13) & 0x7FFFFFFFF
decodedA = (encodedValue >> 48) & 0x7FFF

Магические числа -

Существует очень высокая вероятность того, что вам должно быть интересно, что это за значение Hex и как получить это конкретное значение.

Во многих языках программирования для представления чисел можно использовать разные системы счисления, например 2 (двоичный), 6 (шестнадцатеричный), 8 (восьмеричный) и 10 (десятичный).

Здесь мы используем шестнадцатеричный код для представления чисел. Почему? Потому что представить несколько 1 в шестнадцатеричном формате проще, чем в любых других системах счисления.

Например, если вам нужно число с 4 битами, установленным на 1, то в двоичном формате оно будет представлено как 0b1111, а в шестнадцатеричном - как 0xF. Если вы не знаете шестнадцатеричный код, то вам, возможно, будет легко написать двоичный код, но вы не сможете записать 48 1 в двоичном формате. Но в Hex это можно написать как 0xFFFFFFFFFFFF. Вместо того, чтобы писать 48 1 в двоичной системе, мы пишем 12 F в шестнадцатеричной системе.

Итак, если вы не знаете, как работает шестнадцатеричная система, вам нужно об этом узнать. Это сама по себе интересная тема.

Хочешь со мной связаться? Свяжитесь со мной на Twitter.com/@SkrewEverything.

Нашли какие-нибудь ошибки? Комментарий ниже.

Понравилось? 👏👏👏 и поделитесь им.