Warning: mysqli_query(): (HY000/1030): Got error 28 from storage engine in /www/wwwroot/www.sreguide.com/wp-includes/wp-db.php on line 2007

Warning: mysqli_query(): (HY000/1030): Got error 28 from storage engine in /www/wwwroot/www.sreguide.com/wp-includes/wp-db.php on line 2007
数据结构数组总结 | 专注go语言|微服务|分布式|kubernetes系统研发与源码分析
Warning: mysqli_query(): (HY000/1030): Got error 28 from storage engine in /www/wwwroot/www.sreguide.com/wp-includes/wp-db.php on line 2007

Warning: mysqli_query(): (HY000/1030): Got error 28 from storage engine in /www/wwwroot/www.sreguide.com/wp-includes/wp-db.php on line 2007

数据结构数组总结

数据结构数组

1. 基础概念 

1.1 数组的特性

image.png
数组是一种最常见的线性数据结构,通常数组保存同一类元素,并且在内存上是一段连续的内- 数据结构数组

如果数组扩容则需要重新划分内存空间,进行内存拷贝或者逐个元素的迁移

1.2 切片

image.png
切片是指对数组中的一段引用,在go语言中,我们可以通过切片实现类似动态数组的功能,当切片的空间无法进行元素的存储的时候,可以自动根据扩容策略来进行扩容,同时将旧数组中的数据拷贝到新的数组中去, 然后修改底层指向的数组

1.3 RingBuffer

image.png
Ringbuffer是在系统开发中常用的一种数据结构其核心是利用数组在空间上的连续性来进行内存空间的重复利用,通过一个write和read指针来进行数据读写位置的计算,同时还可以进行扩展,实现可扩展的循环缓冲区

2.基础实现 

2.1切片的实现

2.1.1 切片结构体的定义

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

切片的实现主要分为三部分:长度、容量和底层的数组指针,当切片的长度超过容量的时候,就创建新的数组并进行数据的迁移

2.1.2 切片容量的计算

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

go语言中切片的容量计算,其实还是蛮简单的,当小于1024的时候,直接double否则,则1/4进行递增

2.1.3 内存对齐

slice的切片主要是依赖于growSlice函数实现,当计算完成切片的大小之后,还需要根据元素来进行内存的对齐

capmem = roundupsize(uintptr(newcap) << shift)
func roundupsize(size uintptr) uintptr {
    if size < _MaxSmallSize {
        if size <= smallSizeMax-8 {
            return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
        } else {
            return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
        }
    }
    if size+_PageSize < size {
        return size
    }
    return round(size, _PageSize)
}

2.2 ringBuffer自动扩容版本实现

2.2.1 基于计数器的结构体定义

image.png
相比传统的read和write指针,这里使用一个位置指针和一个计数器来实现一个ringbuffer, 简化计算逻辑

type RingBuffer struct {
    beg      int
    size     int
    readable int
    buffer   []interface{}
}

2.2.2 读写方法


func (r *RingBuffer) WriteOne(item interface{}) {
    if r.readable == r.size {
        newSize := r.size * defaultGrowthFactor
        newBuffer := make([]interface{}, newSize)
        to := r.beg + r.readable
        if to <= r.size {
            copy(newBuffer, r.buffer[r.beg:to])
        } else {
            copied := copy(newBuffer, r.buffer[r.beg:r.size])
            copy(newBuffer[copied:], r.buffer[:to%r.size])
        }
        r.beg = 0
        r.size = newSize
        r.buffer = newBuffer
    }
    r.readable++
    r.buffer[(r.beg+r.readable)%r.size] = item
}

func (r *RingBuffer) ReadOne() (interface{}, bool) {
    if r.readable == 0 {
        return nil, false
    }
    r.readable--
    item := r.buffer[r.beg]
    r.buffer[r.beg] = nil
    if r.beg == r.size-1 {
        r.beg = 0
    } else {
        r.beg++
    }
    return item, true
}

3. 实际应用

3.1 基于ringbuffer实现双chan数据交换 

image.png
在k8s中informer的事件处理的时候,通过listwatch监听apiserver的事件,内部通过两个chan和一个ringbuffer来实现数据的交换,其核心是利用了chan为nil的时候阻塞的特性


    for {
        select {
        case nextCh <- notification:
            notification, ok = p.pendingNotifications.ReadOne()
            if !ok {
                nextCh = nil
            }
        case notificationAdd, ok := <-p.addCh:
            if !ok {
                return
            }
            if notification == nil {
                notification = notificationAdd
                nextCh = p.nextCh
            } else {
                p.pendingNotifications.WriteOne(notificationAdd)
            }
        }
    }

3.2 基于slice实现无限缓冲管道

3.2.1 结构体定义

type scStateUpdateBuffer struct {
    c       chan *scStateUpdate
    mu      sync.Mutex
    backlog []*scStateUpdate
}

3.2.2 实现数据交换


func newSCStateUpdateBuffer() *scStateUpdateBuffer {
    return &scStateUpdateBuffer{
        c: make(chan *scStateUpdate, 1),
    }
}

func (b *scStateUpdateBuffer) put(t *scStateUpdate) {
    b.mu.Lock()
    defer b.mu.Unlock()
    if len(b.backlog) == 0 {
        select {
        case b.c <- t:
            return
        default:
        }
    }
    b.backlog = append(b.backlog, t)
}

func (b *scStateUpdateBuffer) load() {
    b.mu.Lock()
    defer b.mu.Unlock()
    if len(b.backlog) > 0 {
        select {
        case b.c <- b.backlog[0]:
            b.backlog[0] = nil
            b.backlog = b.backlog[1:]
        default:
        }
    }
}

// get returns the channel that the scStateUpdate will be sent to.
//
// Upon receiving, the caller should call load to send another
// scStateChangeTuple onto the channel if there is any.
func (b *scStateUpdateBuffer) get() <-chan *scStateUpdate {
    return b.c
}

3.3 roundrobin算法

type rrPicker struct {
    // subConns is the snapshot of the roundrobin balancer when this picker was
    // created. The slice is immutable. Each Get() will do a round robin
    // selection from it and return the selected SubConn.
    subConns []balancer.SubConn

    mu   sync.Mutex
    next int
}

func (p *rrPicker) Pick(ctx context.Context, opts balancer.PickOptions) (balancer.SubConn, func(balancer.DoneInfo), error) {
    p.mu.Lock()
    sc := p.subConns[p.next]
    p.next = (p.next + 1) % len(p.subConns) //数组实现 
    p.mu.Unlock()
    return sc, nil, nil
}

原创文章,作者:baxiaoshi,如若转载,请注明出处:http://www.sreguide.com/uncategorized/array_slice.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

联系我们

QQ: 52866169