preface

As early as a few years ago has written about the LRU cache: crossoverjie. Top / 2018/04/07 /…

It was implemented in Java at the time, and recently I was refining PTG and needed a least-recently used data structure to store history.

PTG: Performance Testing tool (Go), gRPC client debugging tool implemented with Go.

Go official library does not have the relevant implementation, considering the simplicity of the program is not going to rely on the third party library, write one; The complexity itself is not high, not a few lines of code.

With this data structure, I implemented the request history function in PTG:

Each request is stored in the LRU cache, and the most recently used history is placed first, which also provides related search functions. See the following figure for details.

implementation

There is nothing to say about the implementation principle, which is the same as Java:

  • A bidirectional linked list stores the order of data
  • amapStore the final data
  • Remove the end of the list when the data reaches the upper limit
  • That’s going to be usedNodeMove to the head of the list

Despite the simplicity of Go, the good news is that the basic bidirectional linked list structure is still there.

So a LruCache is defined based on this:

According to the previous analysis:

  • sizeStore cache size.
  • Linked lists store the order of data.
  • mapStore data.
  • lockUsed to control concurrency security.

The next focus is on two functions: write and query.

Determine whether the upper limit of capacity is reached and delete the tail data when the upper limit is reached. Otherwise you want to write the data to the header.

When fetching data, this moves the queried node to the header.

These node operations are encapsulated by List.

So it is more convenient to use.

Finally, it is through this LruCache to achieve the effect of the above image, for more details can refer to the source code:

Github.com/crossoverJi…