Questions I don't know in database kernel interview(1)

出于保密,The company name is not listed here

一面：

How vectorization optimizes branch statements？

譬如ck的JIT:利用JIT提升ClickHouseDozens of times the query performance - 腾讯云开发者社区-腾讯云

(just-in-time compilation)

可以了解一下cpubranch prediction failure mechanism.

PolarDB-X：A lot of instructions need to be explained each time？使用 PolarDB-X 向量化引擎

有哪些压缩算法？

InnoDB 中默认使用 zlib 算法进行压缩,也可以选择 snappy、quicklz 等,详细的对比可以参考这里的一篇文章,简而言之： snappy 和 quicklz在压缩比和cpu消耗上保存了较好的平衡,这两种算法在新开发的软件中使用更为广泛,包括TokuDB、MongoDB等.

clickhouse The general compression algorithm used is actually similar to other databases,比如：

• LZ4：非常高效的压缩算法,在SLS内部大量使用,压缩和解压性能都极强,尤其是解压性能可达到单核4GB/s.缺点是压缩率有点低（但是在日志场景可以达到5-15倍的压缩率,还是非常适用的）

• ZSTD：虽然压缩/解压效率不如LZ4,但是也可以达到单核400M/s的压缩和1G/s左右的解压

linuxWhy have logical addresses and physical addresses？差别？

逻辑地址：

The logical address is for the programmer to see,It is used for internal programming,Program-generated AND segment and offset address,是CS:IP的形式,比如在进行C编程时,The value of the pointer can be read（&操作）,This value is the logical address,It is equivalent to the address of the current process data segment.在intel-32,实模式下,The logical address is equal to the physical address.在保护模式下,If the paging mechanism is not turned on,逻辑地址 = 线性地址.

虚拟地址/线性地址：

虚拟地址就是线性地址.is used to describe the address space of the task.IA-32处理器上,每个任务都有4G的虚拟内存空间,That is, the linear address space.
Linear addresses have two preconditions：Protected mode and page functions are enabled,只有CPU处于保护模式,And the page function is turned on,The address generated by the segment component is the linear address.
Linear addresses are an intermediate layer between logical addresses and physical addresses,Program code generates logical addresses,逻辑地址是selector：offset（CS:IP）的组成,用CSGo as selectorGDT(全局描述符表）中查找得到段基址然后加上offset（段内偏移地址）就得到了线性地址.这个过程一般称为：段式内存管理.

物理地址：

Physical addresses are notmemory address,而是CPUThe address space allocated to the memory device,This address is converted into an address that can be recognized by the memory stick through the address allocation circuit,Implement communication with the memory stick.

页式内存管理：

Divide the linear address into four parts,The first three parts are used as indexes respectively全局页目录、Program page directory、页表里查表,You will end up with a page tablePage Table,The value there is the starting address of a page of physical memory,Plus the fourth part of the linear address（页内偏移）就得到了物理地址.

cpu的cachespeed scale？

与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell

 CPU会有三级内存（L1,L2,L3 ）.

• L1 的存取速度：4 个CPU时钟周期
• L2 的存取速度： 11 个CPU时钟周期
• L3 的存取速度：39 个CPU时钟周期
• RAM内存的存取速度：107 个CPU时钟周期

 L1的速度是RAM的27倍.但是L1/L2的大小基本上也就是KB级别的,L3会是MB级别的.

When will the memory data arrivecache的？

当有数据没有命中缓存的时候,CPU就会以最小为Cache Line的单元向内存更新数据.

“Cache Line”Load the following data piece by piece to a place close to you.

一般来说,一个主流的CPU的Cache Line 是 64 Bytes（也有的CPU用32Bytes和128Bytes）,64Bytes也就是16个32位的整型,这就是CPU从内存中捞数据上来的最小数据单位.

当拿到一个内存地址的时候,先拿出中间的 6bits 来,找到是哪组.

一个8组的cache line中,再进行O(n) n=8 的遍历,主是要匹配前24bits的tag.如果匹配中了,就算命中,如果没有匹配到,那就是cache miss,如果是读操作,就需要进向后面的缓存进行访问了.L2/L3同样是这样的算法.而淘汰算法有两种,一种是随机一种是LRU.现在一般都是以LRU的算法 .

CPU并不一定只是更新64Bytes,因为访问主存实在是太慢了.

二面：

代码如何实现有界阻塞队列？

（I don't even know what this is,go自带channel可以用,所以不太熟悉）

I should be thinking more about the blog I wrote in the first place：

其实就是一个channel的实现.

Look at the analysis from the underlying source codego语言的channel实现_Aiky哇的博客-CSDN博客

但是因为go的MutexNo wait method is provided,So I didn't write it out,,

其实goProvides tools for coordinating individual threads：sync.Cond

使用方法：

 https://www.jb51.net/article/221684.htm

package main

import (
	"fmt"
	"sync"
)

type Myque struct {
	n   int
	que []int

	pushCond sync.Cond
	popCond  sync.Cond
	mtx      sync.Mutex
}

func NewMyque(n int) *Myque {
	myq := Myque{
		n:   n,
		que: make([]int, n),
		mtx: sync.Mutex{},
	}
	myq.pushCond = *sync.NewCond(&myq.mtx)
	myq.popCond = *sync.NewCond(&myq.mtx)
	return &myq
}

func (this *Myque) Push(val int, wg *sync.WaitGroup) {
	defer wg.Done()
	// 加锁
	this.mtx.Lock()

	// 如果队列已经满了,等待
	for len(this.que) >= this.n {
		this.pushCond.Wait()
	}

	// 如果抢到了锁,添加值
	this.que = append(this.que, val)

	// 添加完毕,解锁
	this.mtx.Unlock()

	// 添加完毕,The value can be obtained
	this.popCond.Broadcast()
}

func (this *Myque) Pop(wg *sync.WaitGroup) (v int, le int) {
	defer wg.Done()
	// 加锁
	this.mtx.Lock()

	// 如果队列中没有数据,等待
	for len(this.que) == 0 {
		this.popCond.Wait()
	}

	// Take out
	v = this.que[0]
	this.que = this.que[1:]
	le = len(this.que)

	// 解锁
	this.mtx.Unlock()

	// Wake up an insert thread
	this.pushCond.Broadcast()

	// Output to see the number
	fmt.Println(le)
	return
}

func main() {
	myque := NewMyque(10)

	wg := sync.WaitGroup{}
	wg.Add(200)

	for i := 0; i < 100; i++ {
		go myque.Push(1, &wg)
	}

	for i := 0; i < 100; i++ {
		go myque.Pop(&wg)
	}
	wg.Wait()
	fmt.Println("done")
}

 

有没有看过goThe underlying source code orck源码？

（This really only depends on the accumulation,,I haven't seen it so farck的源码）

There are many more interviews after that,Write down any questions you don't have