LRU 算法

[内存管理] 的一种页面置换算法，对于在内存中但又不用的 [数据块]（内存块）叫做 LRU，操作系统会根据哪些数据属于 LRU 而将其移出内存而腾出空间来加载另外的数据，常用于页面置换算法，是为虚拟页式存储管理服务的。

设计原则

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

实现 LRU

1. 用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为 0 并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为 0。当数组空间已满时，将时间戳最大的数据项淘汰。

2. 利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

3. 利用链表和 hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回 - 1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
   对于第一种方法，需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是 O (n)。对于第二种方法，链表在定位数据的时候时间复杂度为 O (n)。所以在一般使用第三种方式来是实现 LRU 算法。

http 协议

一个 HTTP 请求报文由请求行（request line）、请求头部（header）、空行和请求数据 4 个部分组成

请求行

请求行由请求方法字段、URL 字段和 HTTP 协议版本字段 3 个字段组成，它们用空格分隔。

GET

常见的一种请求方式，当客户端要从服务器中读取文档时，当点击网页上的链接或者通过在浏览器的地址栏输入网址来浏览网页 的，使用的都是 GET 方式。GET 方法要求服务器将 URL 定位的资源放在响应报文的数据部分，回送给客户端。使用 GET 方法时，请 求参数和对应的值附加在 URL 后面，利用一个问号（“?”）代表 URL 的结尾与请求参数的开始，传递参数长度受限制。例 如，/index.jsp?id=100&op=bind, 这样通过 GET 方式传递的数据直接表示在地址中，所以我们可以把请求结果以链接的形式发 送给好友

POST

使用 POST 方法可以允许客户端给服务器提供信息较 多。POST 方法将请求参数封装在 HTTP 请求数据中，以名称 / 值的形式出现，可以传输大量数据，这样 POST 方式对传送的数据大 小没有限制，而且也不会显示在 URL 中，POST 方式请求行中不包含数据字符串，这些数据保存在” 请求内容” 部分，各数据之间也是使用”&” 符号隔开。POST 方 式大多用于页面的表单中。因为 POST 也能完成 GET 的功能，因此多数人在设计表单的时候一律都使用 POST 方式，其实这是一个 误区。

HEAD

HEAD 就像 GET，只不过服务端接受到 HEAD 请求后只返回响应头，而不会发送响应内容。当我们只需要查看某个页面的状态的时 候，使用 HEAD 是非常高效的，因为在传输的过程中省去了页面内容。

请求头部

请求头部由关键字 / 值对组成，每行一对，关键字和值用英文冒号 “:” 分隔。
请求头部通知服务器有关于客户端请求的信息，典型的 请求头有：
User­Agent：产生请求的浏览器类型。
Accept：客户端可识别的内容类型列表。
Host：请求的主机名，允许多个域名同处一个 IP 地址，即虚拟主机。

空行

后一个请求头之后是一个空行，发送回车符和换行符，通知服务器以下不再有请求头。

请求数据

请求数据不在 GET 方法中使用，而是在 POST 方法中使用。POST 方法适用于需要客户填写表单的场合。与请求数据相关的常使 用的请求头是 Content­Type 和 Content­Length。

HTTP 相应报文

HTTP 响应也由三个部分组成，分别是：状态行、消息响应头、响应正文。

状态码

1xx：指示信息表示请求已接收，继续处理。
2xx：成功表示请求已被成功接收、理解、接受。
3xx：重定向要完成请求必须进行更进一步的操作。
4xx：客户端错误请求有语法错误或请求无法实现。
5xx：服务器端错误服务器未能实现合法的请求。

常见状态代码、状态描述的说明如下

200 OK：客户端请求成功。
400 Bad Request：客户端请求有语法错误，不能被服务器所理解。
401 Unauthorized：请求未经授权，这个状态代码必须和 WWW­Authenticate 报头域一起使用。
403 Forbidden：服务器收到请求，但是拒绝提供服务。
404 Not Found：请求资源不存在，举个例子：输入了错误的 URL。500 Internal Server Error：服务器发生不可预期的错误。
503 Server Unavailable：服务器当前不能处理客户端的请求，一段时间后可能恢复正常，举个例子：HTTP/1.1  200 OK（CRLF）。

GET 和 POST

GET 提交，请求的数据会附在 URL 之后（就是把数据放置在 HTTP 协议头＜request­line＞中），以？分割 URL 和传输数据，多个 参数用 & 连接 ; 如果数 据是英文字母 / 数字，原样发送，如果是空格，转换为 +，如果是中文 / 其他字符，则直接把字符串用 BASE64 加密，，GET 提交的数据会在地址栏中显示出来，而 POST 提交，地址栏不会改变， POST 提交：把提交的数据放置在是 HTTP 包的包体＜request body＞中。
HTTP 协议没有对传输的数据大小进行限制，HTTP 协议规范也没有对 URL 长度进行限制。而在实际开发中存在的限制 主要有：
GET: 特定浏览器和服务器对 URL 长度有限制，例如 IE 对 URL 长度的限制是 2083 字节 (2K+35)。对于其他浏览器，如 Netscape、FireFox 等，理论上没有长度限制，其限制取决于操作系统的支持。 
 因此对于 GET 提交时，传输数据就会受到 URL 长度的限制。   
 POST: 由于不是通过 URL 传值，理论上数据不受限。但实际各个 WEB 服务器会规定对 post 提交数据大小进行限制，Apache、 IIS6 都有各自的配置。
 POST 的安全性要比 GET 的安全性高。注意：这里所说的安全性和上面 GET 提到的 “安全” 不是同个概念。上面 “安全” 的含义仅仅 是不作数据修改，而这里安全的含义是真正的 Security 的含义，比如：通过 GET 提交数据，用户名和密码将明文出现在 URL 上，因 为 (1) 登录页面有可能被浏览器缓存， (2) 其他人查看浏览器的历史纪录，那么别人就可以拿到你的账号和密码了，

数据类型

标量 ：boolean （布尔型）integer （整型）float （浮点型，也称作 double) string （字符串）
复合 ：数组 对象
特殊 ：NULL resource (资源)

常见的 header 头

// 信息型状态码，提示目前为止一切正常，客户端应该继续请求，如果已完成请求则忽略.
header('HTTP/1.1 100 OK');
// 通知浏览器 页面不存在
header('HTTP/1.1 404 Not Found');
// 资源被永久的重定向 301 ;302：临时重定向（该资源临时被改变位置）
header('HTTP/1.1 301 Moved Permanently');
// 跳转到一个新的地址
header('Location: http://php.itcast.cn/');
// 延迟转向也就是隔几秒跳转
header('Refresh:10;url=http://php.itcast.cn/');

内容类型

// 网页编码
header('Content-Type: text/html;charset=utf-8');
// 纯文本格式
header('Content-Type:text/plain');
//JPG、JPEG
header('Content-Type:image/jpeg');
//ZIP 文件
header('Content-Type:application/zip');
//PDF 文件
header('Content-Type:application/pdf');
// 音频文件
header('Content-Type: ');
//css 文件
header('Content-type:text/css');
声明一个下载的文件
header('Content-Type:application/octet-stream');
header('Content-Disposition:attachment;filename="ITblog.zip"');
显示一个需要验证的登陆对话框
header('HTTP/1.1 401Unauthorized');
header('WWW-Authenticate:Basic realm="TopSecret"');

魔术方法

__autoload () 类文件自动加载函数
__construct () 构造函数，PHP 将在对象创建时调用这个方法
__destruct ()  析构函数，PHP 将在对象被销毁前（即从内存中清除前）调用这个方法
__call () 当所调用的成员方法不存在（或者没有权限）该类时调用，用于对错误后做一些操作或者提示信息
__clone () 该函数在对象克隆时自动调用，其作用是对克隆的副本做一些初始化操作
__get () 当所对象所调用的成员属性未声明或者级别为 private 或者 protected 等时，我们可以在这个函数里进行自己的一些操作
__set () 当所对未声明或者级别为 private 或者 protected 等进行赋值时调用此函数，我们可以在这个函数里进行自己的一些操作
__isset () 当对一个未声明或者访问级别受限的成员属性调用 isset 函数时调用此函数，共用户做一些操作
__unset () 当对一个未声明或者访问级别受限的成员属性调用 unset 函数时调用此函数，共用户做一些操作
__toString () 函数 该函数在将对象引用作为字符串操作时自动调用，返回一个字符串
__sleep () 函数 该函数是在序列化时自动调用的，序列化这里可以理解成将信息写如文件中更长久保存
__wakeup () 函数 该魔术方法在反序列化的时候自动调用，为反序列化生成的对象做一些初始化操作
invoke () 函数，当尝试以调用函数的方式调用一个对象时，invoke 方法会被自动调用。
_callStatic () 函数，它的工作方式类似于 call () 魔术方法，callStatic () 是为了处理静态方法调用，

超全局变量

$GLOBALS 是 PHP 的一个超级全局变量组，在一个 PHP 脚本的全部作用域中都可以访问。是一个包含了全部变量的全局组合数组。变量的名字就是数组的键。
$_SERVER 是一个包含了诸如头信息 (header)、路径 (path)、以及脚本位置 (script locations) 等等信息的数组。这个数组中的项目由 Web 服务器创建。不能保证每个服务器都提供全部项目；服务器可能会忽略一些，或者提供一些没有在这里列举出来的项目。
$_REQUEST 用于收集 HTML 表单提交的数据。
$_POST 被广泛应用于收集表单数据，在 HTML form 标签的指定该属性："method="post"。
$_GET 同样被广泛应用于收集表单数据，在 HTML form 标签的指定该属性："method="get"。
$_COOKIE 经由 HTTP Cookies 方法提交至脚本的变量
$_SESSION 当前注册给脚本会话的变量。类似于旧数组 $HTTP_SESSION_VARS 数组。
$_FILES 经由 HTTP POST 文件上传而提交至脚本的变量。类似于旧数组 $HTTP_POST_FILES 数组。
$_ENV 执行环境提交至脚本的变量。类似于旧数组 $HTTP_ENV_VARS 数组。

http 和 https 区别

1、https 协议需要到 ca 申请证书，一般免费证书较少，因而需要一定费用。
2、http 是超文本传输协议，信息是明文传输，https 则是具有安全性的 ssl 加密传输协议。
3、http 和 https 使用的是完全不同的连接方式，用的端口也不一样，前者是 80，后者是 443。
4、http 的连接很简单，是无状态的；HTTPS 协议是由 SSL+HTTP 协议构建的可进行加密传输、身份认证的网络协议，比 http 协议安全。

hash 取模算法

hash 算法

分布式 cahce 系统中的一致性 hash 算法应该满足以下几个方面

平衡性 (Balance)

哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

单调性 (Monotonicity)

如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod (P)，在上式中，P 表示全部缓冲的大小。不难看出，当缓冲大小发生变化时 (从 P1 到 P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在 P2P 系统内，缓冲的变化等价于 Peer 加入或退出系统，这一情况在 P2P 系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

分散性 (Spread)

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

负载 (Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

平滑性 (Smoothness)

平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

hash 取模算法

常用的算法是对 hash 结果取余数 (hash () mod N)：对机器编号从 0 到 N-1，按照自定义的 hash () 算法，对每个请求的 hash () 值按 N 取模，得到余数 i，然后将请求分发到编号为 i 的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有 (N-1)/N 的服务器的缓存数据需要重新进行计算；

为何是 (N-1)/N 呢

比如有 3 台机器，hash 值 1-6 在这 3 台上的分布就是：

host 1: 1 4
host 2: 2 5
host 3: 3 6

如果挂掉一台，只剩两台，模数取 2 ，那么分布情况就变成：

host 1: 1 3 5
host 2: 2 4 6

可以看到，还在数据位置不变的只有 2 个： 1，2，位置发生改变的有 4 个，占共 6 个数据的比率是 4/6 = 2/3。

虚拟节点

对于 hash 取模算法，当某个节点的服务器坏了，算有压力将转到下个节点的服务器。那我们考虑是否能够将压力转到其他节点。

虚拟节点即：N 个真实节点，把每个真实节点映射成 M 个虚拟节点，再把 M* N 个虚拟节点，散列在圆环上。各真实节点对应的虚拟节点相互交错分布，这样，某真实节点 down 后，则把其影响平均分担到其他所有节点上。

访问方法：

如果有一个写入缓存的请求，其中 Key 值为 K，计算器 hash 值 Hash (K)， Hash (K) 对应于环中的某一个点，如果该点对应没有映射到具体的某一个机器节点，那么顺时针查找，直到第一次找到有映射机器的节点，该节点就是确定的目标节点，如果超过了 2^32 仍然找不到节点，则命中第一个机器节点。

一致性哈希算法

一种特殊的哈希算法，目前主要应用于分布式缓存当中，可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。

一致性 Hash 算法是对 2^32 取模，2^32 个点组成的圆环称为 Hash 环。根据服务节点的 IP 或者机器名称进行哈希，就能确定每台机器就能确定其在哈希环上的位置；
将数据 key 使用相同的函数 Hash 计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针 “行走”，第一台遇到的服务器就是其应该定位到的服务器。
添加、删除节点的时候，只影响相邻一个节点的数据，其他节点的数据不影响。具有较好的扩展性和容错性。
为了防止数据分布不均匀，可以应用虚拟节点来映射物理节点。

hash 槽

Redis 准备了 16384 个 hash 槽，类似于 Memcached Hash 环上的一个个位置。这 16384 个 hash 槽被分配给不同节点，存放数据时，根据数据的 key 计算出所在的槽，再根据槽找到对应的机器。hash 函数为：CRC16 (key) % 16384。

为什么是 16384？

我们需要维护节点和槽之间的映射关系，每个节点需要知道自己有哪些槽，并且需要在结点之间传递这个消息。为了节省存储空间，每个节点用一个 Bitmap 来存放其对应的槽: 2k = 210248 = 16384，也就是说，每个结点用 2k 的内存空间，总共 16384 个比特位，就可以存储该结点对应了哪些槽。然后这 2k 的信息，通过 Gossip 协议，在结点之间传递。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。