腾讯后台开发暑假实习一面

问题列表

1. 一致性哈希
2. Linux间进程间通信
3. HashMap和HashTable的区别
4. Redis和Mysql的区别
5. 一张表加索引会有什么问题
6. 进程、线程、协程的解释
7. 查看系统端口、查看系统内存大小的命令
8. 查看命令所有路径的命令
9. 把一个文件中的aaa替换成bbb
10. 数组和链表的区别

回答参考

1. 一致性哈希

• 算法思想
  一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法，常用于负载均衡。Memcached client也选择这种算法，解决将key-value均匀分配到众多Memcached server上的问题。它可以取代传统的取模操作，解决了取模操作无法应对增删Memcached Server的问题(增删server会导致同一个key,在get操作时分配不到数据真正存储的server，命中率会急剧下降)。

  简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0 - (2^32)-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：

整个空间按顺时针方向组织。0和(2^32)-1在零点中方向重合。

下一步将各个服务器使用H进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中三台服务器使用ip地址哈希后在环空间的位置如下：

接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数H计算出哈希值h，通根据h确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

例如我们有A、B、C、D四个数据对象，经过哈希计算后，在环空间上的位置如下：

根据一致性哈希算法，数据A会被定为到Server 1上，D被定为到Server 3上，而B、C分别被定为到Server 2上。

• 容错性与可扩展性分析

  下面分析一致性哈希算法的容错性和可扩展性。现假设Server 3宕机了：

可以看到此时A、C、B不会受到影响，只有D节点被重定位到Server 2。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

下面考虑另外一种情况，如果我们在系统中增加一台服务器Memcached Server 4：

此时A、D、C不受影响，只有B需要重定位到新的Server 4。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

• 虚拟节点

一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如我们的系统中有两台服务器，其环分布如下：

此时必然造成大量数据集中到Server 1上，而只有极少量会定位到Server 2上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，我们决定为每台服务器计算三个虚拟节点，于是可以分别计算“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”、“Memcached Server 2#1”、“Memcached Server 2#2”、“Memcached Server 2#3”的哈希值，于是形成六个虚拟节点：

2. Linux间进程间通信

• 管道( pipe )：
  普通管道PIPE： 通常有两种限制,一是单工,只能单向传输;二是只能在父子或者兄弟进程间使用.
  流管道s_pipe: 去除了第一种限制,为半双工，只能在父子或兄弟进程间使用，可以双向传输.
  命名管道:name_pipe：去除了第二种限制,可以在许多并不相关的进程之间进行通讯.
• 信号量( semophore ) ：
  信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 消息队列( message queue ) ：
  消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 信号 ( sinal ) ：
  信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 共享内存( shared memory ) ：
  共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
• 套接字( socket ) ：
  套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。

3. HashMap和HashTable的区别

• 相同点：
  实现原理相同，功能相同，底层都是哈希表结构，查询速度快，在很多情况下可以互用 。
• 不同点：
  1、Hashtable是早期提供的接口，HashMap是新版JDK提供的接口。
  2、Hashtable继承Dictionary类，HashMap实现Map接口。
  3、Hashtable线程安全，HashMap线程非安全。
  4、Hashtable不允许null值，HashMap允许null值.

4. Redis和Mysql的区别

• 类型
  redis是一个key-value存储系统,是nosql,即非关系型数据库,和memcached都是- 缓存数据库.
  mysql是关系型数据库
• 存储
  redis用于存储使用相对频繁的数据到内存中
  mysql用于存放持久化数据到磁盘中
• 速度
  redis读取速度快
  mysql相对速度较慢
• 数据类型
  redis数据类型:字符串类型（string），散列类型（hash），列表类型（list），集合类型（set），有序集合类型（zset）
  mysql数据类型,大致三类:数值,日期,字符
• 使用
  一般来说，mysql用于写入和更新，redis用于读取。

5. 一张表加索引会有什么问题

索引的优点

• 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
• 可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
• 可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
• 在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
• 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

索引的缺点

• 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
• 索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
• 当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

6. 进程、线程、协程的解释
   进程，直观点说，保存在硬盘上的程序运行以后，会在内存空间里形成一个独立的内存体，这个内存体有自己独立的地址空间，有自己的堆，上级挂靠单位是操作系统。操作系统会以进程为单位，分配系统资源（CPU时间片、内存等资源），进程是资源分配的最小单位。
   线程，有时被称为轻量级进程(Lightweight Process，LWP），是操作系统调度（CPU调度）执行的最小单位。
   

进程和线程的区别与联系

• 区别：

调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位；

并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行；

拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源。进程所维护的是程序所包含的资源（静态资源）， 如：地址空间，打开的文件句柄集，文件系统状态，信号处理handler等；线程所维护的运行相关的资源（动态资源），如：运行栈，调度相关的控制信息，待处理的信号集等；

系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。但是进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个进程死掉就等于所有的线程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。

• 联系：

一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程；资源分配给进程，同一进程的所有线程共享该进程的所有资源；处理机分给线程，即真正在处理机上运行的是线程；线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。

协程，是一种比线程更加轻量级的存在，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。

子程序，或者称为函数，在所有语言中都是层级调用，比如A调用B，B在执行过程中又调用了C，C执行完毕返回，B执行完毕返回，最后是A执行完毕。所以子程序调用是通过栈实现的，一个线程就是执行一个子程序。子程序调用总是一个入口，一次返回，调用顺序是明确的。而协程的调用和子程序不同。

协程在子程序内部是可中断的，然后转而执行别的子程序，在适当的时候再返回来接着执行。

7. 查看系统端口、查看系统内存大小的命令

netsta -anotp free-h

8. 查看命令所有路径的命令

which whereis

9. 把一个文件中的aaa替换成bbb

vim :%s/aaa/bbb/gc

10.数组和链表的区别

数组在内存中是一块连续的空间，所以可以随机访问了，访问速度更加快。链表在内存中是离散的，是通过前一个节点保存后一个节点的地址来进行访问的，所以链表访问速度慢，插入删除速度快。