8000 chtest: fix segments-per-key calculation & add layout explanation by dfinkel · Pull Request #68 · vimeo/galaxycache · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

chtest: fix segments-per-key calculation & add layout explanation #68

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
May 5, 2025
Merged

chtest: fix segments-per-key calculation & add layout explanation #68

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
f404f6f
chtest: fix segments_per_key calculation
dfinkel May 5, 2025
863a413
chtest: add block comment explaining hash layout
dfinkel May 5, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
34 changes: 33 additions & 1 deletion consistenthash/chtest/fake_hash.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -70,9 +70,41 @@ func (m *MapArgs) NewMap() *consistenthash.Map {
// it computes required value of segsPerKey to make every ordering of
// the entries in owners appear in the hashring.
func NewMapArgs(args Args) MapArgs {

///////////////////////////////////////////////////////////////////////////
// Here's how this works:
// We not only need segments owned by each individual owner, but we
// need to arrange for segments that fallthrough to each other owner.
// To make this possible, for each pair of owners, we insert 4 segments to cover both orderings.
// For the n=2 case, this will look like (4 segments):
// | a | b | b | a |
// Note: we could make a pass that coalesces this into 2 segments
// instead of 4, but it's not worth the complexity in a test package.
//
// As a result, although we have n * (n-1) pairs, we need another factor of 2.
//
// Similarly, the n = 3 case looks more complicated (12 segments):
// | a | b | a | c | b | a | b | c | c | a | c | b |
//
// We try to distribute the segments between 0 and 2^31 to make things
// robust, and have space for everything without having to deal with
// signed/unsigned conversion issues or overflows.
//
// For Fallthrough keys, we pick the lowest value for the segment that
// we created for that specific fallthrough.
// For Single-owner keys, we just pick the first segment for that owner.
// Pre-registered keys work the same as single-owner keys, but are
// stored in a separate map.
//
// The keen-eyed observer will note that there are some segments that
// can be merged/dedup'd in the n=3 case as well, but as this is a
// test-helper package, simplicity is the most important, so it isn't
// worth complicating this code with any merging/simplification logic.
//////////////////////////////////////////////////////////////////////////

owners := args.Owners
ownersMap := make(map[string][]hashRange, len(owners))
segsPerKey := len(owners) - 1
segsPerKey := (len(owners) - 1) * 2 // we need to cover both orderings for each pair
nSegs := segsPerKey * len(owners)
type indexedString struct {
idx int
Expand Down
101 changes: 99 additions & 2 deletions consistenthash/chtest/fake_hash_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -7,7 +7,7 @@ import (
"testing"
)

func TestMapArgs(t *testing.T) {
func TestMapArgs3Peers(t *testing.T) {
// owners
const (
peer1 = "peer1"
Expand All @@ -27,7 +27,7 @@ func TestMapArgs(t *testing.T) {
"p1p2explicit": {peer1, peer2},
},
})
if expSegs := 2; ma.NSegsPerKey != expSegs {
if expSegs := 4; ma.NSegsPerKey != expSegs {
t.Errorf("unexpected number of key segments: %d; expected %d", ma.NSegsPerKey, expSegs)
}
// make the full map function-scope so we can log it in error cases for later scopes
Expand Down Expand Up @@ -93,3 +93,100 @@ func TestMapArgs(t *testing.T) {
}

}

func TestMapArgs2Peers(t *testing.T) {
// owners
const (
peer1 = "peer1"
peer2 = "peer2"
)
soP1 := SingleOwnerKey(peer1)
soP2 := SingleOwnerKey(peer2)
ftP1P2 := FallthroughKey(peer1, peer2)
ftP2P1 := FallthroughKey(peer2, peer1)

ma := NewMapArgs(Args{
Owners: []string{peer1, peer2},
RegisterKeys: map[string][]string{
"allpeers": nil,
"p1explicit": {peer1},
"p2explicit": {peer2},
"p1p2explicit": {peer1, peer2},
},
})
if expSegs := 2; ma.NSegsPerKey != expSegs {
t.Errorf("unexpected number of key segments: %d; expected %d", ma.NSegsPerKey, expSegs)
}
// make the full map function-scope so we can log it in error cases for later scopes
fullMap := ma.NewMap()
fullMap.Add(peer1, peer2)
{
if soP1Owner := fullMap.Get(soP1); soP1Owner != peer1 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", soP1, soP1Owner, peer1)
}
if soP2Owner := fullMap.Get(soP2); soP2Owner != peer2 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", soP2, soP2Owner, peer2)
}
if soP1Owner := fullMap.Get(ftP1P2); soP1Owner != peer1 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", ftP1P2, soP1Owner, peer1)
}
if soP2Owner := fullMap.Get(ftP2P1); soP2Owner != peer2 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", ftP2P1, soP2Owner, peer2)
t.Logf("full ring: %+v", fullMap)
t.Logf("p2p1 hash: %d", ma.HashFunc([]byte(ftP1P2)))
}
if explAllOwner := fullMap.Get("allpeers"); explAllOwner != peer1 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", "allpeers", explAllOwner, peer1)
}
// fetch with the same number of replicas as peers
if explAllOwner := fullMap.GetReplicated("allpeers", 2); !slices.Equal(explAllOwner, []string{peer1, peer2}) {
t.Errorf("unexpected peer owners for key %q; got %v; want %v", "allpeers", explAllOwner, []string{peer1, peer2})
}
// fetch with more replicas than peers
if explAllOwner := fullMap.GetReplicated("allpeers", 8); !slices.Equal(exp A166 lAllOwner, []string{peer1, peer2}) {
t.Errorf("unexpected peer owners for key %q; got %v; want %v", "allpeers", explAllOwner, []string{peer1, peer2})
}
if explP1Owner := fullMap.Get("p1explicit"); explP1Owner != peer1 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", "p1explicit", explP1Owner, peer1)
}
if explP2Owner := fullMap.Get("p2explicit"); explP2Owner != peer2 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", "p2explicit", explP2Owner, peer2)
}
if explP1P2Owner := fullMap.GetReplicated("p1p2explicit", 2); !slices.Equal(explP1P2Owner, []string{peer1, peer2}) {
t.Errorf("unexpected peer owners for key %q; got %v; want %v", "p1p2explicit", explP1P2Owner, []string{peer1, peer2})
}
}
{
ftP1P2 := FallthroughKey(peer1, peer2)
mapSansPeer1 := ma.NewMap()
mapSansPeer1.Add(peer2)
if soP1Owner := mapSansPeer1.Get(soP1); soP1Owner == peer1 {
t.Errorf("unexpected peer owner for key %q; got %q; wanted something other than %q (excluded from ring)", soP1, soP1Owner, peer1)
}
if soP2Owner := mapSansPeer1.Get(soP2); soP2Owner != peer2 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", soP2, soP2Owner, peer2)
}
if soP2Owner := mapSansPeer1.Get(ftP1P2); soP2Owner != peer2 {
t.Errorf("unexpected fallthrough peer owner for key %q; got %q; want %q", ftP1P2, soP2Owner, peer2)
t.Logf("sans 1 ring: %+v", mapSansPeer1)
t.Logf("full ring: %+v", fullMap)
t.Logf("p2FallThrough hash: %d", ma.HashFunc([]byte(ftP1P2)))
}
}
{
mapSansPeer1 := ma.NewMap()
mapSansPeer1.Add(peer1)
if soP2Owner := mapSansPeer1.Get(soP2); soP2Owner == peer2 {
t.Errorf("unexpected peer owner for key %q; got %q; wanted something other than %q (excluded from ring)", soP2, soP2Owner, peer2)
}
if soP2Owner := mapSansPeer1.Get(soP2); soP2Owner != peer1 {
t.Errorf("unexpected peer owner for key %q; got %q; want %q", soP2, soP2Owner, peer1)
}
if soP2Owner := mapSansPeer1.Get(ftP2P1); soP2Owner != peer1 {
t.Errorf("unexpected fallthrough peer owner for key %q; got %q; want %q", ftP2P1, soP2Owner, peer1)
t.Logf("sans 1 ring: %+v", mapSansPeer1)
t.Logf("full ring: %+v", fullMap)
t.Logf("p2FallThrough hash: %d", ma.HashFunc([]byte(ftP2P1)))
}
}
}
0