Repository: NethermindEth/juno
Pull request #278 (2022-07-09 02:10:37)

Add cache
## Changes:
- Add the `internal/cache` package with the `Cache` interface and the `LRUCache` implementation

## Types of changes

What types of changes does your code introduce?

- New feature (non-breaking change which adds functionality)

## Testing
**Requires testing**

- Yes

**In case you checked yes, did you write tests??**

- Yes


codecov[bot]: # [Codecov](https://codecov.io/gh/NethermindEth/juno/pull/278?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) Report
> Merging [#278](https://codecov.io/gh/NethermindEth/juno/pull/278?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) (c417b7f) into [main](https://codecov.io/gh/NethermindEth/juno/commit/8e4cfd276d0aa5780383ceff927d8d05fe2a0a5a?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) (8e4cfd2) will **not change** coverage.
> The diff coverage is `100.00%`.

```diff
@@            Coverage Diff            @@
##              main      #278   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files           65        67    +2     
  Lines         5916      5966   +50     
=========================================
+ Hits          5916      5966   +50     
```

| Flag | Coverage Δ | |
|---|---|---|
| unittests | `100.00% <100.00%> (ø)` | |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/NethermindEth/juno/pull/278?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) | Coverage Δ | |
|---|---|---|
| [internal/cache/key.go](https://codecov.io/gh/NethermindEth/juno/pull/278/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#diff-aW50ZXJuYWwvY2FjaGUva2V5Lmdv) | `100.00% <100.00%> (ø)` | |
| [internal/cache/lru.go](https://codecov.io/gh/NethermindEth/juno/pull/278/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#diff-aW50ZXJuYWwvY2FjaGUvbHJ1Lmdv) | `100.00% <100.00%> (ø)` | |
| [pkg/crypto/weierstrass/weierstrass.go](https://codecov.io/gh/NethermindEth/juno/pull/278/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#diff-cGtnL2NyeXB0by93ZWllcnN0cmFzcy93ZWllcnN0cmFzcy5nbw==) | `100.00% <0.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/NethermindEth/juno/pull/278?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/NethermindEth/juno/pull/278?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth). Last update [8e4cfd2...c417b7f](https://codecov.io/gh/NethermindEth/juno/pull/278?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth).

IronGauntlets: Since this is a new package can we please move away from the convention of using internal packages? I would suggest adding this package under `juno/cache`.
adriantpaez: > Since this is a new package can we please move away from the convention of using internal packages? I would suggest adding this package under `juno/cache`. Where the cache interface is stored under file `cache.go` and the lru implementation is stored under `juno/cache/lru` directory.

@IronGauntlets Sounds good to me, but because now the project structure is under the `internal` and `pkg` directories, we need to agree first if we will continue with that structure or move to the project root because I can't break the current structure

Patch:
diff --git a/internal/cache/cache.go b/internal/cache/cache.go
new file mode 100644
index 00000000..449a96ba
--- /dev/null
+++ b/internal/cache/cache.go
@@ -0,0 +1,10 @@
+package cache
+
+// Cache represents an in-memory cache, regardless of cache policy.
+type Cache interface {
+	Put(key []byte, value []byte)
+	Get(key []byte) []byte
+	Len() int
+	Cap() int
+	Clear()
+}
diff --git a/internal/cache/lru.go b/internal/cache/lru.go
new file mode 100644
index 00000000..58135947
--- /dev/null
+++ b/internal/cache/lru.go
@@ -0,0 +1,135 @@
+package cache
+
+import (
+	"hash/maphash"
+	"sync"
+)
+
+type cacheNode struct {
+	key   uint64
+	value []byte
+	next  *cacheNode
+	prev  *cacheNode
+}
+
+// LRUCache is a cache with the least-recently-used policy.
+type LRUCache struct {
+	// hashMap contaiins the current cache contents that can be accessed by the key
+	hashMap map[uint64]*cacheNode
+	// start is a reference to the first node in the cache queue
+	start *cacheNode
+	// end is a reference to the last node in the cache queue
+	end *cacheNode
+	// count is the current ammount of items in the cache
+	count int
+	// capacity is the max ammount of items that can be stored in the cache
+	capacity int
+	// hash is used to hash the key
+	hash maphash.Hash
+	// lock is used to protect the cache from concurrent access
+	lock sync.RWMutex
+}
+
+// NewLRUCache creates a new LRUCache instance with the given capacity.
+func NewLRUCache(capacity int) *LRUCache {
+	return &LRUCache{
+		hashMap:  make(map[uint64]*cacheNode, capacity),
+		capacity: capacity,
+		hash:     maphash.Hash{},
+	}
+}
+
+// Put adds a new key-value pair to the cache. If the cache is full then
+// the least-recently-used key-value pair is removed.
+func (c *LRUCache) Put(k []byte, v []byte) {
+	c.lock.Lock()
+	defer c.lock.Unlock()
+
+	// Build the cache key and node
+	key := c.key(k)
+	node := &cacheNode{key: key, value: v}
+
+	// Cache is empty
+	if c.count == 0 {
+		c.hashMap[key] = node
+		c.start = node
+		c.end = node
+		c.count = 1
+		return
+	}
+
+	// Put the new node at the start of the queue
+	c.hashMap[key] = node
+	c.start.prev = node
+	node.next = c.start
+	c.start = node
+	c.count++
+
+	// Remove the last node if the cache is full
+	if c.count > c.capacity {
+		delete(c.hashMap, c.end.key)
+		c.end = c.end.prev
+		c.end.next.prev = nil
+		c.end.next = nil
+		c.count--
+	}
+}
+
+// Get returns the value for the given key. If the key is not found then
+// returns nil.
+func (c *LRUCache) Get(k []byte) []byte {
+	c.lock.Lock()
+	defer c.lock.Unlock()
+
+	key := c.key(k)
+	if node, ok := c.hashMap[key]; ok {
+		if node != c.start {
+			// Move the node to the start of the queue
+			node.prev.next = node.next
+			if node == c.end {
+				c.end = node.prev
+			} else {
+				node.next.prev = node.prev
+			}
+			c.start.prev = node
+			node.next = c.start
+			node.prev = nil
+			c.start = node
+		}
+		return node.value
+	}
+	return nil
+}
+
+// Len returns the current ammount of items in the cache.
+func (c *LRUCache) Len() int {
+	c.lock.RLock()
+	defer c.lock.RUnlock()
+
+	return c.count
+}
+
+// Cap returns the max ammount of items that can be stored in the cache.
+func (c *LRUCache) Cap() int {
+	c.lock.RLock()
+	defer c.lock.RUnlock()
+
+	return c.capacity
+}
+
+// Clear removes all items from the cache.
+func (c *LRUCache) Clear() {
+	c.lock.Lock()
+	defer c.lock.Unlock()
+
+	c.hashMap = make(map[uint64]*cacheNode, c.capacity)
+	c.start = nil
+	c.end = nil
+	c.count = 0
+}
+
+func (c *LRUCache) key(v []byte) uint64 {
+	c.hash.Reset()
+	c.hash.Write(v)
+	return c.hash.Sum64()
+}


Test patch:
diff --git a/internal/cache/lru_test.go b/internal/cache/lru_test.go
new file mode 100644
index 00000000..0dc2487f
--- /dev/null
+++ b/internal/cache/lru_test.go
@@ -0,0 +1,100 @@
+package cache
+
+import (
+	"bytes"
+	"fmt"
+	"testing"
+)
+
+func TestNewLRUCache(t *testing.T) {
+	c := NewLRUCache(10)
+	if c.Cap() != 10 {
+		t.Errorf("Expected capacity to be 10, got %d", c.Cap())
+	}
+	if c.Len() != 0 {
+		t.Errorf("Expected count to be 0, got %d", c.Len())
+	}
+}
+
+func TestLRUCache_Put(t *testing.T) {
+	c := NewLRUCache(10)
+	// Fill the cache
+	for i := 0; i < 10; i++ {
+		key := []byte(fmt.Sprintf("key%d", i))
+		value := []byte(fmt.Sprintf("value%d", i))
+		c.Put(key, value)
+		if c.Len() != i+1 {
+			t.Errorf("Expected count to be %d, got %d", i+1, c.Len())
+		}
+	}
+	for i := 0; i < 10; i++ {
+		key := []byte(fmt.Sprintf("key%d", 10+i))
+		value := []byte(fmt.Sprintf("value%d", 10+i))
+		c.Put(key, value)
+		if c.Len() != 10 {
+			t.Errorf("Expected count to be 10, got %d", c.Len())
+		}
+		deletedKey := []byte(fmt.Sprintf("key%d", i))
+		if v := c.Get(deletedKey); v != nil {
+			t.Errorf("Expected value to be nil, got %s", v)
+		}
+	}
+}
+
+func TestLRUCache_Get(t *testing.T) {
+	c := NewLRUCache(10)
+	for i := 0; i < 3; i++ {
+		key := []byte(fmt.Sprintf("key%d", i))
+		value := []byte(fmt.Sprintf("value%d", i))
+		c.Put(key, value)
+	}
+	for _, i := range []int{2, 1, 0} {
+		key := []byte(fmt.Sprintf("key%d", i))
+		want := []byte(fmt.Sprintf("value%d", i))
+		value := c.Get(key)
+		if !bytes.Equal(value, want) {
+			t.Errorf("Expected value to be %s, got %s", want, value)
+		}
+	}
+	if value := c.Get([]byte("key4")); value != nil {
+		t.Errorf("Expected value to be nil, got %s", value)
+	}
+}
+
+func TestLRUCache_Count(t *testing.T) {
+	c := NewLRUCache(10)
+	if c.Len() != 0 {
+		t.Errorf("Expected count to be 0, got %d", c.Len())
+	}
+	for i := 0; i < 10; i++ {
+		key := []byte(fmt.Sprintf("key%d", i))
+		value := []byte(fmt.Sprintf("value%d", i))
+		c.Put(key, value)
+		if c.Len() != i+1 {
+			t.Errorf("Expected count to be %d, got %d", i+1, c.Len())
+		}
+	}
+}
+
+func TestLRUCache_Capacity(t *testing.T) {
+	c := NewLRUCache(100)
+	if c.Cap() != 100 {
+		t.Errorf("Expected capacity to be 100, got %d", c.Cap())
+	}
+}
+
+func TestLRUCache_Clear(t *testing.T) {
+	c := NewLRUCache(10)
+	for i := 0; i < 10; i++ {
+		key := []byte(fmt.Sprintf("key%d", i))
+		value := []byte(fmt.Sprintf("value%d", i))
+		c.Put(key, value)
+	}
+	if c.Len() != 10 {
+		t.Errorf("Expected count to be 10, got %d", c.Len())
+	}
+	c.Clear()
+	if c.Len() != 0 {
+		t.Errorf("Expected count to be 0, got %d", c.Len())
+	}
+}