LRU和LFU两个英文串各位肯定并不陌生,那是否很深刻理解如下几个问题(也是我最近一直挂在心上的几个问题):
LRU和LFU是指什么呢?它们之间有什么区别和联系呢?它们实现原理是什么呢?分别适用的场景是什么呢?
各位也许只能答出来1、2个,本文将阅读相关文献和走读Go开源LRU、LFU代码实现带领各位揭开LRU、LFU二者的面纱!
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
底层整体使用链表、哈希表来实现,上层使用时候需要进行加锁操作;
初始化特定大小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
}
首先判断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 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
}
// 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)
}
}
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算法类似,但是需要哈希存储值访问的次数,来决定淘汰哪个页面。
底层实现与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
}
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)
}
}
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
}
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
两种结构体调用方式都能大部分满足我们的需求,为什么要有两种调用方式呢? 他们间的异同点是什么呢?
本文浅谈下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
从性能测试结果可以比较明显看出结构体值调用效率会高一些,但是并不是很明显。 所以并不是结构体指针调用效率一定比结构体值调用性能高;跟结构体中字段大小和数量有一定关系,需要实际验证!
本文记录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
安装vim-plug
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.
iwr -useb https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim |`
ni $HOME/vimfiles/autoload/plug.vim -Force
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'
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
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
hey是 Google一女工程师(现在在aws)使用 Go 语言开发的类似 apache ab 的性能测试工具。相比 ab,boom跨平台性更好,而且更容易安装。
./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个请求
开源项目Minio
学习
MinIO是一个基于Apache License v2.0开源协议的对象存储服务。它兼容aws s3云存储服务接口,非常适合于存储非结构化的数据,例如图片、视频、日志文件、备份数据和容量/虚拟机镜像等,而一个对象文件可以是任意大小的,几十kb到5TB不等。
MinIO是一个非常轻量的服务,可以很简单的和其他应用的结合,如MySQL、Redis…
refs:
https://docs.min.io/cn/minio-quickstart-guide.html
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会将对象分为N/2个数据块、N/2个奇偶校验块。尽管可以自定义conf配置Strong Slass来区分EC比,但还是推荐N/2个数据块、奇偶校验块。因为这是防止设备异常最有效的方案。
意味着丢失任意的6块盘(不管其存放的数据块还是奇偶校验块),仍可以从剩下的盘中的数据进行恢复
开源项目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虽然也很强大,但是用起来不太友好…
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