Welcome to Rick's Blog!

这里记录着我的所学所得

揭开LRU、LFU面纱

2022-05-29

Language Algorithm

Golang Algorithm Cache

定义
- LRU
- LFU
实现原理
- LRU
  - init
  - put
  - get
  - evict
- LFU
  - init
  - put
  - get
  - evict
二者区别&适用场景
参考

LRU和LFU两个英文串各位肯定并不陌生，那是否很深刻理解如下几个问题（也是我最近一直挂在心上的几个问题）：
LRU和LFU是指什么呢？它们之间有什么区别和联系呢？它们实现原理是什么呢？分别适用的场景是什么呢？各位也许只能答出来1、2个，本文将阅读相关文献和走读Go开源LRU、LFU代码实现带领各位揭开LRU、LFU二者的面纱！

定义

LRU

from wikipeda

Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item.

LRU其实是Least Recently Used首字母开头的缩写，即淘汰最近最少使用。LRU是一种页面置换算法，选择最近最远的页面进行淘汰。

使用golang-lru进行演示

package main

import (
	"fmt"

	lru "github.com/hashicorp/golang-lru"
)

func main() {
	c, _ := lru.New(5)
	for i := 0; i < 10; i++ {
		c.Add(i, i*i)
	}
	for i := 0; i < 10; i++ {
		fmt.Println(c.Get(i))
	}
	fmt.Println(c.Len())
	fmt.Println(c.Keys()...)

}
output
```bash
<nil> false
<nil> false
<nil> false
<nil> false
<nil> false
25 true
36 true
49 true
64 true
81 true
5
5 6 7 8 9

LFU

实现原理

LRU

init

底层整体使用链表、哈希表来实现，上层使用时候需要进行加锁操作；
初始化特定大小LRU，相当于初始化list、map，并记录LRU大小；

type LRU struct {
	size      int //LRU大小
	evictList *list.List //map存放键值对，主要判断最久没更新的键值对，供后续淘汰使用
	items     map[interface{}]*list.Element //map存放键值对
	onEvict   EvictCallback //淘汰回调函数
}

func NewLRU(size int, onEvict EvictCallback) (*LRU, error) {
	if size <= 0 {
		return nil, errors.New("must provide a positive size")
	}
	c := &LRU{
		size:      size,
		evictList: list.New(),
		items:     make(map[interface{}]*list.Element),
		onEvict:   onEvict,
	}
	return c, nil
}

put

首先判断map中是否有对应的键值对，如果有将节点移动到链表头部，代表当前修改的键值对是最新更新的键值对。如果没有创建键值对节点，并移动到链表头部。
然后判断当前链表长度是否超过预设的size，如果超过，需要删除最久没更新的node。

// Add adds a value to the cache.  Returns true if an eviction occurred.
func (c *LRU) Add(key, value interface{}) (evicted bool) {
	// Check for existing item
	if ent, ok := c.items[key]; ok {
		c.evictList.MoveToFront(ent)
		ent.Value.(*entry).value = value
		return false
	}

	// Add new item
	ent := &entry{key, value}
	entry := c.evictList.PushFront(ent)
	c.items[key] = entry

	evict := c.evictList.Len() > c.size
	// Verify size not exceeded
	if evict {
		c.removeOldest()
	}
	return evict
}

get

// Get looks up a key's value from the cache.
func (c *LRU) Get(key interface{}) (value interface{}, ok bool) {
	if ent, ok := c.items[key]; ok {
		c.evictList.MoveToFront(ent)
		if ent.Value.(*entry) == nil {
			return nil, false
		}
		return ent.Value.(*entry).value, true
	}
	return
}

evict

// removeOldest removes the oldest item from the cache.
func (c *LRU) removeOldest() {
	ent := c.evictList.Back()
	if ent != nil {
		c.removeElement(ent)
	}
}

// removeElement is used to remove a given list element from the cache
func (c *LRU) removeElement(e *list.Element) {
	c.evictList.Remove(e)
	kv := e.Value.(*entry)
	delete(c.items, kv.key)
	if c.onEvict != nil {
		c.onEvict(kv.key, kv.value)
	}
}

LFU

from wikipeda

Counts how often an item is needed. Those that are used least often are discarded first. This works very similar to LRU except that instead of storing the value of how recently a block was accessed, we store the value of how many times it was accessed. So of course while running an access sequence we will replace a block which was used fewest times from our cache. E.g., if A was used (accessed) 5 times and B was used 3 times and others C and D were used 10 times each, we will replace B.

LFU是Least Frequently Used首字母开头的缩写，即淘汰最不常用。它跟LRU算法类似，但是需要哈希存储值访问的次数，来决定淘汰哪个页面。

init

底层实现与LRU实现类似，通过横向和纵向双链表实现

//开启记录淘汰cache时候使用,普通键值对
type Eviction struct {
	Key   string
	Value interface{}
}

type Cache struct {
	// If len > UpperBound, cache will automatically evict
	// down to LowerBound.  If either value is 0, this behavior
	// is disabled.
	UpperBound      int                    //如果cache大小超过UpperBound,淘汰cache
	LowerBound      int                    //淘汰cache大小至LowerBound
	values          map[string]*cacheEntry //map存放键值对
	freqs           *list.List             //记录频率list(横向list)
	len             int                    //记录cache大小
	lock            *sync.Mutex
	EvictionChannel chan<- Eviction //记录淘汰信号量
}

type cacheEntry struct {
	key      string
	value    interface{}
	freqNode *list.Element //指向记录频率list node
}

//记录频率list中的 node
type listEntry struct {
	entries map[*cacheEntry]byte //指向存放键值对ap
	freq    int                  //记录频率大小
}

func New() *Cache {
	c := new(Cache)
	c.values = make(map[string]*cacheEntry)
	c.freqs = list.New()
	c.lock = new(sync.Mutex)
	return c
}

put

func (c *Cache) Set(key string, value interface{}) {
	c.lock.Lock()
	defer c.lock.Unlock()
	if e, ok := c.values[key]; ok {
		// value already exists for key.  overwrite
		e.value = value
		c.increment(e)
	} else {
		// value doesn't exist.  insert
		e := new(cacheEntry)
		e.key = key
		e.value = value
		c.values[key] = e
		c.increment(e)
		c.len++
		// bounds mgmt
		if c.UpperBound > 0 && c.LowerBound > 0 {
			if c.len > c.UpperBound {
				c.evict(c.len - c.LowerBound)
			}
		}
	}
}

func (c *Cache) increment(e *cacheEntry) {
	currentPlace := e.freqNode
	var nextFreq int
	var nextPlace *list.Element
	if currentPlace == nil {
		// new entry
		nextFreq = 1
		nextPlace = c.freqs.Front()
	} else {
		// move up
		nextFreq = currentPlace.Value.(*listEntry).freq + 1
		nextPlace = currentPlace.Next()
	}

	if nextPlace == nil || nextPlace.Value.(*listEntry).freq != nextFreq {
		// create a new list entry
		li := new(listEntry)
		li.freq = nextFreq
		li.entries = make(map[*cacheEntry]byte)
		if currentPlace != nil {
			nextPlace = c.freqs.InsertAfter(li, currentPlace)
		} else {
			nextPlace = c.freqs.PushFront(li)
		}
	}
	e.freqNode = nextPlace
	nextPlace.Value.(*listEntry).entries[e] = 1
	if currentPlace != nil {
		// remove from current position
		c.remEntry(currentPlace, e)
	}
}

get

func (c *Cache) Get(key string) interface{} {
	c.lock.Lock()
	defer c.lock.Unlock()
	if e, ok := c.values[key]; ok {
		c.increment(e)
		return e.value
	}
	return nil
}

evict

func (c *Cache) Evict(count int) int {
	c.lock.Lock()
	defer c.lock.Unlock()
	return c.evict(count)
}

func (c *Cache) evict(count int) int {
	// No lock here so it can be called
	// from within the lock (during Set)
	var evicted int
	for i := 0; i < count; {
		if place := c.freqs.Front(); place != nil {
			for entry, _ := range place.Value.(*listEntry).entries {
				if i < count {
					if c.EvictionChannel != nil {
						c.EvictionChannel <- Eviction{
							Key:   entry.key,
							Value: entry.value,
						}
					}
					delete(c.values, entry.key)
					c.remEntry(place, entry)
					evicted++
					c.len--
					i++
				}
			}
		}
	}
	return evicted
}

二者区别&适用场景

LFU空间占用会比LRU大，LRU算法实现比较简单。
我个人理解，LFU淘汰算法会比较“客观”，不会像LRU一样一股脑把最后一个页面淘汰掉。
LFU会根据统计的结果，用数据说话。同时LRU可能会导致键值对频繁IO。

参考

LRU wiki
LFU wiki
banyu tech blog LRU
golang-lru
golang-lfu
lfu-paper

Read All

Golang结构体值调用vs指针调用

2022-05-14

Language

Golang

调用定义
区别
性能

两种结构体调用方式都能大部分满足我们的需求，为什么要有两种调用方式呢？他们间的异同点是什么呢？

本文浅谈下Golang结构体值调用和指针调用间的区别。

并引出2个问题： 1.结构体指针调用确实如网上说的那么高效么？ 2.如果高效，高效的原因是什么呢？

调用定义

func (s *MyStruct) pointerMethod() { } // method on pointer
func (s MyStruct)  valueMethod()   { } // method on value

区别

1.最重要的一点：接受者是否需要进行修改？如果需要修改，必须使用结构体指针调用。（slice/map作为引用类型，它们的行为有些微妙，但是例如要在函数里修改slice的长度，必须使用结构体指针调用）

modify field of slice

type SliceTest struct {
	s []int
}

func (s SliceTest) valueAppend(p int) {
	s.s = append(s.s, p)

}
func (s *SliceTest) pointerAppend(p int) {
	s.s = append(s.s, p)
}

func (s SliceTest) valueSet(p int) {
	if len(s.s) == 0 {
		return
	}
	s.s[0] = p
}

func (s *SliceTest) pointerSet(p int) {
	if len(s.s) == 0 {
		return
	}
	s.s[0] = p
}

func printSlice(s SliceTest) {
	fmt.Println("slice:", s.s, "len:", len(s.s), "cap:", cap(s.s))
}
unc main() {
	s := SliceTest{s: make([]int, 0)}
	s.valueAppend(10)
	printSlice(s)
	s.pointerAppend(10)
	printSlice(s)
	s.pointerSet(11)
	printSlice(s)
	s.valueSet(12)
	printSlice(s)
}

output

slice: [] len: 0 cap: 0
slice: [10] len: 1 cap: 1
slice: [11] len: 1 cap: 1
slice: [12] len: 1 cap: 1

modify field of other type

type OtherTest struct {
	num int
}

func (p OtherTest) valueMethod(num int) {
	p.num = num
}

func (p *OtherTest) pointerMethod(num int) {
	p.num = num
}
func main(){
        s := OtherTest{num: 0}
	fmt.Println(s)
	s.valueMethod(10)
	fmt.Println(s)
	s.pointerMethod(10)
	fmt.Println(s)
}

output

{0}
{0}
{10}

从这些例子看，如果使用结构体指针调用修改这些字段，修改对于调用者是可见的。但是使用结构体值调用，是通过参数拷贝实现的，修改对于调用者是不可见的。

运用场景：使用结构体值调用来替代结构体指针调用，可以遵循参数不可变行性质，更加安全。这种用法叫做“防御性拷贝”。

2.对效率的考虑，如果接受者是一个很大的结构体，使用指针调用更高效这块后面会做个简单验证

总之除了修改字段外，这两种调用方式几乎没别的区别了；可能因为结构体值调用有参数拷贝操作，他们之前性能差异比较大

性能

写了个简单代码，粗略验证下结构体指针调用是否如网上说的那么高效

benchmark demo

package main

import (
	"testing"
)

type StructTest struct {
	num  int
	num1 int
	num2 int
	num3 int
	str  string
	b    bool
}

func (p StructTest) valueMethod(num int) {
	p.num = num
	p.num1 = num
	p.num2 = num
	p.num3 = num
	p.str = "XXXX"
	p.b = true
}

func (p *StructTest) pointerMethod(num int) {
	p.num = num
	p.num1 = num
	p.num2 = num
	p.num3 = num
	p.str = "XXXX"
	p.b = true
}

func BenchmarkValStruct(b *testing.B) {
	p := StructTest{num: 10}
	for j := 0; j < b.N; j++ {
		for i := 0; i < 1e8; i++ {
			p.valueMethod(i)
		}
	}
}

func BenchmarkPointerStruct(b *testing.B) {
	p := StructTest{num: 10}
	for j := 0; j < b.N; j++ {
		for i := 0; i < 1e8; i++ {
			p.pointerMethod(i)
		}
	}
}

output of call by value

go test -benchmem -run=^$ -bench ^BenchmarkValStruct$ demo/gobench  -benchtime=
60s
goos: darwin
goarch: amd64
pkg: demo/gobench
cpu: Intel(R) Core(TM) i5-8257U CPU @ 1.40GHz
BenchmarkValStruct-8        1356          55742350 ns/op               0 B/op          0 allocs/op
PASS
ok      demo/gobench    81.456s

output of call by pointer

go test -benchmem -run=^$ -bench ^BenchmarkPointerStruct$ demo/gobench  -benchtime=60s
goos: darwin
goarch: amd64
pkg: demo/gobench
cpu: Intel(R) Core(TM) i5-8257U CPU @ 1.40GHz
BenchmarkPointerStruct-8            1260          56138387 ns/op               0 B/op          0 allocs/op
PASS

从性能测试结果可以比较明显看出结构体值调用效率会高一些，但是并不是很明显。所以并不是结构体指针调用效率一定比结构体值调用性能高；跟结构体中字段大小和数量有一定关系，需要实际验证！

Read All

My Vim Note

2022-03-19

Tool

Tool Vim

准备
配置
- 基本配置
- Golang插件配置
入门
实践
参考

本文记录Vim个人常用操作和配置，并持续更新中！

准备

vim 8.0+

git clone https://github.com/vim/vim.git
make distclean
./configure --with-features=huge --enable-python3interp --enable-pythoninterp --with-python-config-dir=/usr/lib/python2.7/config-x86_64-linux-gnu/ --enable-rubyinterp --enable-luainterp --enable-perlinterp --with-python3-config-dir=config-3.6m-x86_64-linux-gnu --enable-multibyte --enable-cscope   
make
sudo make install
sudo cp vim /usr/bin

配置

基本配置

autocmd BufWritePost $MYVIMRC source $MYVIMRC

set nocompatible " 关闭兼容模式
set nu " 设置行号
set cursorline " 突出显示当前行
" set cursorcolumn " 突出显示当前列
set showmatch " 显示括号匹配

" tab 缩进
set tabstop=4 " 设置Tab长度为4空格
set shiftwidth=4 " 设置自动缩进长度为4空格
set autoindent " 继承前一行的缩进方式，适用于多行注释

" 定义快捷键的前缀，即<Leader>
let mapleader=";" 

" ==== 系统剪切板复制粘贴 ====
" v 模式下复制内容到系统剪切板
vmap <Leader>c "+yy
" n 模式下复制一行到系统剪切板
nmap <Leader>c "+yy
" n 模式下粘贴系统剪切板的内容
nmap <Leader>v "+p

" 开启实时搜索
set incsearch
" 搜索时大小写不敏感
set ignorecase
syntax enable
syntax on                    " 开启文件类型侦测
filetype plugin indent on    " 启用自动补全

" 退出插入模式指定类型的文件自动保存
au InsertLeave *.go,*.sh,*.php write

" 解决中文乱码
set fileencodings=utf-8,ucs-bom,gb18030,gbk,gb2312,cp936
set termencoding=utf-8
set encoding=utf-8

Golang插件配置

安装vim-plug

Unix

curl -fLo ~/.vim/autoload/plug.vim --create-dirs \
    https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim

You can automate the process by putting the command in your Vim configuration file as suggested here.

Windows (PowerShell)

iwr -useb https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim |`
    ni $HOME/vimfiles/autoload/plug.vim -Force

Neovim

Unix, Linux

sh -c 'curl -fLo "${XDG_DATA_HOME:-$HOME/.local/share}"/nvim/site/autoload/plug.vim --create-dirs \
       https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim'

Linux (Flatpak)

curl -fLo ~/.var/app/io.neovim.nvim/data/nvim/site/autoload/plug.vim --create-dirs \
    https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim

Windows (PowerShell)

iwr -useb https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim |`
    ni "$(@($env:XDG_DATA_HOME, $env:LOCALAPPDATA)[$null -eq $env:XDG_DATA_HOME])/nvim-data/site/autoload/plug.vim" -Force

.vimrc配置安装插件

call plug#begin()
Plug 'fatih/vim-go'
Plug 'majutsushi/tagbar'
Plug 'scrooloose/nerdtree'
Plug 'Valloric/YouCompleteMe'
call plug#end()

命令行输入vim后输入:PlugInstall就可以开始安装了。

入门

刚开始使用vim使用可以vimtutor，按照上面的例子实践一遍

实践

根据具体的问题，查询资料进行解决

参考

https://github.com/junegunn/vim-plug
https://www.cnblogs.com/standardzero/p/10727689.html
https://www.jianshu.com/p/8426cef1f4f5
https://www.cnblogs.com/starfish29/p/11156333.html

Read All

Hey工具魔改

2022-01-20

OpenSource

Golang Tool

hey manual

hey是 Google一女工程师（现在在aws）使用 Go 语言开发的类似 apache ab 的性能测试工具。相比 ab，boom跨平台性更好，而且更容易安装。

hey manual

./bin/hey_linux_amd64 -h
flag needs an argument: -h
Usage: hey [options...] <url>

Options:
  -n  Number of requests to run. Default is 200.
  -c  Number of workers to run concurrently. Total number of requests cannot
      be smaller than the concurrency level. Default is 50.
  -q  Rate limit, in queries per second (QPS) per worker. Default is no rate limit.
  -z  Duration of application to send requests. When duration is reached,
      application stops and exits. If duration is specified, n is ignored.
      Examples: -z 10s -z 3m.
  -o  Output type. If none provided, a summary is printed.
      "csv" is the only supported alternative. Dumps the response
      metrics in comma-separated values format.

  -m  HTTP method, one of GET, POST, PUT, DELETE, HEAD, OPTIONS.
  -H  Custom HTTP header. You can specify as many as needed by repeating the flag.
      For example, -H "Accept: text/html" -H "Content-Type: application/xml" .
  -t  Timeout for each request in seconds. Default is 20, use 0 for infinite.
  -A  HTTP Accept header.
  -d  HTTP request body.
  -D  HTTP request body from file. For example, /home/user/file.txt or ./file.txt.
  -T  Content-type, defaults to "text/html".
  -U  User-Agent, defaults to version "hey/0.0.1".
  -a  Basic authentication, username:password.
  -x  HTTP Proxy address as host:port.
  -h2 Enable HTTP/2.

  -host HTTP Host header.

  -disable-compression  Disable compression.
  -disable-keepalive    Disable keep-alive, prevents re-use of TCP
                        connections between different HTTP requests.
  -disable-redirects    Disable following of HTTP redirects
  -cpus                 Number of used cpu cores.
                        (default for current machine is 8 cores)

举几个例子

` ./bin/hey_linux_amd64 -z 10m http://127.0.0.1:50000`

持续发10min无限发压

` ./bin/hey_linux_amd64 -c 10 -n 10000 http://127.0.0.1:50000`

10并发发10000个请求

Read All

Minio

2021-05-27

OpenSource

Storage Golang
开源项目Minio学习

前言

MinIO简介

MinIO是一个基于Apache License v2.0开源协议的对象存储服务。它兼容aws s3云存储服务接口，非常适合于存储非结构化的数据，例如图片、视频、日志文件、备份数据和容量/虚拟机镜像等，而一个对象文件可以是任意大小的，几十kb到5TB不等。
MinIO是一个非常轻量的服务，可以很简单的和其他应用的结合，如MySQL、Redis…

MinIO使用

refs:
https://docs.min.io/cn/minio-quickstart-guide.html

MinIO安装

MacOS
```
brew install minio/stable/minio
minio server /data
```
Linux
```
wget https://dl.min.io/server/minio/release/linux-amd64/minio
chmod +x minio
minio server /data
```
使用源码安装，或者要看开源代码；前提是安装好Golang环境

Linux安装golang环境，可以看这篇 Linux配置Golang依赖包
```
go get -u github.com/minio/minio
```
纠删码

MinIO使用纠删码ensure code和校验和checksum来保护数据免受硬件故障和无声数据损坏。即使丢失一半数量(N/2)的硬盘，仍然可以恢复数据。

纠删码ensure code是什么

纠删码是一种恢复丢失和损坏数据的数学算法，Minio采用Reed-Solomon code将对象分为N/2数据和2/N奇偶校验块。这就意味着如果12块盘，一个对象会被分为6个数据块、6个奇偶校验块至10个数据块、2个奇偶校验块。

平常工作中经常说的几-几编码就是这个意思，既能节省空间又能保证数据的安全性。

Minio EC

默认情况下Minio会将对象分为N/2个数据块、N/2个奇偶校验块。尽管可以自定义conf配置Strong Slass来区分EC比，但还是推荐N/2个数据块、奇偶校验块。因为这是防止设备异常最有效的方案。

意味着丢失任意的6块盘(不管其存放的数据块还是奇偶校验块)，仍可以从剩下的盘中的数据进行恢复
Read All
Httpie

2021-02-21

OpenSource

Linux Tool Python
- 概述
  - 主要功能
- 安装
开源项目Httpie学习

概述

HTTPie (pronounced aitch-tee-tee-pie) is a command-line HTTP client. Its goal is to make CLI interaction with web services as human-friendly as possible. HTTPie is designed for testing, debugging, and generally interacting with APIs & HTTP servers. The http & https commands allow for creating and sending arbitrary HTTP requests. They use simple and natural syntax and provide formatted and colorized output.

HTTPie 操作更加友好,好像真是这样.比如CURL虽然也很强大,但是用起来不太友好…

主要功能
- Expressive and intuitive syntax
- Formatted and colorized terminal output
- Built-in JSON support
- Forms and file uploads
- HTTPS, proxies, and authentication
- Arbitrary request data
- Custom headers
- Persistent sessions
- Wget-like downloads
- Linux, macOS and Windows support
- Plugins
- Documentation
- Test coverage
安装

centos 安装为例

yum install httpie

raise error

ImportError: cannot import name UnrewindableBodyError
```
python2 -m pip uninstall urllib3
python2 -m pip install urllib3==1.21.1
```
文档建议使用Python3安装

python3 -m pip install httpie
Read All

1/1

Welcome to Rick's Blog!

揭开LRU、LFU面纱

定义

LRU

LFU

实现原理

LRU

init

put

get

evict

LFU

init

put

get

evict

二者区别&适用场景

参考

Golang结构体值调用vs指针调用

调用定义

区别

性能

My Vim Note

准备

配置

基本配置

Golang插件配置

Unix

Windows (PowerShell)

Neovim

Unix, Linux

Linux (Flatpak)

Windows (PowerShell)

入门

实践

参考

Hey工具魔改

hey manual

Minio

前言

MinIO简介

MinIO使用

MinIO安装

纠删码

纠删码ensure code是什么

Minio EC

Httpie

概述

主要功能

安装

纠删码`ensure code`是什么