TrueCloudLab/frostfs-sdk-go
30
0
Fork 20
Code Issues 29 Pull requests 1 Releases Activity Actions

pool: Sampler isn't protected by mutex #221

New issue
Closed
opened 2024-05-08 11:46:14 +00:00 by dkirillov · 2 comments
dkirillov commented 2024-05-08 11:46:14 +00:00
Member
Copy link

Expected Behavior

Sampler is thread safe.

Current Behavior

Sometimes we get panic:

мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: 2024-05-08T06:17:58.536Z        error        middleware/policy.go:49        policy validation failed        {"request_id": "f0ac6927-2c88-45b7-ac19-0a196f950ec5", "error": "get frostfs container: read container via connection pool: no healthy client"}
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:  panic: runtime error: index out of range [-2]
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:  -> math/rand.(*rngSource).Uint64
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:  ->   math/rand/rng.go:249
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     math/rand.(*rngSource).Int63
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       math/rand/rng.go:234
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     math/rand.(*Rand).Int63
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       math/rand/rand.go:96
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     math/rand.(*Rand).Float64
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       math/rand/rand.go:207
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool.(*sampler).Next
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d/pool/sampler.go:64
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool.(*innerPool).connection
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d/pool/pool.go:2142
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool.(*Pool).connection
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d/pool/pool.go:2121
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool.(*Pool).GetContainer
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d/pool/pool.go:2637
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-s3-gw/internal/frostfs.(*FrostFS).Container
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-s3-gw/internal/frostfs/frostfs.go:98
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/layer.(*layer).containerInfo
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/layer/container.go:49
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/layer.(*layer).GetBucketInfo
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/layer/layer.go:437
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/handler.(*handler).ResolveBucket
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/handler/util.go:82
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/middleware.policyCheck
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/middleware/policy.go:70
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api.NewRouter.PolicyCheck.func7.1
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:       git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/middleware/policy.go:48
мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]:     net/http.HandlerFunc.ServeHTTP

Possible Solution

Since random generator isn't thread safe but we invoke it from multiple goroutines we must protect it with mutex .

diff --git a/pool/sampler.go b/pool/sampler.go
index f5b6635..8798222 100644
--- a/pool/sampler.go
+++ b/pool/sampler.go
@@ -1,13 +1,18 @@
 package pool
 
-import "math/rand"
+import (
+	"math/rand"
+	"sync"
+)
 
 // sampler implements weighted random number generation using Vose's Alias
 // Method (https://www.keithschwarz.com/darts-dice-coins/).
 type sampler struct {
+	mu              sync.Mutex
 	randomGenerator *rand.Rand
-	probabilities   []float64
-	alias           []int
+
+	probabilities []float64
+	alias         []int
 }
 
 // newSampler creates new sampler with a given set of probabilities using
@@ -60,8 +65,13 @@ func newSampler(probabilities []float64, source rand.Source) *sampler {
 // Next returns the next (not so) random number from sampler.
 func (g *sampler) Next() int {
 	n := len(g.alias)
+
+	g.mu.Lock()
 	i := g.randomGenerator.Intn(n)
-	if g.randomGenerator.Float64() < g.probabilities[i] {
+	f := g.randomGenerator.Float64()
+	g.mu.Unlock()
+
+	if f < g.probabilities[i] {
 		return i
 	}
 	return g.alias[i]

Steps to Reproduce (for bugs)

Run the following test several times:

func TestBug(t *testing.T) {
	probabilities := []float64{0.1, 0.2, 0.7}
	s := newSampler(probabilities, rand.NewSource(0))

	for i := 0; i < 10000; i++ {
		n := 100
		var wg sync.WaitGroup
		wg.Add(n)

		for j := 0; j < n; j++ {
			go func() {
				for k := 0; k < 10; k++ {
					s.Next()
				}
				wg.Done()
			}()
		}

		wg.Wait()
	}
}

Regression

Yes

Your Environment

  • Version used: git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d
<!--- Provide a general summary of the issue in the Title above --> ## Expected Behavior [Sampler](https://git.frostfs.info/TrueCloudLab/frostfs-sdk-go/src/commit/02c936f397c7bb9e1e7ca4e71b548f4deaaa32a1/pool/sampler.go#L7) is thread safe. ## Current Behavior Sometimes we get panic: ``` мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: 2024-05-08T06:17:58.536Z error middleware/policy.go:49 policy validation failed {"request_id": "f0ac6927-2c88-45b7-ac19-0a196f950ec5", "error": "get frostfs container: read container via connection pool: no healthy client"} мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: panic: runtime error: index out of range [-2] мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: -> math/rand.(*rngSource).Uint64 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: -> math/rand/rng.go:249 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: math/rand.(*rngSource).Int63 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: math/rand/rng.go:234 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: math/rand.(*Rand).Int63 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: math/rand/rand.go:96 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: math/rand.(*Rand).Float64 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: math/rand/rand.go:207 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool.(*sampler).Next мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d/pool/sampler.go:64 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool.(*innerPool).connection мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d/pool/pool.go:2142 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool.(*Pool).connection мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d/pool/pool.go:2121 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool.(*Pool).GetContainer мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d/pool/pool.go:2637 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/internal/frostfs.(*FrostFS).Container мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/internal/frostfs/frostfs.go:98 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/layer.(*layer).containerInfo мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/layer/container.go:49 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/layer.(*layer).GetBucketInfo мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/layer/layer.go:437 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/handler.(*handler).ResolveBucket мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/handler/util.go:82 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/middleware.policyCheck мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/middleware/policy.go:70 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api.NewRouter.PolicyCheck.func7.1 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: git.frostfs.info/TrueCloudLab/frostfs-s3-gw/api/middleware/policy.go:48 мая 08 06:17:58 vikingrock-node2 frostfs-s3-gw[8913]: net/http.HandlerFunc.ServeHTTP ``` ## Possible Solution Since [random generator](https://git.frostfs.info/TrueCloudLab/frostfs-sdk-go/src/commit/02c936f397c7bb9e1e7ca4e71b548f4deaaa32a1/pool/sampler.go#L8) isn't thread safe but we invoke it from [multiple goroutines](https://git.frostfs.info/TrueCloudLab/frostfs-sdk-go/src/commit/02c936f397c7bb9e1e7ca4e71b548f4deaaa32a1/pool/pool.go#L2146) we must protect it with mutex . ```diff diff --git a/pool/sampler.go b/pool/sampler.go index f5b6635..8798222 100644 --- a/pool/sampler.go +++ b/pool/sampler.go @@ -1,13 +1,18 @@ package pool -import "math/rand" +import ( + "math/rand" + "sync" +) // sampler implements weighted random number generation using Vose's Alias // Method (https://www.keithschwarz.com/darts-dice-coins/). type sampler struct { + mu sync.Mutex randomGenerator *rand.Rand - probabilities []float64 - alias []int + + probabilities []float64 + alias []int } // newSampler creates new sampler with a given set of probabilities using @@ -60,8 +65,13 @@ func newSampler(probabilities []float64, source rand.Source) *sampler { // Next returns the next (not so) random number from sampler. func (g *sampler) Next() int { n := len(g.alias) + + g.mu.Lock() i := g.randomGenerator.Intn(n) - if g.randomGenerator.Float64() < g.probabilities[i] { + f := g.randomGenerator.Float64() + g.mu.Unlock() + + if f < g.probabilities[i] { return i } return g.alias[i] ``` ## Steps to Reproduce (for bugs) Run the following test several times: ```golang func TestBug(t *testing.T) { probabilities := []float64{0.1, 0.2, 0.7} s := newSampler(probabilities, rand.NewSource(0)) for i := 0; i < 10000; i++ { n := 100 var wg sync.WaitGroup wg.Add(n) for j := 0; j < n; j++ { go func() { for k := 0; k < 10; k++ { s.Next() } wg.Done() }() } wg.Wait() } } ``` ## Regression Yes ## Your Environment * Version used: git.frostfs.info/TrueCloudLab/frostfs-sdk-go@v0.0.0-20240402141532-e5040d35e99d
dkirillov added the
bug
 label 2024-05-08 11:46:14 +00:00
fyrchik commented 2024-05-08 11:49:28 +00:00
Owner
Copy link

https://pkg.go.dev/golang.org/x/exp/rand has locked source, should be enough (though we can write our own wrapper too, not a rocket science).

https://pkg.go.dev/golang.org/x/exp/rand has locked source, should be enough (though we can write our own wrapper too, not a rocket science).
fyrchik commented 2024-05-08 11:53:11 +00:00
Owner
Copy link

Refs #125

Refs #125
Sign in to join this conversation.
No Branch/Tag specified
Branches Tags
master
support/v1.0.0-rc.5
support/v1.0.0-rc.4
support/v1.0.0-rc.3
No results found.
Labels
Clear labels   
P0

Highest

  
P1

High

  
P2

Medium

  
P3

Low

  
good first issue

Good for newcomers

  
pool

Tasks related to client pool

  
Infrastructure

Infrastructure, Automation, CI/CD or DevOps related stuff

  
blocked

The issue or PR is blocked by something

  
bug

Something is not working

  
config

Configuration format update or breaking change

  
discussion

Talking about something in order to reach a decision or to exchange ideas

  
documentation

Documentation related

  
duplicate

This issue or pull request already exists

  
enhancement

New feature

  
go

Language features adoption

  
help wanted

Extra attention is needed

  
internal

   
invalid

Something is wrong

  
kludge

This is a kludge and we know it

  
observability

Related to metrics, tracing and logs

  
perfomance

Perfomance related

  
question

More information is needed

  
refactoring

Refactoring

  
wontfix

This won't be fixed

No labels
P0
P1
P2
P3
good first issue
pool
Infrastructure
blocked
bug
config
discussion
documentation
duplicate
enhancement
go
help wanted
internal
invalid
kludge
observability
perfomance
question
refactoring
wontfix
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
2 participants
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: TrueCloudLab/frostfs-sdk-go#221
No description provided.
Delete branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?