Konsistent hashing
Fra Wikipedia, den frie encyklopedi
Konsistent hashing er en teknikk for indeksering i et datanett. Det er en variant av hashing som forsøker å fordele lagringen likt på de ulike bøtter i tabellen. Dette er spesielt anvendelig i en distribuert hashtabell, der ansvaret for lagring er spredt på flere noder i et datanett.
Hver bruker har et synsfelt (view) bestående av en andel av tabellens bøtter. Andelen er fast, men kan bestå av ulike bøtter over tid. Ulike brukere kan ha forskjellige synsfelt, men når de arbeider med felles bøtter, vil hashfunksjonen med overveldende sannsynlighet, sikre at arbeidet skjer mot samme ansvarlige, slik at en unngår inkonsistens, sprikende tilstand.
Dette gjør at en kan lagre tabellen distribuert, uten å kopiere endringer til alle noder når endringene skjer. Nye bøtter er betraktelig enklere å legge til, og ved oppslag tar det kun O(1) tid.
Teknikken ble først utviklet ved Massachusetts Institute of Technology og beskrevet i
- Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., and Lewin, D. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web. I: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ACM Press, side 654–663, 1997.
