【笔记】语言底层场景

目录

C++

Golang

数据结构与算法

场景设计

C++

1.C++的多态

• 多态就是一个接口，多种实现方法，即动态绑定
• 通过虚函数实现

2.什么是虚函数，原理是什么，怎么样使用虚函数

• 类中存有一个虚函数表，实例化的对象拥有一个虚函数指针用来指向虚函数表中的某个位置
• 虚函数在运行时通过虚函数表确定，是动态的；内联函数在编译时候进行代码嵌入，是静态的，所以如果把虚函数声明为内联，编译器仍然会当做普通虚函数处理
• 虚函数的缺点是：一是虚函数表和虚函数指针会增大开销，二是在一个CPUcache里面，有了虚函数以后，编译器不会做一些很强大的优化
• 对于继承自父类的子类，应该将父类析构函数设为虚函数

3.const关键字的作用和一般使用情景

• 定义不会改变的常量，使编译器保护这些常量，防止代码无意的修改

4.static关键字的作用和一般使用情景

• 类里的static函数，里面就只能调用static成员
• static成员在类未进行第一次实例化时就已经占据了空间
• 存在堆上

5.了解构造函数和析构函数吗？它们俩可以是虚函数吗（还有静态函数、内联函数、友元函数、非成员函数也不能是虚函数）

• 构造函数不能是虚函数，析构函数可以是虚函数
• 一般析构函数设为虚函数是便于子类重载，避免使用父类指针指向子类对象时，去调用了父类的析构函数导致部分子类成员没能释放，造成内存泄漏

6.incline函数和宏的区别是什么

• incline在编译时展开，宏在预编译时展开；
• incline内联函数有类型检测、语法判断等功能，而宏没有，因为宏只是做简单的文本替换，这也导致要注意括号问题

7.说一下你了解的vector和map实现方式和功能

• vector，动态数组，有扩容机制
  • .clear()是把size置为0，而capacity不变
  • 真正清空vector要去与空vector做swap
• unordered_map的底层是用vector+链表实现的

8.字节对齐

• 原理：
  • 因为尽管内存是以字节为单位，但是大部分处理器并不是按字节块来存取内存的。它一般会以2字节,4字节,8字节,16字节甚至32字节为单位来存取内存，我们将上述这些存取单位称为内存存取粒度
  • 假如没有内存对齐机制，数据可以任意存放，现在一个int变量存放在从地址1开始的联系四个字节地址中，该处理器去取数据时，要先从0地址开始读取第一个4字节块,剔除不想要的字节（0地址）,然后从地址4开始读取下一个4字节块,同样剔除不要的数据（5，6，7地址）,最后留下的两块数据合并放入寄存器.这需要做很多工作
  • 有了内存对齐的，int类型数据只能存放在按照对齐规则的内存中，比如说0地址开始的内存。那么现在该处理器在取数据时一次性就能将数据读出来了，而且不需要做额外的操作，提高了效率。
• 对齐的准则：
  • 结构体变量的首地址能够被其对齐字节数大小所整除
  • 结构体每个成员相对结构体首地址的偏移都是成员大小的整数倍，如不满足，对前一个成员填充字节以满足
  • 结构体的总大小为结构体对齐字节数大小的整数倍，如不满足，最后填充字节以满足

9.单例模式

• 饿汉单例模式：系统启动的时候就利用static机制实例化了类，后面每次要用就返回这个指针
• 懒汉单例模式：第一次用到这个类的时候才去实例化，后面每次要用就返回这个指针

10.i++其实分3步执行

• 读取i的值，增加i的值，回写i的新值
• 这3步每一步都是原子操作，但是组合在一起就不一定是原子操作了，所以i++线程不安全，++i线程安全
• ++i比i++效率高得原因是，前者只用返回i+1的结果，而后者既要先保存i的结果还要保存i+1的结果

11.static关键字的作用

• 静态函数(在函数返回类型前加static)：作用域为声明语句所在的整个文件
• 全局静态变量(在全局变量前加static)：作用域为声明语句所在的整个文件
• 局部静态变量(在局部变量前加static)：作用域仍为局部
• 总结：
  • 类的静态成员和静态函数：这个类的所有对象都共用一个，注意静态函数只能引用类中的静态成员
  • static与extern相反，static意味着该变量、函数在被声明的文件之外是不可见的，除非引入声明的文件作为头文件，但是这样的话会每一个引入该头文件的文件都会定义一个自己的变量造成内存浪费，所以一般用extern在头文件中声明才是正确的方式
  • 静态变量都放在内存的静态存储区内，在程序运行期间一直存在不会释放，所有在函数内定义的局部静态变量，会在第一次运行到该语句时就创建，第二次运行到该定义语句会自动跳过，直到程序终止才释放

12.堆和栈的区别

• 堆会产生内存碎片，栈不会
• 堆只能动态分配需要程序员手动分配和释放；栈由系统管理静态分配，也可以用alloca()动态分配，但都是由系统释放
• 堆内存地址由低到高；栈内存地址相反
• 堆为虚拟内存大小；栈默认为1M（linux下为10M）
• 堆的速度慢，因为是不连续的空间；栈的速度，因为是连续的空间可以直接通过栈顶指针+偏移量来操作目标数据，并且会有操作系统硬件层面的支持

13.new与malloc区别

• new是C++用于内存分配的运算符，malloc是C用于内存分配的库函数
• new会自动计算要多少字节的内存，malloc需要用户指定字节数
• new会返回指定类型的指针，malloc返回的统一是void *，需要用户自己再转一次
• new用delete释放，malloc用free释放
• new用的是静态存储区的空间(一般是堆)，malloc用的是堆的空间

14.#define和typedefine

• define在预编译做字符串替换，typedefine在编译的时候才处理，相当于起别名

15.shared_ptr

• shared_ptr和局部变量一样，离开作用域时会自己销毁
• 每当一个shared_ptr被拷贝或当成值赋给其他变量时，内置计数器都会自动+1，当指向该对象的一个shared_ptr被销毁时，shared_ptr类的析构函数会对计数器-1，为0时就去销毁这个对象(调用这个对象的析构函数)来释放动态内存
• weak_ptr指针不能直接访问对象的方法，要先将其转化成shared_ptr指针再访问
  • weak_ptr:用于解决shared_ptr互相指向形成循环，内存一直无法释放导致泄漏，它不会增加对象的引用计数
  • weak_ptr判断指针是否释放也是通过shareed_ptr里的计数引用来判断的

16.指针和引用的区别

• 指针占4字节空间，引用只是一个别名不占空间
• 指针可初始化为nullptr，引用必须初始化为一个已存在对象
• 引用易引起内存泄漏，因为指向的对象可能在栈里被回收了

17.C++的编译过程分几个阶段

• 预编译.i->编译.o->汇编.s->链接.exe
• Linux下用C++编程的步骤
  • 用vim编写.cpp文件
  • 用g++编译得到.out文件
  • 用./xx.out执行

18.C++在linux下怎么断点调试

• 使用gdb，对某行打上断点
• 然后在生成二进制程序的时候, 加上 -g 选项

19.protected类权限修饰符

• 成员只能被该类或子类的成员函数访问
• 注意不允许子类对象用.直接访问，只能在子类的成员函数里访问

20.多线程怎么保证引用计数的安全的

• 用std::atomic，操作时自带锁

21.valotile关键字的用处

• 提醒编译器它后面所定义的变量随时都有可能改变，因此编译后的程序每次需要存储或读取这个变量的时候，都会直接从变量地址中读取数据
• 避免编译器额外优化
  • 因为编译器可能优化读取和存储，可能暂时使用寄存器中的值，如果这个变量由别的程序更新了的话，将出现不一致的现象

22.自旋锁用于占用锁时间特别短的场景，如果每次用锁要用很长时间就不能使用自旋锁了

• 通过while()里写sleep(0)来实现一直持续唤醒，并去问锁能不能拿到

23.读写锁的实现

• 两个互斥量+一个记录读者数量的整型
  • 一个表示读锁，一个表示写锁
• 两个信号量+一个记录读者数量的整型
  • 信号量初始化为1当作互斥量用

24.fanal关键字的用处

• 表示最终的
• 用于修饰的类不可继承，用于修饰的方法不可重载

25.浅拷贝和深拷贝的区别

• 有一个对象A，它里面有对象b和c
• 浅拷贝A得到的C，它里面的对象b、c指向的还是原来的对象
• 深拷贝A得到的C，它里面的对象b、c是完全新的对象

26.内联函数为什么可以提高效率

• 普通函数需要传递参数、创建并最后销毁栈帧

27.将析构函数声明为私有，可以保证这个类的对象只会被放在堆上

• 因为栈里面的变量需要自动调用析构函数

28.不能重载的符号

• .成员访问操作符和.*成员指针访问操作符
• ::域解析操作符
• sizeof()

29.编译器实现lamda表达式的原理

• 创建lamda匿名类，使用这个匿名类重载operator()
• 实例化lamda对象
• 通过对象调用operator()

30.new申请的内存可以free吗

• 不可以，因为new必须搭配delete使用

31.C和C++的栈帧过程

• 把返回地址推到栈上，CPU指针指向新调用函数的入口
• 函数开始创建新栈帧
• 函数的参数通过寄存器或直接推送到栈，来传递
• 执行完函数体后，通过移动栈指针来销毁栈帧

Golang

1.GMP模型

• G是协程，M是线程，P是调度器
  • P是程序启动的时候就创建，数量是固定的。M是P里有任务待执行但是没有空闲的M时才会去创建，数量是动态变化的，最大限制是1000但很少能用到
• M想运行G，那么必须去获取P，而这个P里面还有一个存放很多G的本地队列
  • 优先将新创建的G放在P的本地队列里面
• 全局P里有存放G的全局队列
• 如果本地队列已经没有g会去隔壁的本地队列里面拿
• 实例：1w个协程，会如何调度
  • 先将1w个G按平均分配到各个P的本地队列里，本地队列满了就放全局队列里
  • 本地队列执行g，若执行时间太长就保存上下文把该g放队列后面
  • 当某个P在执行g的时候如果发生系统调用导致M阻塞，就会有一个空闲的M1来执行这个P剩下的其他g
  • 某个本地队列执行完了后，后先去隔壁偷一半，没了再去全局拿

2.channel的底层，如何用它来实现并发，如果channel满了会怎么办

• 底层用hchan结构体实现，一个ring buffer，一个发送队列，一个接受队列
  • ring buffer设计成环状是用来降低开销的，类似循环队列
• 一个无缓冲的管道，如果他没有接受者在等待接受，那么向其塞数据的这个操作也会阻塞
• mutex成员，任何对该channel的修改都要去获取mutex
  • 常说的“channel无锁”，指的是ring buffer里有位置，数据只有放进去的一瞬间要加锁，很短暂，所以说无锁

3.Go语言的特点

• 直接编译成二进制，没有虚拟化损失(python运行时需要解释器把代码解释成机器码)
• 代码跨平台，但是编译出来的产物是不跨平台的
• runtime直接编译进可执行文件里

4.Go中的扇入、扇出

• 扇入：多个通道合并到一个通道，例如：select关键字聚合多条通道分别服务
• 扇出：一个通道分散到多个通道，例如：用go关键字起多个协程

5.线程和协程的区别

• 线程由操作系统调度，协程由用户控制
• 线程的cpu切换、线程栈等开销较大，而协程是在用户空间里运行的开销小
• 可以把协程理解为用户级别的线程

6.协程之间的通信方式

• 共享内存
• 消息队列
• 信号量

7.比较

• 同类型并且里面成员都是可比较类型的struct才能比较
• 接口interface比较时，只有类型相等、值也相等才会相等
• slice和map不能比较

8.gin框架的关键组成

• 路由、请求处理组件:gin.Engine结构体
• 中间件组件:gin的Use函数将中间件函数进行注册
• 异常处理组件:gin.Recovery()
• 日志记录组件:gin.Logger()

9.Go的map的实现(线程不安全的，读写均匀、读少写多用map+锁)

• go的map是由链表法实现的，hmap底层是一个存放指针的数组，每个指针指向一个由bmap，每一个bmap放8个哈希值相同的数据
  • bmap
    • 有一个overflow指针指向可用的bmap，若超过8个的话就把多的数据根据这个指针传到另一个bmap去
    • 有key和value，最多只能存8个k-v对，注意这里存的不是值，也是key和value的地址
• 在runtime包里面
• 扩容是因为如果哈希值太多，溢出桶指向溢出桶指向溢出桶，这样性能就会大跌
  • 装载因子超过6.5会触发扩容，即每个桶里平均装了6.5个以上数据
  • 溢出桶数量大于普通桶数量也会触发扩容(这里的扩容有可能不增加桶数，只做整理，因为可能之前很多然后删了之后现在数据很少，会很稀疏地存在)
  • step1：建新的双倍普通桶，然后bucket指向新桶，oldbucktet指向旧桶，并且把该hmap标记为扩容
  • step2：渐进式转移数据，即每一次数据要写到旧桶时才把这个旧桶的数据转移到新桶里，这时候还会顺带迁移8个桶(即渐进式并不完全依赖于访问)
  • step3：当所有旧桶里都迁移完了之后就释放旧桶占据的内存空间（所以会有并发问题）
• 读多写少要用sync.Map，里面读不加锁，写加锁
  • 里面有两个map，一个read map，一个dirty map
    • 正常的读、修改都走read这个map
    • 发生追加的时候走dirty这个map，mutex锁会去锁dirty
      • 并且如果发送追加/删除时dirty为空，则触发把read数据拷贝过来
    • 上升操作：每次去read读不到并且dirty里能读到时，misses+1，当misses==len(dirty)时触发把dirty上升为read，并把老read删除

10.Go的GC用的是“标记-清除”

• 具体算法是三色标记法
  • 首先，所有的节点都置为白色
  • 接着，把所有Root Set节点置为灰色
    • 被栈上、全局变量、寄存器中的指针引用的节点
    • (寄存器中的指针即os正在操作处理时用的指针)
  • 然后，把Root Set引用的所有节点置为灰色
  • 如此循环往复，当灰色队列里面为空时表示扫描完成，开始清除所有白色的节点
• 强三色不变性：黑色只会指向灰色或者黑色，实现方法是如果指向白色就置其为灰色，目的是提高GC效率
• 插入屏障、删除屏障组成的混合屏障实现了上述三色不变性
  • 把插入的节点统一置灰
  • 把删除的节点相关节点统一置灰
• gc调优
  • GODEBUG=gctrace=1来查看GC日志，具体判断需要调哪些参数
  • GOGC=100表示，当前堆中的内存达到当前分配内存的100%时启动GC，可以调小一点来频繁触发GC

11.Go的内存管理

• 单位是heapArena，64M
• 大对象(大于32k)按需分配，小对象按级分配，微对象(小于16b)多个合并直到满足16b再按级分配
• 每个线程P有一个本地的内存mcache做缓存用，里面每个级别的mspan分别有2个(scan和noscan)，每次线程要申请空间时不用去中央要，先从自己本地去要，这种结构类似协程调度的GMP模型

12.go程序的启动过程

• 运行rt0文件。go程序的入口底层上是runtime库的rt0_xx.s汇编文件，而不是main.go
  • 有多个rt0文件，不同的操作系统、芯片用不同的rt0文件
• 起g0协程。g0是调度协程的协程，即母协程，是第一个协程
  • 启动调度器
• 启动主协程，并放入调度器，运行main.go
  • 执行runtime包的init()方法
  • 启动GC垃圾收集器
  • 执行用户包依赖的init()方法
  • 最后再执行用户的main()方法

13.defer关键字

• 碰到defer的时候会记录地址，然后当前函数返回的时候调deferreturn()去执行这个地址，多个defer遵循先进后出
  • 当前函数返回有两步，1.将返回值赋给一个新变量，除非这个返回值是传参那么就直接用传参2.执行RET返回指令
  • defer会在第一步之后就执行，如果在defer里修改了返回值，且这个返回值用的是传参来存的那么就会影响，用局部变量来存的不影响

    a = 1;
    defer{a++};
    return a;
    //a是传参会返回2
    //a不是传参会返回1

• 一般记录在栈上，如果defer里面有recover就放到堆上
• defer的语句如果在执行前就确定了，那么编译器会直接把defer的内容加在函数末尾，这样也叫开放编码

14.context的使用

• 每个goroutine在运行前，都要事先知道程序当前的执行状态，通常将这些状态封装在一个context变量。context包通过构建树形关系的context，来达到上一层goroutine对下一层goroutine的控制
• context应该作为参数传递，而不是存储在结构体或全局变量中，以确保上下文信息在并发环境中正确传递和管理
• 具体方法：
  • context.Backupgroup()得到根节点的context
  • context.TODO()得到一个context，不知道使用什么contex时一般使用这个
  • context.WithCancel()得到一个可取消的context子节点，可以调用返回的cancel函数来取消该context
  • context.WithTimeout()和WithDeadline()得到一个有时间限制子节点，超时会自动取消
  • context.Done()来判断是否这个contex是否结束
    • 因为当一个请求被取消或超时时，所有用来处理该请求的goroutine都应该迅速退出
  • context.get()、set()从里面拿k-v、设置k-v

15.recover和panic

• recover用于从panic中恢复
• panic一旦触发会直接终止当前协程，并向调用堆栈的上层函数传播，直到被最外层的recover捕获或者程序结束
  • 当前协程的panic只能被当前协程的recover捕获
  • 所以要在当前协程的defer里面写recover()，确保发生panic时不带崩其他协程

16.interface{}

• 底层是iface结构体
• 记录了数据的地址、具体底层是由什么类型实现的以及实现的方法
  • 所以当接口有类型信息时，空接口就不会是nil了

17.类型断言和类型判断

• 类型断言：用x.(T)来断言是不是T类型

  _,ok : = x.(T);

• 类型判断：用一个变量来存x.(type)

  switch t := x.(type) {
  case int:
      xx1
  ......

18.defer和return的执行顺序详解

• 首先return将结果写入返回值
  • 非命名的话创建一个临时变量存
• 接着defer开始执行一些收尾工作
  • 如果这里的defer改变了return保存的变量，那么就会影响函数最后的返回值
• 最后函数携带当前返回值退出

19.别名类型和源类型的关系

• type MyString = string，MyString是string的别名类型，他俩是完全相同的，只是名字不一样
• type MyString string，这种又叫类型定义，string是MyString的潜在类型，潜在类型指的是本质是什么类型，他俩属于不同类型不能比较、互相赋值，但是可以强转

20.能做map的key的类型需要满足可比较这个条件

• 通道channel可以做map的key，因为channel是可比较的
  • ps：channel是引用类型实质上是一个指针，所以比较其实比的是内存地址

21.case的表达式会在select执行之初就计算出来

• 如果多个满足，那么就以伪随机算法选取分支执行
  • go内部根据满足分支的数量生成一个随机数，然后用这个随机数来选择分支
• 如果一个都没满足且没有default分支，那么select就会阻塞，直到其中某一分支满足

22.go的面向对象怎么实现

• 继承：通过组合的形式来模拟继承，例如A类里面包含了B类成员
• 封装：通过首字母大小写来实现，包内、外访问权限的控制
• 多态：使用多个接口来实现多态，定义多个类实现同一个接口，那么就可以在不同类型对象上调用相同名称的方法

23.结构体里面内嵌了一个interface叫a

• 作用是把这个a作为匿名成员，实现的场景是：
  • 该结构体没有实现a内所有的方法，按理说是不能声明该结构体为a的，但是如果内嵌了，那么就可以声明了
  • 只是在运行中去调用这个没有实现方法时才会报错

24.用go的singleflight库去执行函数

• 底层是map + sync.waitgroup，原理是：
  • 如果调用map中不存在的call，那么就加锁执行，执行完成后释放done()
  • 如果调用map存在的call，那么就wait()，直到释放后就直接取map里的结果即可
• 适用场景是某个用户并发大量地访问redis里不存在的key，导致缓存击穿大请求直接访问到db上，使用这个库就可以保证击穿只访问db层一次

25.once对象去执行某方法，可以保证无论起多少个协程去执行，这个方法全局只被执行一次

• once底层是靠mutex实现的
  • mutex底层是靠信号量锁sema实现的

26.go的包管理

• go mod的常见命令有哪些
  • go mod init：把当前目录初始化为一个新模块，创建go.mod文件
  • go mod tidy：删掉不再依赖的模块
  • go mod download：下载go.mod里的依赖到本地
• go get的是模块还是包，mod文件里required的是模块还是包，包和模块有什么区别
  • 包是在同一目录下的go文件
  • 模块是一个包的集合，在go.mod文件里声明
  • go get xx的这个xx如果是模块名那么拉下来的就是模块，如果xx是模块名/包名，那么拉下来的就是这个模块里的特定包
• go.mod和go.sum的区别
  • .mod记录的是直接依赖及其版本号
  • .sum记录的是直接和间接依赖及其版本号
    • 同时.sum还会给每个依赖根据其内容生成一个加密hash值，如果后面需要重新到网上下载同版本的该依赖时会重新比对hash值，如果不一样说明网上这个依赖被修改了，go此时会发出警告

数据结构与算法

1.哈希表的负载因子

• 负载因子=已保存节点空间/哈希表空间，一般设为0.75

2.set和array的区别

• 唯一性。set的底层是红黑树，但是保证唯一性用的是哈希表
  • 保证唯一性的底层实现是，先判断key得到的hashcode有一样的么，如果有，那么再调equals()去检查

3.如果发生哈希冲突应该怎么处理，哈希表的时间复杂度是多少
- 链表法，插入、查询、判断key值开销：unordered_map是O(1)，map是O(logn)
- 还有开放寻址法、再哈希法、公共溢出区法三种方法，开放寻址法即在冲突位置依照某种规则计算出下一个位置，例如线性+1

4.二叉树时间复杂度

• O(logn)，查找和开销都是这个

5.动态数组删除元素的时间复杂度

• O(n)，因为无论是开辟新数组还是移动其他成员的位置，复杂度都是n

6.unordered和普通的数据结构有什么区别，比如unordered_map和map

• 底层：unordered_map底层是hash_map，map底层是红黑树
  • hash_map是由vector和链表构成，每个vector的位置连一个链表，声明的时候就会自动初始化一个vector去占用空间(质数，不同编译器用不同的质数比如53)
• 顺序：unordered_map是插入顺序，map是按key从小到大排列的
• 插入、查询、判断key值开销：unordered_map是O(1)，map是O(logn)

7.红黑树的特性

• 每个节点或者是黑色，或者是红色。
• 根节点是黑色
• 每个叶子节点是黑色(注意：红黑树叶子节点是NULL)
• 不能出现连续的黑色节点
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

8.红黑树与AVL树比较，都是BST(二叉搜索树)

• AVL是严格的平衡二叉搜索树，执行插入或删除，往往需要开销较大的旋转来保持平衡，但是高度较低
• 红黑树是一种弱平衡二叉搜索树，只需确保没有一条路径比其他路径长两倍即可，所以旋转次数少，但是高度较高
• 查询较多的情况用AVL树，
• 插入和删除场景较多的情况用红黑树，map和set

9.list底层

• 底层数据结构是双向链表，所以不支持下标访问，不是连续的内存空间
• list每次插入都需要申请内存

10.dijkstra和spfa区别

• dijkstra用堆，spfa用优先队列
• dijkstra不能处理负权值，spfa可以处理
• spfa的最坏复杂度和dijkstra相同，但是spfa可能会被卡

11.deque

• 底层由多段等长的连续空间组成
• 用一个数组存放指向这些连续空间地址的指针
  • 和unordered_map底层类似

12.希尔排序就是插入排序的改进版，也是不稳定的

• 先划分子序列，注意这里划分的子序列是交错的
  • 按增量的方式进行子序列划分，将整个序列中下标值相差固定值的所有元素划分到同一个子序列中。比如，整个序列有9个元素，而增量为3，那么第0、3、6个元素属于第一个子序列，第1、4、7个元素属于第二个子序列，第2、5、8个元素属于最后一个子序列
• 然后对每个子序列进行插入排序
• 然后再按一个新的较小的增量进行划分，再重复以上步骤
• 最后得到完整的排序

13.sort底层是快排

• 元素少的话会去用插入排序
• 用快排是因为快排在比较随机的分布上，表现较好

14.排序的稳定性

• 常见的算法中只有冒泡、插入、归并是稳定的
• 排序算法的稳定性通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同

场景设计

1.秒杀系统最重要的是异步、削峰，通过拦截器、分布式架构和消息队列实现

2.缓存数据一致性如何保证

• 一般而言都是先更新数据库，再去缓存里删老数据
• 两种方案
  • 双写策略：修改完数据库后，马上再用set方法将新数据写入到缓存中
    • 缺点：写入数据库后，再写入到缓存中这一步可能会由于网络原因延迟，导致脏数据
      • 例如改了数据库a改成1然后再改成2，此时网络波动改成1的写缓存操作在改成2的写缓存操作之后才执行，这样就不一致了
    • 解决办法：设置过期时间，这样一段时间后到数据库里取更新缓存的数据仍然可以得到正确数据
  • 先写后删策略:修改完数据库后，马上把缓存中的数据去删掉
    • 缺点：删除因为网络波动延迟和删除操作失败仍然可能有脏数据
    • 解决办法：设置过期时间，MQ异步处理保证执行删除
  • 延迟双删策略：先删缓存，再写数据库，延迟n秒后再去删缓存
    • 缺点：这n秒里还是会有脏数据，因此仍然不是强一致性的
    • 解决办法：设置过期时间，MQ异步处理保证执行删除
• 根据系统设计的思想：
  • 放入缓存的数据本就不应是实时性的、一致性要求很高的，所以缓存数据的时候要加上过期时间保证每天拿到最新的即可。
  • 遇到实时性、一致性要求高的数据，就应该直接查数据库，即使速度慢一些

3.rabbitmq如何保证消息不丢失，如果发送了多次相同的消息要怎么处理

• 消息丢失有三种
  • 生产者发给mq途中丢失：开启confirm机制给每个消息分配一个id，生产者发送消息后mq收到返回ACK，没收到返回nack
  • mq因为断电等情况丢失：设置消息持久化和镜像集群
  • mq发给消费者途中丢失：开启AKC应答机制，即消费者收到后给mq回一个ACK
    • kafka的ack有以下三种策略：
    • ACK = 0 时 发送一次 不论下游是否接收
    • ACK = 1 时，等待下游接收成功即可
    • ACK = -1 时 ，需等待下游将消息同步给消息队列

4.如果让你设计一个应用层的协议你会考虑什么，怎么去识别包的长度，如果包里本身包含这个特殊字符怎么办
- 用socket封装实现，基于TCP去实现，考虑首部包含资源的位置、请求的方式、协议版本
- 1.首部加一个len字段 2.用特殊字符做分割，换一个少用的字符或者加转义符/

5.rabbitmq和kafka的优缺点

• rabbitmq有消息存活时间和延迟/预定消息， kafka有ack机制可以保证消息的顺序处理
• rabbitmq消息一旦消费成功就会删除，反之处理失败则放回；但kafka会一直保留消息，根据超时时间来删除，可以反复消费消息消费者可以根据自己的能力进行消费
• rabbitmq是基于推的消息传递系统，可以具有更好地实时性，但会使消费者处于高风险中，而kafka是基于拉的消息传递系统，消费者可以根据自己的能力进行消费。
• kafka使用分区的结构，在横向扩展上更有优势

6.让你设计一个线程安全的hash map，怎么设计

• 讲了read map和脏map来进行读写分离，说开销太大，有没有一个map实现的
• 讲了加读写锁，说太常规，开销大
• 讲了加锁的时候给随机字符串，要写的时候这个字符串和自己本地的字符串相同才表明是自己加的锁可以操作，否则表示其他线程加的锁不可以操作

7.让你实现一个微博推送：

• 实现功能点：
  • 用户可以发布新消息
  • 用户可以查阅他们关注的人发布的推文
• 第一种实现方式：发布推文时，只需将新推文插入全局推文集合即可。当一个用户请求自己的主页时间线时，首先查找他关注的所有人，查询这些被关注用户发布的推文并按时间顺序合并
• 第二种实现方式：为每个用户的主页时间线维护一个缓存，就像每个用户的推文收件箱。当一个用户发布推文时，查找所有关注该用户的人，并将新的推文插入到每个主页时间线缓存中。 因此读取主页时间线的请求开销很小，因为结果已经提前计算好了。
  • 推特的第一个版本使用了方法1，但系统很难跟上主页时间线查询的负载。所以公司转向了方法2，方法2的效果更好，因为发推频率比查询主页时间线的频率几乎低了两个数量级，所以在这种情况下，最好在写入时做更多的工作，而在读取时做更少的工作。
  • 然而方法2的缺点是，发推现在需要大量的额外工作。平均来说，一条推文会发往约75个关注者，所以每秒4.6k的发推写入，变成了对主页时间线缓存每秒345k的写入。但这个平均值隐藏了用户粉丝数差异巨大这一现实，一些用户有超过3000万的粉丝，这意味着一条推文就可能会导致主页时间线缓存的3000万次写入！及时完成这种操作是一个巨大的挑战 —— 推特尝试在5秒内向粉丝发送推文。
• 混合方式：大多数用户发的推文会被扇出写入其粉丝主页时间线缓存中。但是少数拥有海量粉丝的用户（即名流）会被排除在外。当用户读取主页时间线时，分别地获取出该用户所关注的每位名流的推文，再与用户的主页时间线缓存合并，如方法1所示。这种混合方法能始终如一地提供良好性能。

9.小内存，巨量数据类型题(频次有关用哈希，大小有关用小顶堆)

• 1G内存的机器，有1000G的日志文件(每一条有ip属性)，怎么得到出现次数前10的ip？
  • hash分桶法，先切片按ip哈希分成1000个桶，每个桶里计算前10的ip，最后再汇总得到总前10的ip
• 1G内存的机器，1000G大小的整数，怎么去重
  • 先按哈希分组，再每个组里面内部比较去重
• 1G内存的机器，1000G大小的整数，怎么求前100个最大的
  • 用前100个数建立一个小顶堆(原理堆排序)，然后从遍历第101个开始，如果当前数大于堆顶则堆顶压出，把当前数压进去，并重新进行堆排序
• 1G内存的机器，1000G大小的整数，怎么求中位数
  • 先用小顶堆求出最大的1G数，然后取堆顶，其他全抛弃，再遍历一遍比这个数小的才能入栈，这样就可以得到第2G大的数…..最终得到第2.5G大的中位数

10.引包出现的循环依赖问题

• 如何判断有依赖？
  • 第一种办法：dfs，先随机从某节点出发往下走，并记录走过的节点，走到头回到上一节点走下一条路，如果走到了重复的点就说明有环
  • 第二种办法：拓扑排序，先把没有依赖的包初始化并降低依赖这些包的入度，然后把入度为0的包放进队列，等待下一轮初始化，直到队列为空，如果还有包没初始化，那么就说明有依赖
• 有环的话怎么解决？
  • 枚举断边，再判断是否断环
• 如果是多个环耦合的话怎么解决
  • 枚举断边，
• 如果是多个环耦合的话，怎么返回各个环的依赖顺序
  • 深搜+回溯

10.思维题

• 1.1000瓶药水，其中一瓶有毒，喝到有毒的24小时之后会死，请问一天之内试出有毒的药水需要几只小白鼠
  • 二进制编号
• 2.有一个50个球的盒子，每次可以拿1-7个球，你先手拿，怎样保证自己能拿到最后一个球
  • 自己拿完之后保证盒子里的球数为8的倍数即可，这样无论对手拿几个，最后都能自己胜利
• 3.有三扇门，其中一扇门背后有奖品，某次选择中，你先选A门，然后主持人打开了B门发现是空的，请问这时候你是维持当前选择，还是选另一扇没打开的C门中奖概率更高
  • 坚持初选：当你最初选择门A时，奖品在门A后面的概率为1/3。
  • 切换选择：因为此时选项只有两个A或C，已知A、C必有奖品，即C门有奖品的概率为1-1/3 = 2/3
    • 这个2/3其实是根据两种情形叠加的，即主持人打开B，你选C + 主持人打开C你选B
• 4.给一堆相同的绳子，密度不均匀，已知一根绳子烧完是1小时，如何得到15分钟烧完的绳子
  • a绳两头烧，b绳一头烧，a绳烧完后b绳剩余长度就是30分钟，如此反复就可得到15分钟的绳子
• 5.一个通往真话村和假话村的路口有有一个人，但你不知道他来自哪个村，怎么去到真话村
  • 问他“你来自哪个村”，朝着他指的方向走即可
  • 真话村民会指向真话村，假话村民也会指向真话村
• 6.一个通往真话村和假话村的路口有有两个人，他们其中一个是真话村民，一个是假话村民
  • 任意问一个人“如果让你身边的人指路真话村，他会指向哪”，然后朝着相反的方向走即可
  • 真话村民会知道假话村民指向假话村，假话村民会知道真话村民指向真话村，但是他要说谎，于是也是指向假话村

11.分流的技术方案

• 负载均衡：硬件、软件、DNS
• 应用层分流：例如不同uid打到不同后端服务器
• 数据库分片、主从复制

12.场景设计题

• 有一本英文书籍，怎么压缩它来存储？
  • 1.把常用的单词建一个字典，用字典的索引来表示该单词
  • 2.使用变长编码，例如霍夫曼编码，使得频率高的单词变成较短编码，频率低的单词变成较长编码
  • 3.使用压缩算法，例如LZ77去识别字符串中的重复模式和冗余数据，将其替换成更短的表达形式