Comments (5)
siennathesane
commented on August 15, 2024
I'd be happy to take a look at any fuzzing examples you have, but currently we don't have any data races that I'm aware of. In the case of delete, reads are free, but writes are not, so we are only locking when we delete the key, not when we check for it's existence.
The way it works is every key gets a hash, and then it's sent to the shards (just optimised byte arrays). When we go to get a key, the key is rehashed and we then get the contents from the shards at the index of the shard it resides in. The last I checked the only times we need to lock are when we need to write to the shard, which means Set and Delete, because otherwise we would definitely have a race condition on data writes.
We've spent the cycles going through an optimising the locking strategy as best we could at each step. The goal is to lock as little as possible for as quickly as possible, as the goal is pure performance, and allowing reads while writing is locked whenever possible. If you think there's a more efficient locking strategy, I'd be happy to review any PRs you come up with. :)
from bigcache.
holiman
commented on August 15, 2024
I tried reproing something, the result wasn't really what I expected (crash instead of error)
The testcase is below, and aside from that I modified maxShardSize to not do the convertMBToBytes, but use the given value.
func TestCacheDelRandomly(t *testing.T) {
c := Config{
Shards: 1,
LifeWindow: time.Second,
CleanWindow: 0,
MaxEntriesInWindow: 10,
MaxEntrySize: 10,
Verbose: true,
Hasher: newDefaultHasher(),
HardMaxCacheSize: 100,
Logger: DefaultLogger(),
}
cache, _ := NewBigCache(c)
var wg sync.WaitGroup
wg.Add(3)
var ntest = 100000
go func(){
for i := 0; i < ntest; i++{
r := uint8(rand.Int())
key := fmt.Sprintf("thekey%d", r)
cache.Delete(key)
}
wg.Done()
}()
go func(){
for i := 0; i < ntest; i++{
r := uint8(rand.Int())
key := fmt.Sprintf("thekey%d", r)
val := []byte(fmt.Sprintf("%x%x%x%x%x%x%x", r,r,r,r,r,r,r))
cache.Set(key, val)
}
wg.Done()
}()
go func(){
for i := 0; i < ntest; i++{
r := uint8(rand.Int())
key := fmt.Sprintf("thekey%d", r)
val := []byte(fmt.Sprintf("%x%x%x%x%x%x%x", r,r,r,r,r,r,r))
if got, err := cache.Get(key); err == nil && !bytes.Equal(got, val){
fmt.Printf("ERR: Got %s -> %s (exp %s)\n ", key, got, val)
}
}
wg.Done()
}()
wg.Wait()
}New queue with initialCapacity 100, maxCapacity 100
2019/02/15 09:34:50 Collision detected. Both "thekey208" and "thekey145" have the same hash e39a7b36da6f8f8b
2019/02/15 09:34:50 Collision detected. Both "thekey120" and "thekey177" have the same hash ecaa2236dfae8c2c
2019/02/15 09:34:50 Collision detected. Both "thekey162" and "thekey157" have the same hash ec9cac36dfa3394e
2019/02/15 09:34:50 Collision detected. Both "thekey162" and "thekey172" have the same hash ec9cac36dfa3394e
2019/02/15 09:34:50 Collision detected. Both "thekey185" and "thekey6" have the same hash ec95a336df9d0b55
panic: runtime error: slice bounds out of range
goroutine 21 [running]:
github.com/allegro/bigcache/queue.(*BytesQueue).peek(0xc0000c2c68, 0x2e, 0x0, 0x3, 0x411d1e, 0xc00014edc0, 0xeb884e38, 0xdfb4c04c9bf101fc)
/home/user/go/src/github.com/allegro/bigcache/queue/bytes_queue.go:199 +0x229
github.com/allegro/bigcache/queue.(*BytesQueue).Get(0xc0000c2c68, 0x2e, 0xec95a336df9d0b55, 0xc0000ea12c, 0x464aea, 0x91d9a0, 0xc000124180)
/home/user/go/src/github.com/allegro/bigcache/queue/bytes_queue.go:164 +0x35
github.com/allegro/bigcache.(*cacheShard).set(0xc0000c2c60, 0xc0001a04f0, 0x9, 0xec95a336df9d0b55, 0xc00014ef08, 0xe, 0x20, 0xe, 0xc00014ef08)
/home/user/go/src/github.com/allegro/bigcache/shard.go:64 +0x34c
github.com/allegro/bigcache.(*BigCache).Set(0xc0000872b0, 0xc0001a04f0, 0x9, 0xc00014ef08, 0xe, 0x20, 0xe, 0x0)
/home/user/go/src/github.com/allegro/bigcache/bigcache.go:117 +0xab
github.com/allegro/bigcache.TestCacheDelRandomly.func2(0x186a0, 0xc0000872b0, 0xc00008c7c0)
/home/user/go/src/github.com/allegro/bigcache/bigcache_test.go:394 +0x1ff
created by github.com/allegro/bigcache.TestCacheDelRandomly
/home/user/go/src/github.com/allegro/bigcache/bigcache_test.go:389 +0x1cb
from bigcache.
holiman
commented on August 15, 2024
A printout in the bytes_queue before that happens:
Trying to access out of bounds: blocksize 0xc7000000 q.array[50 :3338666034], len 200
panic: runtime error: slice bounds out of range
and
Trying to access out of bounds: blocksize 0x18000000 q.array[50 :402653234], len 200
Looks like blocksize is sometimes corrupted. Also, I managed to get the test to execute without crashing once, and caught the thing I'd been fishing for:
=== RUN TestCacheDelRandomly
New queue with initialCapacity 100, maxCapacity 200
2019/02/15 09:49:47 Allocated new queue in 2.892µs; Capacity: 200
ERR: Got thekey103 -> fbfbfbfbfbfbfb (exp 67676767676767)
--- PASS: TestCacheDelRandomly (0.27s)
PASS
from bigcache.
holiman
commented on August 15, 2024
More context, printing out the data surrounding the blocksize read
Trying to access out of bounds: blocksize 0x38613861 q.array[132 :945895653], len 200
Contents of array in the neighbourhood of 'blocksize': [...79313638613861386138613861386138613828000000497f...]
One of the entries, namely this one (number 138 / 8A)
key thekey138 val 3861386138613861386138613861
has obviously overwritten the location where it looks for blocksize:
[...793136 3861386138613861386138613861 3828000000497f...]
from bigcache.
holiman
commented on August 15, 2024
If I make the lock around del one contiguous writelock, then all errors disappear.
from bigcache.
Related Issues (20)
- Excessive memory allocation HOT 1
- The index(int) of entries(queue.BytesQueue) overflows the hashmap's uint32 value HOT 4
- Memory so high, and when clean not reduce size HOT 5
- Benchmark is not fair, So the speed can't be trusted HOT 4
- Whether it is a bug ? HOT 1
- Why doesn't bigcache consider designing expiration time for each cache key? HOT 4
- How does bigcache handle hash collisions HOT 1
- BigCache is logging allocations it should not HOT 4
- Support for the map? HOT 1
- compile a 32-bit LSB executable on arm and Execution error-> panic: unaligned 64-bit atomic operation HOT 6
- Is there a memory leak in bigcache? HOT 4
- Add multi-level cache design HOT 2
- Why do we need to configure both lifeWindow and cleanWindow? HOT 2
- GRPC server support HOT 4
- feature: Support uint64 keys without converting to string then back again HOT 6
- Proposal to Integrate SIEVE Eviction Algorithm
- potential misuse of reflect function
- Unused parameter in shards.go [ DEL ] HOT 4
- Improve error handling in BytesQueue.Push function in queue.go HOT 2
- A panic occurred, causing the lock to remain engaged.panic: makeslice: len out of range
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from bigcache.