LocalCache

Caches can be stand-alone caches (EGS: LocalCache) or distributed caches (EGS: Redis). Caches exist to relieve pressure on back-end databases

For example, the following scenario:

If Redis cache avalanche happened or other abnormalities, then a flash, all requests to the Mysql database directly, it is easy to hang Mysql to play, or want to alleviate the pressure of Redis side too

A convenient solution for this scenario is to use LocalCache, that is, to add LocalCache to each Service instance. The Service can use the memory of a single machine to cache data that is not easily changed, so that the vast majority of repeated requests do not go directly to Redis, as shown in the following figure

Knowledge summary

In order to understand the FreeCache code, we need the following knowledge reserves, I listed here, if you are not clear about some of the nouns in the article, you can click on the corresponding link to learn by yourself

  1. Used on 32-bit systemsatomicAccess a 64-bit word, if the 64-bit word’s data address is not 8-byte alignedpanicAt thefreecahceIn thesegmentIt’s reflected in the structure,segmentThe underline in the structure is the guaranteesegmentUsed in structuresatomicFor details on the security of operation fields, seeissue
  2. freecacheUsing memory alignment technology to improve CPU access to data,Specific reference
  3. inGoFor arrays and slicesGCThe scan can be approximated asO(1)The time ofSpecific reference

What makes FreeCache special

  • It can store millions of pieces of data
  • It’s almost zeroGCpressure
  • Concurrent security
  • pureGoimplementation
  • The approximateLRUalgorithm
  • Strictly limit memory usage
  • Support iterative

FreeCache overall frame

Based on the data structure above, the first overviewfreecacheThe process of querying data for akey, first of all, withSum64The algorithm hashes out a numbernum1, and you get thiskeyTo depositsegment, each onesegmentThe corresponding256aslot, takenum1The low8Who getslotIdAfter, according to againnum1The low16A (hash16) get written data in theslotIdUnder theentryPtrTo find the data inringBufStorage start location inoffset, and then you can do some data operations

Source code analysis

Once you have a general familiarity with the process, you can follow the link to see each of the freecache modules

const segmentCount = 256

type Cache struct {
   locks    [segmentCount]sync.Mutex
   segments [segmentCount]segment
}
Copy the code

The above structure is the entry to the freecache component. There are 256 segments and locks attached to these 256 segments. For each segment, a []byte slice is used to store data

The source code of Freecache is more difficult to understand, one is the evacuate method, and the other is the underlying RingBuf(subscript change is more difficult to understand), which will be explained in detail below

  • Core method
func Set(key, value []byte, expireSeconds int) (err error)
func Get(key []byte) (value []byte, err error)
Copy the code

Set

The main logic of the Set method is divided into the following parts:

  1. Check whether the parameter is valid

The length of the key cannot exceed 65535, and the total length of the key and value cannot exceed 1/1024 of the preset freecache size

if len(key) > 65535 {
   return ErrLargeKey
}
maxKeyValLen := len(seg.rb.data)/4 - ENTRY_HDR_SIZE
if len(key)+len(value) > maxKeyValLen {
   // Do not accept large entry.
    return ErrLargeEntry
}
Copy the code
  1. Look for the currentkeyThe depositslotAnd in theslotThe position of

Find the slot where the key is stored using the offset method. * * * * * * * * * * * * * * *

type segment struct {
   *rb            RingBuf   // ringBuf to store byte data
    segId         int       // Id of the current segment
    _             uint32    // To protect the security of atomic accessing 64-bit words on 32-bit systems
    missCount     int64     // The number of times the key was not found in the current segment
    hitCount      int64     // The number of times the current segment found the key
    entryCount    int64     // The number of current segment pairs stored (key, value)
    totalCount    int64     // All (key, value) pairs saved in the current segment, including deleted pairs
    totalTime     int64     // Store the sum of all (key, value) pairs to approximate LRU operation
    timer         Timer     // The timing component of the current segment
    totalEvacuate int64     // The number of times the approximate LRU policy was executed
    totalExpired  int64      // The number of expired (key, value) pairs
    overwrites    int64      // Overwrite the number of writes
    touched       int64      // Update the expiration counter of the key, value pair's expiration time function (Touch)
   *vacuumLen     int64      // Remaining capacity of the current segment
   *slotLens      [256]int32 // Store the actual data length of all slots
   *slotCap       int32      // Capacity occupied by each slot
   *slotsData     []entryPtr // The underlying slice shared by 256 slots
 }
Copy the code

Each segment has 256 slots. All slots share slotData

It’s basically finding the present firstslotinslotDataOffset inoffsetAnd then cut it out[offset, offset+slotLen)The capacity ofslotCapA contiguous slice of

func (seg *segment) getSlot(slotId uint8) []entryPtr {
   slotOff := int32(slotId) * seg.slotCap
   return seg.slotsData[slotOff : slotOff+seg.slotLens[slotId] : slotOff+seg.slotCap]
}
Copy the code

The way to find the location of the key in slot is to use binary lookup, which relies on the value of hash16 mentioned above, as shown below

func (seg *segment) lookup(slot []entryPtr, hash16 uint16, key []byte) (idx int, match bool) {
   idx = entryPtrIdx(slot, hash16)
   for idx < len(slot) {
      ptr := &slot[idx]
      ifptr.hash16 ! = hash16 {break
      }
      match = int(ptr.keyLen) == len(key) && seg.rb.EqualAt(key, ptr.offset+ENTRY_HDR_SIZE)
      if match {
         return
      }
      idx++
   }
   return
}
Copy the code

The above code can be broken into two pieces:

First: find the position where the hash16 value is the starting entryPtr for the function argument

func entryPtrIdx(slot []entryPtr, hash16 uint16) (idx int) {
   high := len(slot)
   for idx < high {
      mid := (idx + high) >> 1
      oldEntry := &slot[mid]
      if oldEntry.hash16 < hash16 {
         idx = mid + 1
      } else {
         high = mid
      }
   }
   return
}
Copy the code

Find entryPtr whose key matches the function argument in the entryPtr with the same hash16 value

func (rb *RingBuf) EqualAt(p []byte, off int64) bool {
   if off+int64(len(p)) > rb.end || off < rb.begin {
      return false
   }
   readOff := rb.getDataOff(off)
   readEnd := readOff + len(p)
   if readEnd <= len(rb.data) {
      return bytes.Equal(p, rb.data[readOff:readEnd])
   } else {
      firstLen := len(rb.data) - readOff
      equal := bytes.Equal(p[:firstLen], rb.data[readOff:])
      if equal {
         secondLen := len(p) - firstLen
         equal = bytes.Equal(p[firstLen:], rb.data[:secondLen])
      }
      return equal
   }
}
Copy the code

The function in the second block of code is to judge whether the underlying ringBuf matches p from the position of off. The first is to judge the parameters. The concepts of begin and end are maintained in ringBuf, and the range of OFF must be between [begin, end]. After that, the getDataOff method is called to obtain the actual starting position of the off position (which belongs to a relatively convoluted part, and the design of ringBuf will be specially discussed below), and then the end position of the read is obtained by the length of P, and then see whether the data is divided into two sections. If not, the data is directly compared, otherwise, the comparison is performed in sections

  1. Assign header information to the data

If the current key is not found in the specified slot, a new header is required. If the current key is not found in the specified slot, a new header is required

type entryHdr struct {
   accessTime uint32  // Data access time
   expireAt   uint32  // Data expiration time
   keyLen     uint16  // The length of the data key
   hash16     uint16  // The value of data hash16
   valLen     uint32  // The length of data val
   valCap     uint32  // The capacity allocated for data val
   deleted    bool    // Whether the data is deleted
   slotId     uint8   // Data stored in slotId
   reserved   uint16  // The reserved field is also used for memory alignment
}
Copy the code

In entryPtr, we see both valLen and valCap, so what does valCap do? It’s actually a pre-allocated space for Val, as you can see in the picture below

valCapIs equal to thevalLen+Yellow area.freecacheEach stored data is organized in the form of the figure above, where the length of the header is fixedENTRY_HDR_SIZE=24For updates to header information look at the code block below

var hdrBuf [ENTRY_HDR_SIZE]byte
hdr := (*entryHdr)(unsafe.Pointer(&hdrBuf[0]))
if match {
   matchedPtr := &slot[idx]
   seg.rb.ReadAt(hdrBuf[:], matchedPtr.offset)
   hdr.slotId = slotId
   hdr.hash16 = hash16
   hdr.keyLen = uint16(len(key))
   originAccessTime := hdr.accessTime
   hdr.accessTime = now
   hdr.expireAt = expireAt
   hdr.valLen = uint32(len(value))
   if hdr.valCap >= hdr.valLen {
      //in place overwrite
atomic.AddInt64(&seg.totalTime, int64(hdr.accessTime)-int64(originAccessTime))
      seg.rb.WriteAt(hdrBuf[:], matchedPtr.offset)
      seg.rb.WriteAt(value, matchedPtr.offset+ENTRY_HDR_SIZE+int64(hdr.keyLen))
      atomic.AddInt64(&seg.overwrites, 1)
      return
   }
   // avoid unnecessary memory copy.
seg.delEntryPtr(slotId, slot, idx)
   match = false
   // increase capacity and limit entry len.
for hdr.valCap < hdr.valLen {
      hdr.valCap *= 2
   }
   if hdr.valCap > uint32(maxKeyValLen-len(key)) {
      hdr.valCap = uint32(maxKeyValLen - len(key))
   }
} else {
   hdr.slotId = slotId
   hdr.hash16 = hash16
   hdr.keyLen = uint16(len(key))
   hdr.accessTime = now
   hdr.expireAt = expireAt
   hdr.valLen = uint32(len(value))
   hdr.valCap = uint32(len(value))
   if hdr.valCap == 0 { // avoid infinite loop when increasing capacity.
hdr.valCap = 1}}Copy the code

The unsafe package first defines an array whose size is ENTRY_HDR_SIZE. After that, it uses an unbroadening package to assign Pointers to the header of an array to HDR, allowing operations on HDR to be mapped directly to arrays. Select * from slot where the slot is located and select * from slot where the slot is located. Select * from slot where the slot is located and select * from slot where the slot is located. Select * from slot where the slot is located and select * from slot where the slot is located. Seg. DelEntryPtr (slotId, slot, IDx); But the underlying ringBuf is not deleted. What does that mean? EntryPtr has been mentioned a number of times before, but let’s take a look at the details of the entryPtr structure stored in slot

type entryPtr struct {
    offset   int64  // Data offset in ringBuf
    hash16   uint16 // The value of data hash16
    keyLen   uint16 // The length of the data key
    reserved uint32 // Reserved field for memory alignment
}
Copy the code

(Note: keyLen is an optimization point that can be filtered by comparing the length of the keyLen with that of the key after lookup.)

EntryPtr stores data offset in ringBuf. If entryPtr is removed from slot, insert a new entryPtr with a different offset. However, the dirty data in the underlying ringBuf is always there. Because the following evacuate function reextracts the deleted data and overwrites the dirty data with new data, redundant data copying is not required here

  1. Data recovery

You first get the total length of the data written

entryLen := ENTRY_HDR_SIZE + int64(len(key)) + int64(hdr.valCap)
Copy the code

Len (header information) + len(key) + len(valCap), the corresponding data culling operation, of course, occurs in the case of insufficient capacity, the code is as follows, is also a more difficult point in Freecache

func (seg *segment) evacuate(entryLen int64, slotId uint8, now uint32) (slotModified bool) {
   var oldHdrBuf [ENTRY_HDR_SIZE]byte
   consecutiveEvacuate := 0
   for seg.vacuumLen < entryLen {
      oldOff := seg.rb.End() + seg.vacuumLen - seg.rb.Size()
      seg.rb.ReadAt(oldHdrBuf[:], oldOff)
      oldHdr := (*entryHdr)(unsafe.Pointer(&oldHdrBuf[0]))
      oldEntryLen := ENTRY_HDR_SIZE + int64(oldHdr.keyLen) + int64(oldHdr.valCap)
      if oldHdr.deleted {
         consecutiveEvacuate = 0
         atomic.AddInt64(&seg.totalTime, -int64(oldHdr.accessTime))
         atomic.AddInt64(&seg.totalCount, - 1)
         seg.vacuumLen += oldEntryLen
         continue} expired := oldHdr.expireAt ! =0 && oldHdr.expireAt < now
      leastRecentUsed := int64(oldHdr.accessTime)*atomic.LoadInt64(&seg.totalCount) <= atomic.LoadInt64(&seg.totalTime)
      if expired || leastRecentUsed || consecutiveEvacuate > 5 {
         seg.delEntryPtrByOffset(oldHdr.slotId, oldHdr.hash16, oldOff)
         if oldHdr.slotId == slotId {
            slotModified = true
         }
         consecutiveEvacuate = 0
         atomic.AddInt64(&seg.totalTime, -int64(oldHdr.accessTime))
         atomic.AddInt64(&seg.totalCount, - 1)
         seg.vacuumLen += oldEntryLen
         if expired {
            atomic.AddInt64(&seg.totalExpired, 1)}else {
            atomic.AddInt64(&seg.totalEvacuate, 1)}}else {
         // evacuate an old entry that has been accessed recently for better cache hit rate.
newOff := seg.rb.Evacuate(oldOff, int(oldEntryLen))
         seg.updateEntryPtr(oldHdr.slotId, oldHdr.hash16, oldOff, newOff)
         consecutiveEvacuate++
         atomic.AddInt64(&seg.totalEvacuate, 1)}}return
}
Copy the code

This part of the logic is heavier, with a flow chart will be more clear

The Evacuate method in ringBuf is discussed in more detail below

  1. willkey.valueiw

After the evacuate is performed, we need to check the location of the current key to be inserted into the slot, because the IDX calculated before will change if the information in the current slot is deleted. Finally, we write the required information into slot and ringBuf to complete a data insertion

Ok, so much has been introduced above, mainly from a macro point of view of the top-down analysis, but for ringBuf this data structure we are still more confused, here specifically to talk about this data structure, old rules, first look at its structure definition

type RingBuf struct {
   begin int64 Len (data) is the real location of the data
   end   int64 Len (data) is the real location of the data
   data  []byte // The underlying byte array where the data is stored
   index int // Maintain the real location where data will be written next & the starting location of all data
}
Copy the code

Let’s focus on a few core functions in ringBuf

  1. getDataOff
func (rb *RingBuf) getDataOff(off int64) int {
   var dataOff int
   if rb.end-rb.begin < int64(len(rb.data)) {
      dataOff = int(off - rb.begin)
   } else {
      dataOff = rb.index + int(off-rb.begin)
   }
   if dataOff >= len(rb.data) {
      dataOff -= len(rb.data)
   }
   return dataOff
}
Copy the code

DataOff = off-rb. begin; dataOff = off-rb. begin; dataOff = off-rb. begin; dataOff = off-rb. begin

DataOff = rb.index + int(off-rb.begin); dataOff = rb.index + int(off-rb.begin); dataOff = rb.index + int(off-rb.begin); This corresponds to the following situation

The real length of data is 5, and the dotted line is imaginary. In fact, end should be at 1. The elements at positions 5 and 6 correspond to positions 0 and 1 in data, which is a ring

  1. ReadAt
func (rb *RingBuf) ReadAt(p []byte, off int64) (n int, err error) {
   if off > rb.end || off < rb.begin {
      err = ErrOutOfRange
      return
   }
   readOff := rb.getDataOff(off)
   readEnd := readOff + int(rb.end-off)
   if readEnd <= len(rb.data) {
      n = copy(p, rb.data[readOff:readEnd])
   } else {
      n = copy(p, rb.data[readOff:])
      if n < len(p) {
         n += copy(p[n:], rb.data[:readEnd-len(rb.data)])
      }
   }
   if n < len(p) {
      err = io.EOF
   }
   return
}
Copy the code

ReadOff = readOff; readEnd = readOff; if readEnd does not exceed the length of data, read directly; otherwise, The contents of the [readBegin, len(data)) part are read first, and then the contents of the [0, readend-len (data)) part are read

  1. Write
func (rb *RingBuf) Write(p []byte) (n int, err error) {
   if len(p) > len(rb.data) {
      err = ErrOutOfRange
      return
   }
   for n < len(p) {
      written := copy(rb.data[rb.index:], p[n:])
      rb.end += int64(written)
      n += written
      rb.index += written
      if rb.index >= len(rb.data) {
         rb.index -= len(rb.data)
      }
   }
   if int(rb.end-rb.begin) > len(rb.data) {
      rb.begin = rb.end - int64(len(rb.data))
   }
   return
}
Copy the code

Write is an appending Write. Note that in Freecache, the more recent the data is, so index moves len(p) times to put the data to the end

  1. Evacuate
func (rb *RingBuf) Evacuate(off int64, length int) (newOff int64) {
   if off+int64(length) > rb.end || off < rb.begin {
      return - 1
   }
   readOff := rb.getDataOff(off)
   if readOff == rb.index {
      // no copy evacuate
rb.index += length
      if rb.index >= len(rb.data) {
         rb.index -= len(rb.data)
      }
   } else if readOff < rb.index {
      var n = copy(rb.data[rb.index:], rb.data[readOff:readOff+length])
      rb.index += n
      if rb.index == len(rb.data) {
         rb.index = copy(rb.data, rb.data[readOff+n:readOff+length])
      }
   } else {
      var readEnd = readOff + length
      var n int
      if readEnd <= len(rb.data) {
         n = copy(rb.data[rb.index:], rb.data[readOff:readEnd])
         rb.index += n
      } else {
         n = copy(rb.data[rb.index:], rb.data[readOff:])
         rb.index += n
         var tail = length - n
         n = copy(rb.data[rb.index:], rb.data[:tail])
         rb.index += n
         if rb.index == len(rb.data) {
            rb.index = copy(rb.data, rb.data[n:tail])
         }
      }
   }
   newOff = rb.end
   rb.end += int64(length)
   if rb.begin < rb.end-int64(len(rb.data)) {
      rb.begin = rb.end - int64(len(rb.data))
   }
   return
}
Copy the code

The Evacuate method is the most logically complex method in the whole ringBuf. Its function is to move the data starting from the off position with length of length to the tail of all data. Like other methods, the real read position readOff is obtained first, and then there are three cases. If the position of readOff and index are the same, then the length of the index loop can be moved. If readOff is less than index, the getDataOff function will tell you, DataOff = rb.index + int(off-rb.begin); dataOff = rb.index + int(off-rb.begin); If readOff is greater than index, check the relationship between readEnd and Len (data). If it is <=, copy the data directly from index. Otherwise, overwrite the data in two sections. Finally, get the new offset newOff of [off, off+length] data, and update the values of end and BEGIN

(note: The evacuate method in the Set method makes a judgment that if the evacuate method is performed for more than five times in a row, the current first entryPtr is deleted. There may be some doubt as to whether the data is overwritten and written to cause dirty data if the evacuate method is performed for five times in a row. The answer is no. After a Evacuate is performed, the new oldOff is the next element moved previously, so there is no override written.)

  1. Skip
func (rb *RingBuf) Skip(length int64) {
   rb.end += length
   rb.index += int(length)
   for rb.index >= len(rb.data) {
      rb.index -= len(rb.data)
   }
   if int(rb.end-rb.begin) > len(rb.data) {
      rb.begin = rb.end - int64(len(rb.data))
   }
}
Copy the code

Skip function is mainly used in the case that the allocated valCap is larger than the real valLen. After writing the header information, key and Val, Skip valcap-vallen backwards

Get

After sorting out the context of Set method and ringBuf above, the understanding of Get method is a blow to dimension reduction. The process of Get method is generally divided into two parts (there is a PEEK field in the function to indicate whether information needs to be punched, which is not very critical, so you can understand by yourself).

  1. Locate the data and obtain the correspondingHeader information, the code is as follows
hdr, ptr, err := seg.locate(key, hashVal, peek)
iferr ! =nil {
   return
}
Copy the code
func (seg *segment) locate(key []byte, hashVal uint64, peek bool) (hdr *entryHdr, ptr *entryPtr, err error) {
   slotId := uint8(hashVal >> 8)
   hash16 := uint16(hashVal >> 16)
   slot := seg.getSlot(slotId)
   idx, match := seg.lookup(slot, hash16, key)
   if! match { err = ErrNotFoundif! peek { atomic.AddInt64(&seg.missCount,1)}return
   }
   ptr = &slot[idx]

   var hdrBuf [ENTRY_HDR_SIZE]byte
   seg.rb.ReadAt(hdrBuf[:], ptr.offset)
   hdr = (*entryHdr)(unsafe.Pointer(&hdrBuf[0]))
   if! peek { now := seg.timer.Now()ifhdr.expireAt ! =0 && hdr.expireAt <= now {
         seg.delEntryPtr(slotId, slot, idx)
         atomic.AddInt64(&seg.totalExpired, 1)
         err = ErrNotFound
         atomic.AddInt64(&seg.missCount, 1)
         return
      }
      atomic.AddInt64(&seg.totalTime, int64(now-hdr.accessTime))
      hdr.accessTime = now
      seg.rb.WriteAt(hdrBuf[:], ptr.offset)
   }
   return hdr, ptr, err
}
Copy the code

If the slot in which the key is stored and its location in the slot are not found, an error message is displayed. Otherwise, after the data header is obtained, an error message is displayed to determine whether the current data has expired. The data header and entryPtr are returned

  1. fromringBufRead data from
seg.rb.ReadAt(value, ptr.offset+ENTRY_HDR_SIZE+int64(hdr.keyLen))
Copy the code

You can see that the Get method does not move the accessed data directly to the end of all the data, as a real LRU would, which explains why Freecache’s LRU algorithm is called an approximate LRU

  • Non-core method
func Touch(key []byte, expireSeconds int) (err error)
func GetFn(key []byte, fn func([]byte) error) (err error).Copy the code

Non-core methods mainly include some aggregate functions, such as GetOrSet or SetAndGet, and some functions with a bottom pocket, such as GetFn. In addition, most of them are dotted functions, such as ExpiredCount, etc. Because the underlying calls are basically similar to the core methods, there is no more elaboration here

conclusion

Freecache freecache freecache freecache freecache freecache freecache freecache Freecache