Послідовне хешування – веб-сайт Елі Бендерського

Послідовне хешування – веб-сайт Елі Бендерського


Ця публікація є вступом до узгодженого хешування, алгоритму для розробки хеш-таблиці так, що тільки невелика частина ключів повинна бути повторно обчислена, коли розмір таблиці змінюється.

Мотивуючий варіант використання

Припустімо, ми розробляємо кешуючий веб-проксі, але очікувані вимоги до пам’яті вищі, ніж може впоратися одна машина. Тому ми розподіляємо кеш між кількома машинами. Як ми це робимо? За наявності URL-адреси, як ми переконаємося, що ми можемо легко дізнатися, до якого сервера нам слід звернутися для потенційно кешованої версії?

Підхід, який одразу спадає на думку хешування. Давайте обчислимо числовий хеш URL-адреси та рівномірно розподілимо його між N вузлами (саме так ми називатимемо сервери в цій публікації):

hash := calculateHashFunction(url)
nodeId := hash % N

Цей процес працює, але виявляється, що він має серйозні недоліки в реальних програмах.

Проблема з наївним підходом хешування

Знову розглянемо наш випадок використання кешування; у реалістичному додатку в «інтернет-масштабі» одне з припущень, які ми зробили, явно не виконується — вузли кешу не є статичними. Нові вузли додаються до системи, якщо навантаження велике (або якщо в експлуатацію надходять нові машини); існуючі вузли можуть вийти з ладу або бути відключеними для обслуговування. Іншими словами, кількість Н у нашому додатку не є константою.

Проблема може бути очевидною зараз; щоб продемонструвати це безпосередньо, розглянемо реальну реалізацію hashitem за допомогою Go md5 пакет:

// hashItem computes the slot an item hashes to, given a total number of slots.
func hashItem(item string, nslots uint64) uint64 {
  digest := md5.Sum(()byte(item))
  digestHigh := binary.BigEndian.Uint64(digest(8:16))
  digestLow := binary.BigEndian.Uint64(digest(:8))
  return (digestHigh ^ digestLow) % nslots
}

Термінологія трохи скоригована:

  • Замість того, щоб urlми будемо посилатися на загальний пункт
  • «Слот» — поширене поняття в хеш-таблицях: our hashitem обчислює номер слота для елемента, враховуючи загальну кількість доступних слотів

Скажімо, ми почали з 32 слотів і хешували рядки "привіт",
"послідовний" і "бабак". Отримуємо такі слоти:

hello       (n=32): 4
consistent  (n=32): 14
marmot      (n=32): 5

Тепер припустимо, що додано ще один вузол і підсумок nslots зростає до 33. Знову хешуємо наші елементи:

hello       (n=33): 23
consistent  (n=33): 18
marmot      (n=33): 31

Всі слоти змінені!

Це значна проблема з наївним підходом хешування. Будь-коли
nslots зміни, ми отримуємо абсолютно різні слоти для практично будь-якого предмета. У реалістичній програмі це означає, що щоразу, коли новий вузол приєднується або залишає наш кешуючий кластер, відбуватиметься потік кеш-промахів за кожним запитом, доки новий кластер не заспокоїться. І зміни вузлів іноді відбуваються в самий незручний час; Уявіть, що навантаження різко зростає (можливо, про сайт було згадано в резонансному інформаційному виданні або відбувається пряма трансляція події), і для цього додаються нові вузли. Це не найкращий час для тимчасової втрати кешування!

Послідовне хешування

Послідовний алгоритм хешування вирішує проблему елегантним способом. Ключова ідея полягає в тому, щоб відобразити і вузли, і елементи на інтервалі, а потім елемент належить найближчому до нього вузлу. Конкретно, ми беремо одиничне коло та зіставляємо вузли та елементи з кутами на цьому колі. Ось приклад, який докладніше пояснює, як працює цей метод:

Послідовне хешування – веб-сайт Елі Бендерського

Тут показано п’ять вузлів: від N1 до N5 і три елементи: Ix, Iy, Iz. Спочатку ми додаємо вузли: використовуючи операцію хешування, ми відображаємо їх на коло (подробиці пізніше). Потім, коли елементи надходять, ми визначаємо, до якого вузла вони належать, наступним чином:

  • Використовуйте ту саму операцію хешування, щоб знайти розташування елемента в колі
  • Вузол, якому належить цей елемент, є найближчим за годинниковою стрілкою

На нашій діаграмі Ix відображається на N1, Iy на N2, а Iz на N3. Поки все добре, але переваги цього підходу стають очевидними, коли вузли змінюються. У нашій діаграмі припустимо, що N3 видалено. Тоді Iz відобразиться на N5.
Відображення інших елементів не змінюється!

Додавання вузлів має аналогічний результат. Якщо додається новий вузол N6 і він хешується до позиції між Iy і N2 на колі, з цього моменту Iy буде зіставлено з N6, але інші елементи збережуть своє відображення.

Припустимо, у нас є всього М предмети, які нам потрібно розподілити Н
вузлів. Використовуючи наївний підхід хешування, коли ми додаємо або видаляємо вузол, усе
М елементи змінюють своє відображення. З іншого боку, при послідовному хешуванні необхідно змінити лише приблизно. Це величезна різниця.

Оригінальний документ про послідовне хешування (див. ) називає це властивість монотонності алгоритму:

Якщо елементи спочатку призначаються набору сегментів, а потім до форми додаються нові контейнери, тоді елемент може переміщуватися зі старого сегмента в новий, але не з одного старого сегмента в інший.

Впровадження узгодженого хешування

Реалізувати узгоджений алгоритм хешування, як описано вище, досить легко. Найважливіша частина реалізації полягає в тому, щоб знайти вузол, на який зіставляється елемент – це передбачає певний пошук. Оригінальний документ про послідовне хешування пропонує використовувати збалансоване бінарне дерево для пошуку; реалізація, яку я тут демонструю, використовує дещо інший, але еквівалентний підхід: бінарний пошук у лінійному масиві позицій вузлів (слотів).

По-перше, деякі практичні міркування:

  • Теоретично одиничне коло можна розглядати як безперервний діапазон
    (0, 1). Однак у програмуванні ми надаємо перевагу дискретній області, тому ми збираємося «квантувати» цей діапазон, щоб (0, розмір кільця)де
    Розмір кільця є деяким достатньо великим числом, яке уникає зіткнень.
  • Дивлячись на кругову діаграму вище, уявіть, що 0 градусів — це «північ» (12 годин), а кути збільшуються за годинниковою стрілкою. У нашій дискретній області 12 годин – це 0, а 3 години – це Розмір кільця/4і так далі.

Коли вузол додається до узгодженого хешу, його розташування визначається за допомогою хеш-функції, як hashitem як описано вище, с
nslots=розмір кільця. Вузли зберігаються за допомогою пари структур даних, як показано нижче; у цьому прикладі використовуються приблизні розташування вузлів від N1 до N5 на круговій діаграмі вище (припустимо, Розмір кільця=1024 тут):

Вузли та масиви слотів для показано вище

Позиції вузлів на колі зберігаються в слотиякий сортується. вузлів містить відповідні імена вузлів. Для кожного i,
вузли (i) знаходиться на позиції слоти(i) на колі.

Ось ConsistentHasher структура даних у Go:

type ConsistentHasher struct {
  // nodes is a list of nodes in the hash ring; it's sorted in the same order
  // as slots: for each i, the node at index slots(i) is nodes(i).
  nodes ()string

  // slots is a sorted slice of node indices.
  slots ()uint64

  ringSize uint64
}

// NewConsistentHasher creates a new consistent hasher with a given maximal
// ring size.
func NewConsistentHasher(ringSize uint64) *ConsistentHasher {
  return &ConsistentHasher{
    ringSize: ringSize,
  }
}

І ось як реалізовано пошук того вузла, якому даний елемент відповідає:

// FindNodeFor finds the node an item hashes to. It's an error to call this
// method if the hasher doesn't have any nodes.
func (ch *ConsistentHasher) FindNodeFor(item string) string {
  if len(ch.nodes) == 0 {
    panic("FindNodeFor called when ConsistentHasher has no nodes")
  }
  ih := hashItem(item, ch.ringSize)

  // Since ch.slots is a sorted list of all the node indices for our nodes, a
  // binary search is what we need here. ih is mapped to the node that has the
  // same or the next larger node index. slices.BinarySearch does exactly this,
  // by returning the index where the value would be inserted.
  slotIndex, _ := slices.BinarySearch(ch.slots, ih)

  // When the returned index is len(slots), it means the search wrapped
  // around.
  if slotIndex == len(ch.slots) {
    slotIndex = 0
  }

  return ch.nodes(slotIndex)
}

Ключовим тут є виклик бінарного пошуку. Додавання та видалення вузлів виконується аналогічно за допомогою бінарного пошуку – дивіться повний код.

Кращий розподіл предметів за допомогою віртуальних вузлів

Поширеною проблемою, яка виникає під час впровадження узгодженого хешування, є незбалансований розподіл елементів між різними вузлами. З елементами та загальною кількістю вузлів, середній Розподіл буде приблизно на вузол, але на практиці це буде не дуже збалансовано – деякі вузли матимуть набагато більше призначених елементів, ніж інші (дивіться Додаток для отримання додаткової інформації).

У реальній програмі це може означати, що деякі кеш-сервери будуть набагато зайнятіші, ніж інші, що є поганою річчю щодо планування ємності та ефективного використання HW. На щастя, є елегантне налаштування послідовного алгоритму хешування, яке значно пом’якшує проблему: віртуальні вузли.

Замість того, щоб зіставляти кожен вузол з окремим розташуванням кола, ми будемо зіставляти його з В місця натомість. Є кілька способів зробити це – найпростіший – це просто змінити назву вузла якимось чином. Наприклад, коли
AddNode називається додати вузолвін буде працювати:

for i := range V {
  vnodeName = fmt.Sprintf("%v@%v", node, i)

  // ... now add vnodeName to the nodes/slots slices
}

Тоді, під час пошуку елемента ми зіткнемося з одним із віртуальних вузлів, декодуємо назву вузла з нього (у нашому прикладі просто видаліть @ суфікс) і поверніть це. Реалізація видалення вузла так само проста.

Ідея полягає в тому, що заданий вузол з іменем фуімена віртуальних вузлів
foo@0, foo@1, foo@2 тощо будуть розподілені по всьому колу, а не групуватися в одному місці. Перегляньте Додаток, щоб розрахувати, як це впливає на остаточний розподіл.

Вихідний код цієї публікації містить a ConsistentHasherV тип, який дуже схожий на ConsistentHasherза винятком того, що він реалізує стратегію віртуального вузла. Користувальницький інтерфейс залишився незмінним – дещо змінилася лише внутрішня реалізація.

Код

Повний вихідний код цієї публікації є на GitHub.

Додаток

Якість хеш-функції дуже важлива для гарного перетасування вузлів у колі, але навіть якщо ми візьмемо ідеальну хеш-функцію, яка створює рівномірно розподілені значення, результат, ймовірно, буде неоптимальним для наших потреб.

Скажімо, ми вибираємо точки на одиничному колі рівномірно в діапазоні
(0, 1). Якщо ми відсортуємо точки за кутом, проміжки між сусідніми кутами є статистикою порядку. Вони відповідають бета-розповсюдженню з параметрами (1, N-1)що має середнє значення та дисперсію .

Це досить суттєво. Розглянемо коло з 20 вузлами. Стандартним відхиленням розподілу є квадратний корінь із дисперсії; підставляючи , отримуємо:

З 20 вузлами, рівномірно розподіленими по колу, ми можемо очікувати в середньому 18 градусів відстані між двома вузлами. Стандартне відхилення 0,048 означає 17 градусів, що можна порівняти із середнім!

Ми також можемо навести реалістичний приклад, щоб продемонструвати це. Давайте згенеруємо 20 випадкових кутів на колі та покажемо, як виглядає розподіл вузлів:

Коло з довільно розподіленими точками

У цьому конкретному зразку середній кут між двома сусідніми вузлами становить 18 градусів (як очікувалося). Найменший кут становить лише 1,04 градуса, а найбільший – 42 градуси. Це означає, що деякі вузли отримають у 40 разів більше елементів, призначених їм, ніж інші!

Легко побачити, як віртуальні вузли допомагають; уявіть, що кожен сервер відображає деяку кількість випадково розподілених вузлів на колі; деякі з них будуть далі, ніж інші, від найближчого сусіда, але в середньому буде набагато менше різноманітності. Математично дано набір п рівномірно розподілені випадкові величини з дисперсією vдисперсія їх середнього становить .

Як конкретний експеримент я запустив симуляцію, подібну до наведеної вище, але з 10 віртуальними вузлами на вузол. Ми розглядатимемо загальну частину кола, що відображається на вузол, коли воно відображається на будь-якому зі своїх віртуальних вузлів. У той час як середнє значення залишається 18 градусів, дисперсія суттєво скорочується – найменша становить 11 градусів, а найбільша – 26.

Ви можете знайти код для цих експериментів у Demo.go файл репозиторію вихідного коду.




Source link

Postagens Similares

  • ਮੇਰੀ ਜੇਕੀਲ ਸਾਈਟ ‘ਤੇ ਟਿੱਪਣੀਆਂ ਸ਼ਾਮਲ ਕਰਨਾ

    📅 21 ਨਵੰਬਰ 2025 | ⏱️ ~3 ਮਿੰਟ ਪੜ੍ਹੋ ਮੈਂ ਪਿਛਲੇ ਕੁਝ ਮਹੀਨਿਆਂ ਤੋਂ ਟਿੱਪਣੀਆਂ ਲਈ ਸਮਰਥਨ ਜੋੜਨ ‘ਤੇ ਕੰਮ ਕਰ ਰਿਹਾ ਹਾਂ। ਇੱਕ ਸਥਿਰ ਸਾਈਟ ‘ਤੇ, ਇਹ ਔਖਾ ਹੈ, ਪਰ ਅੰਤ ਵਿੱਚ ਇਹ ਹੋ ਗਿਆ ਹੈ। ਕੁਝ ਮਹੀਨੇ ਪਹਿਲਾਂ ਮੌਰੀਸ ਰੇਂਕ ਅਤੇ ਮੈਂ ਫੈਡੀ (ਮੇਰੇ ਖਿਆਲ ਵਿੱਚ) ‘ਤੇ ਗੱਲਬਾਤ ਕਰ ਰਹੇ ਸੀ ਅਤੇ ਉਸਨੇ…

  • 評論:夜行者(馬克·羅森)

    夜人 故意是「無人問津的馬克朗森的書」。這不是關於贏得格萊美獎的超級製作人,而是關於這位工作 DJ 多年來“拖著板條箱進入酒吧和夜總會”、閱覽室並點燃舞池。 自始至終,羅森都坦誠地談論毒品和夜生活的過度。他講述了在隧道中混合物質、意外吸食海洛因、看著人們滑入 K 洞的經歷,並展示了這個世界是多麼令人興奮和殘酷。他聲稱正是焦慮和恐慌發作使他擺脫了毒癮。 這本書同樣誠實地講述了他成長的環境和特權世界。從搖滾明星繼父米克瓊斯(《外國人》中的主音吉他手,他可以悄悄地「借用​​」一箱箱放克和靈魂音樂)到以他上大學為條件為他買下 Technics 的母親,到他祖父設立的信託基金安全網,以及普遍接近成名的生活。儘管如此,Ronson 對 DJ 和這項特權似乎打開的側門總是很謙虛,例如在其他人苦苦掙扎多年的時候直接進入 Peter Gatien 的美國俱樂部。 對於大多數 DJ 來說,進入加蒂恩的俱樂部意味著在獲得 Club USA 的一席之地之前要在小酒吧和燈光昏暗的密室裡進行多年的表演。我應該需要那麼長時間來建立聯繫,逐漸向上。相反,我偶然發現了它。我已經擁有大多數其他人所沒有的優勢。我媽媽買了裝備給我。我是由一位擁有家庭工作室的音樂家撫養長大的。但即使對我來說,這也是一個荒謬的幸運突破。參加美國俱樂部比賽的想法是超現實的。我覺得對於這麼大的舞台來說太綠了。但我沒有辦法拒絕它。 資料來源:《夜行人》馬克‧羅森 (Mark Ronson) 著 我發現這本書的有趣之處在於羅森如何帶我們了解一門看似失傳的藝術。他講述了在 Rock and Soul 購買第一張套牌的經歷,弄清楚這一切是如何運作的,學習閱讀不同的房間和觀眾,透過 BPM 在黏性標籤上構建套牌,轟炸、咬合、改進,並慢慢贏得尊重。我對他打電話給年長的同學曼尼·艾姆斯 (Manny Ames) 詢問刮盤課程的經驗特別感興趣。 “你有貼紙嗎?”我爭先恐後地尋找一些麥克賽爾盒式磁帶標籤。他隨意地把它們撕下來,並向我展示瞭如何通過將貼紙從中心孔向外粘貼,就像指南針上的針一樣,對同一張唱片的兩份副本進行標記。「這樣,當您來回運行兩張唱片時,您將始終知道自己在視覺上的位置,」他說,並分享了一些既簡單又令人興奮的事情。貼紙使他能夠透過追蹤唱片的每轉,將唱片旋轉回精確的位置——2 點鐘、7 點鐘等。鐘面上的每個位置都對應於特定的聲音:大鼓可能位於 3 點鐘位置,軍鼓位於 9 點鐘位置,這樣就可以一致地找到並重複節拍的任何部分。 資料來源:《夜行人》馬克‧羅森 (Mark Ronson) 著 憑藉這一洞察力,羅森證明了成功只是時間,而不是魔法。(1) 這包括每週八場演出,口袋裡裝著無窮無盡的演示磁帶,週二晚上在狹小的房間裡演奏。 Ronson 在觀看 DJ AM 使用兩張唱片重新排序歌詞後指出了努力和練習的地方。 「老兄。你是怎麼學會這些東西的?!!」我問,仍在嘗試處理。「夥計……剛剛在嬰兒床裡觀看了老DMC的戰鬥並自學了常規。當你戒掉可卡因時你能做什麼,真是太瘋狂了。」他咯咯地笑了一聲,吸了一口煙。看著散落一地的…

  • Listen over N ting

    september 2009 Jeg vedder på at du den nåværende utgaven av Kosmopolitisk har en artikkel hvis tittel begynner med et tall. “7 ting han ikke vil fortelle deg om sex,” eller noe sånt. Noen populære magasiner har artikler av denne typen på forsiden av hver utgave. Det kan ikke skje ved et uhell. Redaktører må…

  • ਪੈਨਸੀਵ: ਮਾਰਚ 8 2024 – ਡੂਨ 2 ਨੂੰ

    ਜਨਤਕ ਵਿਚਾਰਾਂ ਦਾ ਸੰਗ੍ਰਹਿ ਜੋ ਬਲੌਗਪੋਸਟ ਹੋ ਸਕਦਾ ਹੈ ਪਰ ਮੇਰੇ ਕੋਲ ਸਮਾਂ ਨਹੀਂ ਹੈ, ਇਸ ਲਈ ਇੱਥੇ ਛੋਟਾ ਰੂਪ ਹੈ। ਮੈਂ ਭਵਿੱਖ ਵਿੱਚ ਇਹਨਾਂ ਨੂੰ ਪੂਰੀਆਂ ਪੋਸਟਾਂ ਵਿੱਚ ਅੱਪਗ੍ਰੇਡ ਕਰ ਸਕਦਾ ਹਾਂ। Source link

  • پینٹ کی ایک اور نئی چاٹ

    20 مارچ 2026 تو پتہ چلتا ہے کہ مجھے سرسوں کا پیلا اور سٹیل کا نیلا ڈیزائن پسند نہیں آیا جو میں نے کچھ ہفتے پہلے بنایا تھا۔ یہ میرے ساتھ ٹھیک نہیں بیٹھا تھا، اور اگر میں اپنی ڈیزائن کی تاریخ پر نظر ڈالتا ہوں تو وہ ڈیزائن جو برسوں سے پھنس گئے ہیں،…

Deixe um comentário

O seu endereço de email não será publicado. Campos obrigatórios marcados com *