Vid dynamisk belastningsbalansering vill vi allokera en uppsättning kunder (kulor) till en uppsättning servrar (bins) med målet att minimera den maximala belastningen på en server och även minimera antalet rörelser efter att ha lagt till eller tagit bort en server eller en klient 1. Vi vill ha en hashing-stil lösning där vi ger ID för en klient kan effektivt hitta sin server i en distribuerad dynamisk miljö. I en sådan dynamisk miljö kan både servrar och kunder läggas till och/eller tas bort från systemet i valfri ordning. De mest populära lösningarna för sådana dynamiska inställningar är Consistent Hashing [KLL + 97,SML + 03] eller Rendezvous Hashing [TR98]. Belastningsbalanseringen av dessa system är dock inte bättre än en slumpmässig tilldelning av kunder till servrar, så med n av varje, förväntar vi oss att många servrar överbelastas med  till (log n/ log log n) klienter. I detta dokument strävar vi efter att utforma hashsystem som uppnår önskad nivå av lastbalansering, samtidigt som antalet rörelser under alla tillägg eller borttagning av servrar eller kunder minimeras. I synnerhet, vi anser ett problem med m bollar och n bins, och med tanke på en användarspecificerad balanseringsparameter c = 1 + ε > 1, syftar vi till att hitta en hashing schema utan belastning över cm / n, som kallas kapaciteten i behållarna. Vår algoritmiska utgångspunkt är det konsekventa hashsystem där aktuella bollar och bins är hashed till en enhet cykel, och en boll placeras i den första bin efter varandra i medurs ordning. För att klara av givna kapacitetsbegränsningar tillämpar vi idén om linjär undersökning genom att vidarebefordra bollen på cirkeln till den första icke-fullständiga bin. Vi visar att i vårt hashsystem när en boll eller bin sätts in eller tas bort, det förväntade antalet bollar som måste flyttas är inom en multiplikativ faktor av O( 1 ε 2 ) av den optimala för ε ≤ 1 (Theorem 3) och inom en faktor 1 + O( log c ) av den optimala för ε ≥ 1 (Theorem 2). Tekniskt sett är den senare bunden den mest utmanande att bevisa. Det innebär att vi för superkonstant c, vi betalar bara en försumbar kostnad i extra drag. Vi får också samma gränser för det enklare problemet där vi istället för en användare specificerad balanseringsparameter har en fast bin kapacitet C för alla behållare, och definiera c = 1 + ε = Cn / m.
Ihållande belastningsbalansering utvidgades REF till att omfatta garantier för maximal belastning.
Consistent Hashing with Bounded Loads
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}