memcached 虽然称为 “ 分布式 ” 缓存服务器，但服务器端并没有 “ 分布式 ” 功能。每个服务器都是完全独立和隔离的服务。memcached 的分布式，则是完全由客户端程序库实现的。这种分布式是 memcached 的最大特点。

2、memcache的内存分配机制

如何存放数据到memcached缓存中?(memcache内存分配机制)

Slab Allocator内存分配机制：预先将内存分配成数个slab仓库，每个仓库再切出不同大小的chunk，去适配收到的数据。多余的只能造成浪费，不可避免。 增长因子(Grace factor)：一般而言观察数据大小的变化规律设置合理的增长因子，默认1.25倍. 太大容易造成浪费。

如果有100byte的内容要存储，但122大小的仓库的chunk用满了怎么办? 答:是并不会寻找更大仓库的chunk来存储，而是把122仓库中的旧数据踢掉!

3、memcache的惰性失效机制

• 当某个值过期后并不会从内存删除。(因此status统计时的curr_items有其信息) 
• 如果之前没有get过，将不会自动删除。如果(过期失效，没get过一次)又没有一个新值去占用他的位置时，当做空的chunk占用。
• 当取其值(get)时，判断是否过期：如果过期返回空，且清空。(所以curr_items就减少了) 即这个过期只是让用户看不到这个数据而已，并没有在过期的瞬间立即从内存删除，这个过程 称为lazy expirtion，属性失效，好处是节约了cpu和检测的成本，称为“惰性失效机制”

4、memcache缓存的无底洞现象

缓存的无底洞现象：facebook的工作人员反应，他们在2010年左右，memcacahed节点就已经达到3000个，大约数千G的缓存，他们发现一个问题，memchache连接频率太高导致效率下降，于是加memcache节点，添加后发现连接频率导致的问题仍然没有好转，称之为“无底洞现象”。

问题分析：以用户为例：user-133-age，user-133_name，user-133-height………N个key 当服务器增多，133号用户的信息也被散落在更多的服务器， 所以同样是访问个人主页，得到相同的个人信息，节点越多，要连接节点越多，对于memcache的连接数并没有随着节点的增多而降低，问题出现。

事实上：nosql和传统的rdbms并不是水火不容，两者在某些设计上是可以相互参考的。对于nosql的key-value这种存储，key的设计可以参考mysql中表和列的设计。比如user表下有age、name、height列，对应的key可以用user：133：age=23，user：133：name=ls，user：133：height=168;

问题的解决方案：把某一组key按其共同前缀来分布，比如：user：133：age=23，user：133：name=ls，user：133：height=168;在用分布式算法求其节点时，应该以user：133来计算，而不是以user：133：age来计算，这样这三个关于个人信息的key都落在同一个节点上。再次访问只需要连接一个节点。问题解决。

5、一致性Hash算法的实现原理

Hash环

我们把232次方想成一个环，比如钟表上有60个分针点组成一个圆，那么hash环就是由232个点组成的圆。第一个点是0，最后一个点是232-1,我们把这232个点组成的环称之为HASH环。

​

一致性Hash算法

将memcached物理机节点通过Hash算法虚拟到一个虚拟闭环上(由0到232构成)，key请求的时候通过Hash算法计算出Hash值然后对232取模，定位到环上顺时针方向最接近的虚拟物理节点就是要找到的缓存服务器。

假设有ABC三台缓存服务器：我们使用这三台服务器各自的IP进行hash计算然后对232取模即：==**Hash(服务器IP)%232== 计算出来的结果是0到232-1的一个整数，那么Hash环上必有一个点与之对应。比如：

​

​

现在缓存服务器已经落到了Hash环上，接下来我们就看我们的数据是怎么放到缓存服务器的?我们可以同样对Object取Hash值然后对232取模，比如落到了接近A的一个点上：

​

那么这个数据理应存到A这个缓存服务器节点上​

所以，在缓存服务器节点数量不变的情况下，缓存的落点是不会变的。

​但是如果B挂掉了呢? 按照hash且取模的算法，图中3这个Object理应就分配到了C这个节点上去了，所以就会到C上找缓存数据，结果当然是找不到，进而从DB读取数据重新放到了C上。

但是对于编号为1,2的Object还是落到A，编号为4的Object还是落到C，B宕机所影响的仅仅是3这个Object。这就是一致性Hash算法的优点。

Hash环的倾斜

前面我们理想化的把三台memcache机器均匀分到了Hash环上：

​但是现实情况可能是：

​如果Hash环倾斜，即缓存服务器过于集中将会导致大量缓存数据被分配到了同一个服务器上。比如编号1,2,3,4,6的Object都被存到了A，5被存到B，而C上竟然一个数据都没有，这将造成内存空间的浪费。为了解决这个问题，一致性Hash算法中使用“虚拟节点”解决。

​虚拟节点解决Hash环倾斜

​

“虚拟节点”是“实际节点”在hash环上的复制品，一个实际节点可能对应多个虚拟节点。这样就可以将ABC三台服务器相对均匀分配到Hash环上，以减少Hash环倾斜的影响，使得缓存被均匀分配到hash环上。

6、hash算法平衡性

平衡性指的是hash的结果尽可能分布到所有的缓存中去，这样可以使得所有的缓存空间都可以得到利用。但是hash算法不保证绝对的平衡性，为了解决这个问题一致性hash引入了“虚拟节点”的概念。虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica )，一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。“虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。

例如假设 cache A 的 IP 地址为202.168.14.241 。引入“虚拟节点”前，计算 cache A 的 hash 值：Hash(“202.168.14.241”); 引入“虚拟节点”后，计算“虚拟节”点 cache A1 和 cache A2 的 hash 值：

• Hash(“202.168.14.241#1”); // cache A1  
• Hash(“202.168.14.241#2”); // cache A2   

这样只要是命中cacheA1和cacheA2节点，就相当于命中了cacheA的缓存。这样平衡性就得到了提高。

7、memcached与redis的区别

• redis做存储，可以持久化，memcache做缓存，数据易丢失。
• redis支持多数据类型，memcache存放字符串。
• redis服务端仅支持单进程、单线程访问，也就是先来后到的串行模式，避免线程上下文切换，自然也就保证数据操作的原子性。Memcache服务端是支持多线程访问的。
• redis虽然是单进程单线程模式，但是redis使用了IO多路复用技术做到一个线程可以处理很多个请求来保证高性能。

8、Redis的主从复制

• 在Slave启动并连接到Master之后，它将主动发送一个SYNC命令给Master。
• Master在收到SYNC命令之后，将执行BGSAVE命令执行后台存盘进程(rdb快照), 同时收集所有接收到的修改数据集的命令即写命令到缓冲区，在后台存盘进程执行完毕后，Master将传送整个数据库文件到Slave。
• Slave在接收到数据库文件数据之后，将自身内存清空，加载rdb文件到内存中完成一次完全同步。
• 接着，Master继续将所有已经收集到缓冲区的修改命令，和新的修改命令依次传送给Slaves 
• Slave将在本地执行这些数据修改命令，从而达到最终的数据同步 
• 之后Master和Slave之间会不断通过异步方式进行命令的同步，从而保证数据的实时同步 
• 如果Master和Slave之间的链接出现断连现象，Slave可以自动重连Master，但是在重新连接成功之后。

9、Redis的部分复制过程

部分同步工作原理如下：

• Master为被发送的复制流创建一个内存缓冲区(in-memory backlog)，记录最近发送的复制流命令 
• Master和Slave之间都记录一个复制偏移量(replication offset)和当前Master ID(Master run id)
• 当出现网络断开，Slave会重新连接，并且向Master请求继续执行原来的复制进程 
• 如果Slave中断网前的MasterID和当前要连的MasterID相同，并且从断开时到当前时刻Slave记录的偏移量所指定的数据仍然保存在Master的复制流缓冲区里面，则Master会向Slave发送缺失的那部分数据，Slave执行后复制工作可以继续执行。
• 否则Slave就执行完整重同步操作

10、Redis的主从复制阻塞模式

• 同一个Master服务可以同步n多个Slave服务
• Slave节点同样可以接受其它Slave节点的连接和同步服务请求，分担Master节点的同步压力
• Master是以非阻塞方式为Slave提供同步服务，所以主从复制期间Master一样可以提供读写请求。
• Slave同样是以非阻塞的方式完成数据同步，在同步期间，如果有客户端提交查询请求，Redis则返回同步之前的数据

11、Redis的数据持久化方式

Rdb快照和aof ØRDB快照：可以配置在n秒内有m个key修改就做自动化快照方式 ØAOF：每一个收到的写命令都通过write函数追加到文件中。更安全。

12、Redis的高可用部署方式

哨兵模式

redis3.0之前的Sentinel哨兵机制，redis3.0之前只能使用一致性hash方式做分布式缓存。哨兵的出现主要是解决了主从复制出现故障时需要人为干预的问题。

Redis哨兵主要功能

• 集群监控：负责监控Redis master和slave进程是否正常工作 
• 消息通知：如果某个Redis实例有故障，那么哨兵负责发送消息作为报警通知给管理员
• 故障转移：如果master node挂掉了，会自动转移到slave node上 
• 配置中心：如果故障转移发生了，通知client客户端新的master地址

Redis哨兵的高可用

原理：当主节点出现故障时，由Redis Sentinel自动完成故障发现和转移，并通知应用方，实现高可用性

​

• 哨兵机制建立了多哨兵节点，共同监控数据节点的运行状况。
• 同时哨兵节点之间也互相通信，交换对主从节点的监控状况。
• 每隔1秒每个哨兵会向整个集群：Master主服务器+Slave从服务器+其他Sentinel(哨兵)进程，发送一次ping命令做一次心跳检测。

哨兵如何判断redis主从节点是否正常?

涉及两个新的概念：主观下线和客观下线。

• 主观下线：一个哨兵节点判定主节点down掉是主观下线。
• 客观下线：只有半数哨兵节点都主观判定主节点down掉，此时多个哨兵节点交换主观判定结果，才会判定主节点客观下线。

原理：基本上哪个哨兵节点最先判断出这个主节点客观下线，就会在各个哨兵节点中发起投票机制Raft算法(选举算法)，最终被投为领导者的哨兵节点完成主从自动化切换的过程。

集群模式

redis3.0之后的容错集群方式，无中心结构，每个节点保存数据和整个集群状态,每个节点都和其他所有节点连接，需要至少三个master提供写的功能。

因此集群中至少应该有奇数个节点，因此至少有三个节点，每个节点至少有一个备份节点，所以redis集群应该至少6个节点。

每个Master有一个范围的slot槽位用于写数据。

13、Redis可以在线扩容吗?zk呢

Reids的在线扩容，不需要重启服务器，动态的在原始集群中添加新的节点,并分配slot槽。但是zk不能在线扩容，需要重启，但是我们可以选择一个一个重启。

14、Redis高并发和快速的原因

• redis是基于内存的，内存的读写速度非常快;
• redis是单线程的，省去了很多上下文切换线程的时间;
• redis使用多路复用技术，可以处理并发的连接。

缺点：无法发挥多核CPU性能

15、浏览器本地缓存的了解和使用

资源在浏览器端的本地缓存可以通过Expires和Last-Modified返回头信息进行有效控制。

• Expires告诉浏览器在该指定过期时间前再次访问同一URL时，直接从本地缓存读取，无需再向服务器发起http请求;  

优点是：浏览器直接读取缓存信息无需发起http请求。   

缺点是：当用户按F5或Ctl+F5刷新页面时浏览器会再次发起http请求。

• 当服务器返回设置了Last-Modified头，下次发起同一URL的请求时，请求头会自动包含If-Modified-Since头信息，服务器对静态内容会根据该信息跟文件的最后修改时间做比较，如果最后修改时间不大于If-Modified-Since头信息，则返回304：告诉浏览器请求内容未更新可直接使用本地缓存。(注意：只对静态内容有效，如js/css/image/html等，不包括动态内容，如JSP)

优点：无论用户行为如何都有效; 

缺点：仍需向服务器发起一次http请求;

16、缓存雪崩

如果缓存集中在一段时间内失效，发生大量的缓存穿透，所有的查询都落在数据库上，造成了缓存雪崩。

解决办法：没有完美的解决方案，可以通过随机算法让失效时间随机分布，避免同一时刻失效。

17、缓存穿透

访问一个不存在的key，缓存不起作用，请求会穿透到DB，可能DB也没查到，流量大时DB会挂掉。

解决办法： 

1.采用布隆过滤器，使用一个足够大的bitmap，用于存储可能访问的key，不存在的key直接被过滤;

2、访问key未在DB查询到值，也将空值写进缓存，但可以设置较短过期时间。

java中的hashmap面试题

HashMap的Hash碰撞

​

Hash值冲突问题是Hash表存储模型需要解决的一个问题。通常有两种方法：

将相同Hash值的Entry对象组织成一个链表放置在hash值对应的槽位。HashMap采用的是链表法，且是单向链表(通过head元素就可以操作后续所有元素，对链表而言，新加入的节点会从头节点加入。) 核心源码：

private void addEntry(int hash, K key, V value, int bucketIndex) {  

    Entrye = table[bucketIndex];  

    table[bucketIndex] = new Entry(hash, key, value, e);  

    if (size++ >= threshold)  

        resize(2 * table.length);  

}

以上代码说明：系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处。

• 如果 bucketIndex 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象 (产生一个 Entry 链) 
• 如果 bucketIndex 索引处没有 Entry 对象，也就是上面程序代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。HashMap里面没有出现hash冲突时，没有形成单链表时，hashmap查找元素很快,get()方法能够直接定位到元素， 但是出现单链表后，单个bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早 放入该 bucket 中)，那系统必须循环到最后才能找到该元素。

18、HashMap的get和put原理

PUT原理：当调用HashMap的put方法传递key和value时，先调用key的hashcode方法。通过key的Hash值来找到Bucket—-‘桶’的位置，然后迭代这个位置的Entry列表 判断是否存在key的hashcode和equals完全相同的key，如果完全相同则覆盖value， 否则插入到entry链的头部。

HashMap在put时的Entry链形成的场景?

当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：

如果这两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。

如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。

如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部

GET原理：根据该 key 的 hashCode 值计算它的 hash 码，遍历并循环取出 Entry 数组中指定索引处的Entry值，如果该 Entry 的 key 与被搜索 key 相同 ，且Enrty的hash值跟key的hash码相同，然后看是否是Entry链，如果是则迭代这个位置的Entry列表,判断是否存在key的hashcode和equals完全相同的key，如果完全相同则获取value。

19、HashMap的rehash

HashMap初始容量大小为16,一般来说，当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的元素都需要被重算一遍。这叫rehash，这个成本相当的大

20、HashMap的线程不安全问题

比如put操作时，有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引BucketIndex坐标，然后获取到该桶里面的Entry链表header头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。另一个不安全的体现是是get操作可能由于resize而死循环。

​

21、HashMap和Hashtable的区别

相同点：

• 都实现了Map接口 
• Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异

不同点：

• hashMap允许NULL作为key和value，而hashtable不允许
• hashMap线程不安全，Hashtable线程安全 
• hashMap速度快于hashtable 
• HashMap 把 Hashtable的contains方法去掉了，改成containsvalue和containsKey,避免引起误会 
• Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现

22、为什么collection没有实现clonable接口

Collection接口有很多不同的集合实现形式，而clonable只对具体的对象有意义。

23、为什map没有实现collection接口

Set 和List 都继承了Conllection，Map没有继承于Collection接口，Map提供的是key-Value的映射，而Collection代表一组对象。

24、Map接口的实现有哪些,区别是什么

HashMap,LinkedHashMap,Hashtable,TreeMap。

LinkedHashMap 是HashMap的一个子类，保存了记录的插入顺序 Hashtable和HashMap类似，它继承自Dictionary类，不同的是它不允许键或值为空。TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器。​

​

 想要学习更多的知识可以，工众号：编程领域