前言 作为程序员，应该都对二叉树都不陌生，我们都知道二叉树的变体二叉查找树，非常适合用来进行对一维数列的存储和查找，可以达到 O(logn) 的效率；我们在用二叉查找树进行插入数据时，根据一个数据的值和树结点值的对比，选择二叉树的两个叉之一向下，直到叶子结点，查找时使用二分法也可以迅速找到需要的数据。 但二叉树只支持一维数据，如一个标量数值，对地图上的位置点这种有xy两个方向上的信息却无能为力，那么是否有一种树能够支持二维数据的快速查询呢？ 四叉树 介绍 四元树又称四叉树是一种树状数据结构，在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。它将数据区分成为四...

前言 时隔一个多月，终于又有时间来更新我的服务器了，这次更新主要实现一下 CGI 协议。 先放上GitHub链接 tinyServer-GitHub-枕边书 作为一个服务器，基本要求是能受理请求，提取信息并将消息分发给 CGI 解释器，再将解释器响应的消息包装后返回客户端。在这个过程中，除了和客户端 socket 之间的交互，还要牵扯到第三个实体 - 请求解释器。 如上图所示，客户端负责封装请求和解析响应，服务器的主要职责是管理连接、数据转换、传输和分发客户端请求，而真正进行数据文档处理与数据库操作的就是请求解释器，这个解释器，在 PHP 中一般是 PHP-FPM，JAVA 中是 Se...

前言 上篇博客中提到了空间索引的用途和多种数据库对空间索引的支持情况，那么在应用层以下，好学的小伙伴应该会考虑空间索引的实现原理了。 目前空间索引的实现有 R树和其变种GIST树、四叉树、网格索引等。 网格索引不再多提，使用普通的hash表存储地点和风格之间的映射来实现。今天要介绍的GeoHash算法实现的空间索引，虽然是以B树实现，但我认为它也借用网格索引的一部分思想。 GeoHash 原理 GeoHash 算法的原理说起来是很简单的，如下图： 从横向上将整个方形纸分为左右两份，左侧部分为标记为 0， 右侧部分标记为 1； 再将红点所在的部分划分为左右两块，再对红...

空间索引 索引我们都用过，它是一种特殊的存储结构，就像图书馆里书的分类存放策略或是现代化图书馆里的图书查询系统，能帮助我们快速找到自己需要的书。 数据库中，索引的存储一般使用 B树 或 B+树 来实现，通过二分法来查找法来快速定位到数据位置。 普通索引对于一维数据(key->data)是无往不利，可是面对空间数据(lon,lat -> data)就有些无能为力了，如果查询(116.27636, 40.041285)附近的点： 我们在 lon 或 lat 列上创建普通索引，假设是 lon 列，那么通过 lon 列查找到同一经度的数据后，还要在此基础上...

前言 离职前对做过的支付系统进行了一番#总结，继续完善我的C服务器。 本想着接下来大概实现一下 CGI 协议，但是实现过程中被一个问题卡住了： C进程与php进程的交互数据类型问题： 在 C 进程中我准备将服务器处理后的请求数据存储在一个结构体内，然后将此结构体中的信息传给 PHP，而 PHP 进程内也会有一个全局数组与之对应，可是众所周之，结构体是 C 进程内的内存数据，是无法直接传给 PHP 使用的。 这时候我们也需要一种“协议”来解决进程数据类型的异构性。当然这个解决方案确定起来还是很简单的，无非是对C结构体进行序列化，使用xml，jso...

支付系统的要求：安全、高效。安全是基本，高效是追求。 要达成两个目标，难免会遇到各种坑，下面挑几个典型的问题来讲述，并附上简单的应对方案。 请求超时问题 网络的可靠性要依赖硬件，所以只要是网络调用，必然要考虑超时问题，另外因为支付系统一般内部验证操作多，请求处理时间长，比一般系统超时的概率更大。 支付系统内的每一个请求都应该谨慎处理，而对于无法确定结果的超时请求更不能轻易确定终态，绝对不能像一个简单的网页请求一样重试一次。 一般采取保守策略，将交易状态保持在一个无害的默认状态（处理中或未支付），等待下次触发处理。 请求超时本身易处理，但它导致的后续问题会很多，下面会提到。 终态判断处理问...

业务流程 上文提到由于支付处理的流程复杂性，为了避免因为冗长的流程阻塞降低了处理效率，支付系统中多使用异步机制，将整个支付业务流程拆分为多步处理。支付系统将流程划分为业务受理、支付前置和支付网关、终态获取、结果处理四个大部分，各部分之间以消息队列或系统之间的交互分隔。风控和路由属于支付前置服务，但由于其重要性和复杂性，将它们提出来分别介绍。 下面的图是两种典型的交易时序图： 业务受理 业务受理接口是与商户系统的交互处，主要功能为接受交易业务，响应给商户的是受理结果，而并非交易结果，交易结果会通过异步方式告知商户。 为了考虑接口的安全性，受理接口要依次验证支付请求报文的安全性、商户的权...

前言 做支付一年多了，公司的支付平台刚搭建好进的公司，经历了从一开始的各处漏洞，到代码重构后系统稳定运行，再到功能的逐渐完善和易用性提升，最后到现在追求系统效率的提升，我也从当初对支付一脸懵逼的实习生到成为了解支付的各个方面能顺利解决各种问题的开发工程师，感触颇多。 在做的是一个典型的聚合支付平台，主要跟第三方支付公司（也有银行）交互。 开发语言是 PHP。可能大家印象中，支付作为一个重型业务，应该用 java 这种重型语言来开发。但在小型公司初期业务迅速扩展时期，跟得上业务的发展至关重要，PHP 作为敏捷开发的代表，自然在技术选型上有着很大的优势。可能跟业务量相关，平台目前在一个阿里云...

前言 继续更新“用 C 写一个 web 服务器”项目（上期链接：用C写一个web服务器（一） 基础功能），本次更新选择了 I/O 模型的优化，因为它是服务器的基础，这个先完成的话，后面的优化就可以选择各个模块来进行，不必进行全局化的改动了。 I/O模型 接触过 socket 编程的同学应该都知道一些 I/O 模型的概念，linux 中有阻塞 I/O、非阻塞 I/O、I/O 多路复用、信号驱动 I/O 和 异步 I/O 五种模型。 其他模型的具体概念这里不多介绍，只简单地提一下自己理解的 I/O 多路复用：简单的说就是由一个进程来管理多个 socket，即将多个 s...

前言 C 语言是一门很基础的语言，程序员们对它推崇备至，虽然它是我的入门语言，但大学的 C 语言知道早已经还给了老师，C 的使用可以说是从头学起。 之前一直在读书，看了《C Primer Plus》、《APUE》、《UNP》，第一本看完之后虽然对 C 的语法有了大概的了解，可是要说应用，还差得很远；后两本算是咬着牙翻完的，应用更不敢说，只是对概念有了基本的认识。 我们都知道，学一门语言，只看不写，很容易出现眼高手低，写代码无处下手的情况，于是终于在下班和周末挤出时间，准备写一个小项目。正好最近在看 nginx 服务器与 php sapi 相关的知识，于是考虑以 nginx 的思想，写一个...