微信支付一面（C++后台）

恋喵大鲤鱼

发布于 2020-08-19 15:53:38

1.7K0

发布于 2020-08-19 15:53:38

文章被收录于专栏：C/C++基础C/C++基础

前言

2020-07-05 日晚于深圳滨海大厦参加了公司内部活水转岗微信支付的面试。这里将面试过程中被问及的问题整理一下，温故知新，以备不时之需，也希望能够帮助到正在求职的网友。

Q&A

1.说一下最近工作中自己参与的一个有难度的需求以及实现方案？

从项目谈起，貌似是社招面试绕不开的一个环节。这里面试官主要是想考察自己在项目中遇到的难点以及解决问题的能力。

我遇到的一个需求难点是：高并发高可用服务中对低延时的要求。我参与建设的是一个信息流广告投放系统（流金系统），承接腾讯看点信息流业务，针对不同的信息流平台根据大数据做精细化的流量运营，帮助腾讯看点实现流量变现、商业价值最大化。

需求的背景是品牌广告主对上下文资讯内容的健康度、关键词提出要求进行品牌广告保护，希望上下文资讯内容不出现指定关键词以及涉黄涉恐等级低于指定阈值，如果不满足要求则不出品牌广告。由于业务后台拉取广告与资讯为节省耗时是并发拉取，我们在对品牌广告进行保护时需要知道资讯的健康信息。

这种情况下顺其自然地想到一个实现方法就是让上游（业务后台）在拉取资讯后带上资讯的健康信息再来拉取广告，即并发改串行。但这个方法不可行，因为串行耗时大于端给到业务后台的超时时间，满足低延迟的要求。

既然并发改串行无法满足低延迟的要求，那么从业务层面来考虑有没有什么方法呢。既然业务后台能够拿到资讯健康信息和广告，那么品牌广告的过滤放在业务后台来实现不就顺理成章了吗？业务后台仍为并发拉取资讯&广告，对广告的保护逻辑放在业务后台来实现。但是为了保证混业务后台与广告逻辑解耦，以及流金系统对广告业务的更多控制，这个方案也不可行。

那么有没有一种既能满足低延时的要求，又能把广告保护的逻辑仍放在流金系统来控制呢？实际上是有的。具体的实现方案就是通过二次请求 + 广告缓存。

在的第一次请求时，流金系统拉取品牌广告和候补的普通广告，在下发广告前，把品牌广告和普通广告缓存到本地，回包中打上二次请求标识，告诉业务后台此次请求中有品牌广告，需要进行上下文保护，由业务后台携带上下文发起二次请求。

流金系统在收到业务后台的二次请求时，完成过滤保护逻辑并上报检测结果，如果上下文符合要求，则下发品牌广告，否则下发普通广告。

二次请求的耗时因为是直接从内存中获取广告，耗时极短，大概在 10ms 内，远远小于全链路拉取广告的耗时，满足了低延迟的要求。

2.既然用到了缓存，那么你认为在使用缓存时，一般需要考虑哪些方面的问题？

这个是关于缓存选型的问题，没有最好的缓存组件，只有更适合的缓存组件，所以关于缓存的选择，需要结合具体应用场景，选择一个合适的缓存即可。

缓存的选择，一般需要考虑如下几点：

（1）本地缓存还是分布式缓存；

（2）缓存的淘汰策略；

（3）缓存的读写性能；

（4）是否需要持久化；

（5）缓存所支持的数据结构，比如常用的字符串（string)、链表（list）、集合（set）、有序集合（zset）、哈希表（hash table）。

因为我的应用场景需要的缓存只是使用一次，获取后即可删除，且是缓存本地，所以使用编程语言自带的 map 并根据数据大小和内存大小预估好容量即可，再下次获取后进行删除。当然需要起一个线程，定期清理过期的数据，以防止异常情况下，缓存的数据永远没有被读取而得不到删除。

3.我大致了解了你需求的实现过程，你之前使用过 C++ 吧，那问一下 C++ 语法相关的问题。你知道 const 在 C++ 中有哪些作用吗？

在C ++中，const 实际上有 2 个主要用途。

（1）修饰变量。使变量在其生命周期内不会被更改，比如定义常量、修饰函数参数与函数返回值；

// 定义常量
const int a = 1;

// 修饰函数参数
void PrintStudent(const Student& student) {
  cout << student.GetName();
}

// 修饰函数返回值
const int& disp5(int& ri) {
	cout<<ri<<endl;
	return ri;
}

（2）修饰函数。const 可以成员方法使其成为常函数而无法改变对象，并与同名的普通成员方法形成重载。

class Student {
  public:
    string GetName() const { ... }
};

4.你使用过 map 吧，你知道 map 的实现原理是什么吗？

map 经常使用，C++ 中的 map 是通过红黑树来实现的。

5.既然 map 是使用红黑树实现的，你知道红黑树的是如何自平衡的吗？

红黑树的原理好久没有温故了，戳中了知识盲点。这里不禁让我想起微软中国一个招聘官曾在校园宣讲会 Q&A 环节说到，虽然手写代码一般不需要实现一个红黑树，但是红黑树的原理必须要清楚。

红黑树（Red Black Tree）是一种含有红黑结点并能自平衡二叉查找树，典型的用途是实现 map。

它必须满足下面规则：

规则1：每个结点要么是黑色，要么是红色。
规则2：根结点是黑色。
规则3：每个叶子结点（NIL）是黑色。
规则4：每个红色结点的两个子结点都是黑色。
规则5：任意一结点到每个叶子结点的路径都包含相同数量的黑结点。

记住上面的规则也不难，我们会发现黑色结点非常特殊，规则1即“非红即黑”，规则2和3即“首尾全黑”，规则4即“红子双黑”，规则5即“路径等黑”。

这些规则强制约束红黑树，使得红黑树具有如下关键特性:

（1）从根到叶子的最长路径不大于最短路径的两倍，所以红黑树大致上是平衡的。

从规则5中，我们知道从根结点到每个叶子结点的黑色结点数量是一样的，那么纯由黑色结点组成的路径就是最短路径；

规则4表明路径上不能有两个连续的红色结点，除了根结点和叶子结点，当红色结点和黑色结点交替出现数量相同时，即位最长路径。

（2）加入到红黑树中的结点为红色结点。

从规则4中知道，当前红黑树中从根结点到每个叶子结点的黑色结点数量是一样的，此时假如新的黑色结点的话，必然破坏规则，但加入红色结点却不一定，除非其父结点就是红色结点，因此加入红色结点，破坏规则的可能性小一些。

下面是一个红黑树示例：

再了解红黑树的基本性质后，红黑树是如何实现自平衡的呢？红黑树总是通过旋转和变色达到自平衡。

关于红黑树的自平衡、查找、插入和删除，详见图解红黑树。

6.对 HTTP 协议了解吧，问几个 HTTP 的问题。你知道 HTTP 中 GET 和 POST 的区别吗？

HTTP 协议是后台开发必须要了解的协议，因为在后台开发工作中，少不了使用 HTTP 协议进行交互，比如访问 HTTP 服务获取数据或者实现一个 HTTP 服务。当然，HTTP 协议是不仅仅是后台开发需要了解，只要是开发人员都必须要了解。

HTTP 定义了与服务器交互的不同方法，最基本的方法有4种，分别是 GET，POST，PUT，DELETE。URL 全称是资源描述符，我们可以这样认为：一个 URL 地址，它用于描述一个网络上的资源，而 HTTP 中的 GET，POST，PUT，DELETE 就对应着对这个资源的查，改，增，删4个操作。到这里，大家应该有个大概的了解了，GET 一般用于获取/查询资源信息，而 POST 一般用于更新资源信息。

在谈论 HTTP GET 和 POST 的区别时，我们不能脱离其使用分场景，就像我们在做阅读理解时要想了解某个句子的具体含义，不能脱离语境。下面就分场景说一下 GET 和 POST 的区别。

浏览器的 GET 和 POST 的区别：

（1）作用不同。GET 用于获取资源，POST 用于更新资源；

（2）携带数据的方式不同。GET 一般将数据已参数的形式放到 URL 中，虽然 HTTP 标准并未对 URL 长度做限制，但是浏览器在实现时，一般会对 URL 的长度做限制，所以携带的数据有限；POST 将数据放到 Body 中，无长度限制；

（3）安全性不同。GET 比 POST 更不安全，因为参数直接暴露在 URL 上，所以不能用来传递敏感信息；

（4）幂等性不同。GET 对访问的数据没有副作用，具有幂等性。POST 用于更新操作往往是有副作用的，不幂等。因为幂等性的差别，GET 产生的 URL 地址可以保存为书签，而 POST 不可以。GET 请求会被浏览器主动 cache，而 POST 不会，除非手动设置。

RPC 接口中的 GET 和 POST 的区别：

在后台 RPC 接口调用中，我们可以利用 HTTP 协议进行通信，此时 GET/POST 不光能用在前端和后端的交互中，还能用在后端各个子服务的调用中。当用HTTP实现接口发送请求时，就没有浏览器中那么多限制了，只要是符合 HTTP 格式的就可以发送。

所以该应用场景下，GET 与 POST 除了语义上区别，在作用上并无区别，GET 可以使用 body 协议数据用于更新远端资源，POST 也可以把数据放到 URL 参数中用于获取远端资源，这完全取决于被调接口的具体实现。

7.网络安全中 XSS 漏洞你知道是如何防护的吗？

面试被问及网络安全，虽然不是搞安全的，但是并不意外，因为安全问题无处不在，虽然不是从事安全工作，但是常见的安全知识还是需要知道的。

简介

XSS 漏洞是 Web 安全中最为常见的漏洞，通常指的是通过利用网页开发时留下的漏洞，通过巧妙的方法注入恶意指令代码到网页，使用户加载并执行攻击者恶意制造的网页程序。这些恶意网页程序通常是 JavaScript，但实际上也可以包括 Java、 VBScript、ActiveX、 Flash 或者甚至是普通的HTML。攻击成功后，攻击者可能得到包括但不限于更高的权限（如执行一些操作）、私密网页内容、会话和 cookie 等各种内容。

XSS（Cross Site Scripting）名为跨站脚本攻击，因其缩写会与层叠样式表（Cascading Style Sheets，CSS）的缩写混淆，故将其缩写为 XSS。

XSS本质是HTML注入。

分类

从攻击代码的工作方式可以分为三个类型：

（1）存储型XSS：危害直接。跨站代码存储在服务器，如在个人信息或发表文章的地方加入代码，如果没有过滤或过滤不严，那么这些代码将储存到服务器中，每当有用户访问该页面的时候都会触发代码执行；

（2）反射型XSS：最为普遍。反射型跨站脚本漏洞，需要欺骗用户自己去点击链接才能触发XSS代码，一般容易出现在搜索页面；

（3）DOM型XSS：相对较少。DOM（document object model文档对象模型），客户端脚本处理逻辑导致的安全问题。基于DOM的XSS漏洞是指受害者端的网页脚本在修改本地页面DOM环境时未进行合理的处置，而使得攻击脚本被执行。

目的

常见的 XSS 攻击手段和目的有：

（1）盗用cookie，获取敏感信息。

（2）利用植入Flash，通过crossdomain权限设置进一步获取更高权限；或者利用Java等得到类似的操作。

（3）利用iframe、frame、XMLHttpRequest或上述Flash等方式，以（被攻击）用户的身份执行一些管理动作，或执行一些一般的如发微博、加好友、发私信等操作。

（4）利用可被攻击的域受到其他域信任的特点，以受信任来源的身份请求一些平时不允许的操作，如进行不当的投票活动。

（5）在访问量极大的一些页面上的XSS可以攻击一些小型网站，实现DDoS攻击的效果。

防御

XSS攻击主要是由程序漏洞造成的，要完全防止XSS安全漏洞主要依靠程序员较高的编程能力和安全意识，当然安全的软件开发流程及其他一些编程安全原则也可以大大减少XSS安全漏洞的发生。这些防范XSS漏洞原则包括：

（1）不信任用户提交的任何内容，对所有用户提交内容进行可靠的输入验证和，包括对URL、查询关键字、HTTP头、REFER、POST数据等，仅接受指定长度范围内、采用适当格式、采用所预期的字符的内容提交，对其他的一律过滤；

（2）实现 Session 标记、验证码系统或者HTTP引用头检查，以防功能被第三方网站所执行；

（3）cookie 防盗。避免直接在cookie中泄露用户隐私，例如email、密码，等等；通过使cookie和系统IP绑定来降低cookie泄露后的危险。这样攻击者得到的cookie没有实际价值，很难拿来直接进行重放攻击；

（4）如果Web应用必须支持用户提供的HTML，那么必须确认接收的内容被妥善地规范化，仅包含最小的、安全的Tag（没有JavaScript），去掉任何对远程内容的引用（尤其是样式表和JavaScript），使用HTTPonly的cookie。

8.网络安全中 CSRF 漏洞又是如何防护的呢？

简介

CSRF（Cross Site Request Forgery）名为跨站请求伪造，是一种挟制用户在当前已登录的Web应用程序上执行非本意的操作的攻击方法。

攻击者盗用了你的身份，以你的名义发送恶意请求，对服务器来说这个请求是完全合法的，但是却完成了攻击者所期望的一个操作，比如以你的名义发送邮件、发消息，盗取你的账号，添加系统管理员，甚至于购买商品、虚拟货币转账等。

示例

假如一家银行用以运行转账操作的URL地址如下：

https://www.examplebank.com/withdraw?account=AccoutName&amount=1000&for=PayeeName

那么，一个恶意攻击者可以在另一个网站上放置如下代码：

<img src="https://www.examplebank.com/withdraw?account=Alice&amount=1000&for=Badman">

如果有账户名为 Alice 的用户访问了恶意站点，当图片被加载时，图片链接将被触发，而她之前刚访问过银行不久，登录信息尚未过期，那么她就会损失 1000 资金。

这种恶意的网址可以有很多种形式，藏身于网页中的许多地方。此外，攻击者也不需要控制放置恶意网址的网站。例如他可以将这种地址藏在论坛，博客等任何用户生成内容的网站中。这意味着如果服务端没有合适的防御措施的话，用户即使访问熟悉的可信网站也有受攻击的危险。

透过例子能够看出，攻击者并不能通过CSRF攻击来直接获取用户的账户控制权，也不能直接窃取用户的任何信息。他们能做到的，是欺骗用户浏览器，让其以用户的名义运行操作。

防御措施

目前防御 CSRF 攻击主要有三种策略：

（1）验证 HTTP Referer 字段；

根据 HTTP 协议，在 HTTP 头中有一个字段叫 Referer，它记录了该 HTTP 请求的来源地址。在通常情况下，访问一个安全受限页面的请求来自于同一个网站在请求地址中添加 token 并验证；在 HTTP 头中自定义属性并验证。

以上文银行操作为例，Referer字段地址通常应该是转账按钮所在的网页地址，应该也位于www.examplebank.com之下。而如果是CSRF攻击传来的请求，Referer字段会是包含恶意网址的地址，不会位于www.examplebank.com之下，这时候服务器就能识别出恶意的访问。

这种办法简单易行，工作量低，仅需要在关键访问处增加一步校验。但这种办法也有其局限性，因其完全依赖浏览器发送正确的Referer字段。虽然http协议对此字段的内容有明确的规定，但并无法保证来访的浏览器的具体实现，亦无法保证浏览器没有安全漏洞影响到此字段。并且也存在攻击者攻击某些浏览器，篡改其Referer字段的可能。

（2）添加校验token。

CSRF 攻击之所以能够成功，是因为黑客可以完全伪造用户的请求，该请求中所有的用户验证信息都是存在于 cookie 中，因此黑客可以在不知道这些验证信息的情况下直接利用用户自己的 cookie 来通过安全验证。要抵御 CSRF，关键在于在请求中放入黑客所不能伪造的信息，并且该信息不存在于 cookie 之中。可以在 HTTP 请求中以参数的形式加入一个随机产生的 token，并在服务器端建立一个拦截器来验证这个 token，如果请求中没有 token 或者 token 内容不正确，则认为可能是 CSRF 攻击而拒绝该请求。

（3）在 HTTP 头中自定义属性并验证。

这种方法也是使用 token 并进行验证，和上一种方法不同的是，这里并不是把 token 以参数的形式置于 HTTP 请求之中，而是把它放到 HTTP 头中自定义的属性里。通过 XMLHttpRequest 这个类，可以一次性给所有该类请求加上 csrftoken 这个 HTTP 头属性，并把 token 值放入其中。这样解决了上种方法在请求中加入 token 的不便，同时，通过 XMLHttpRequest 请求的地址不会被记录到浏览器的地址栏，也不用担心 token 会透过 Referer 泄露到其他网站中去。

然而这种方法的局限性非常大。XMLHttpRequest 请求通常用于 Ajax 方法中对于页面局部的异步刷新，并非所有的请求都适合用这个类来发起，而且通过该类请求得到的页面不能被浏览器所记录下，从而进行前进，后退，刷新，收藏等操作，给用户带来不便。另外，对于没有进行 CSRF 防护的遗留系统来说，要采用这种方法来进行防护，要把所有请求都改为 XMLHttpRequest 请求，这样几乎是要重写整个网站，这代价无疑是不能接受的。

CSRF 与 XSS 的区别？

（1）XSS本质是HTML注入，和 SQL 注入差不多，而 CSRF 则是冒充用户发起非法请求；

（2）CSRF 需要用户登录后完成攻击，XSS 不需要。

9.使用过 DB 吧，你知道 MySQL 锁机制是怎样的吗？

锁，在现实生活中是为我们想要隐藏于外界所使用的一种工具。在计算机中，是协调多个进程或线程并发访问某一资源的一种机制。在数据库当中，除了传统的计算资源（CPU、RAM、I/O等等）的争用之外，数据也是一种供许多用户共享访问的资源。如何保证数据并发访问的一致性、有效性，是所有数据库必须解决的一个问题，锁的冲突也是影响数据库并发访问性能的一个重要因素。从这一角度来说，锁对于数据库而言就显得尤为重要。

MySQL 在不同的应用场景拥有多种锁，分为如下几类：

（1）按照锁的粒度划分：行锁、表锁、页锁；

（2）按照锁的使用方式划分：共享锁、排它锁（悲观锁的一种实现）；

（3）还有两种思想上的锁：悲观锁、乐观锁。

默认情况下，表锁和行锁都是自动获得的，不需要额外的命令。

行锁

行级锁是Mysql中锁定粒度最细的一种锁，表示只针对当前操作的行进行加锁。行级锁能大大减少数据库操作的冲突。其加锁粒度最小，但加锁的开销也最大。有可能会出现死锁的情况。行级锁按照使用方式分为共享锁和排他锁。

（1）共享锁（S锁、读锁）：

若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A。在T释放A上的S锁之前，其他事务只能再对A加S锁，而不能加X锁，这保证了其他事务可以读A，但不能更新A。

select ... lock in share mode;

（2）排它锁（X锁、写锁）：

若事务T对数据对象A加上X锁，事务T可以读A也可以修改A。在T释放A上的锁之前，其他事务不能再对A加任何锁，这保证了其他事务不能再读取和修改A。

select ... for update

表锁

表级锁是 MySql 锁中粒度最大的一种锁，表示当前的操作对整张表加锁，资源开销比行锁少，不会出现死锁的情况，但是发生锁冲突的概率很大。被大部分的 MySql 引擎支持，MyISAM 和 InnoDB 都支持表级锁，但是 InnoDB 默认的是行级锁。

共享锁用法：

LOCK TABLE table_name [ AS alias_name ] READ;

排它锁用法：

LOCK TABLE table_name [AS alias_name][ LOW_PRIORITY ] WRITE;

解锁用法：

unlock tables;

页锁

页级锁是MySQL中锁定粒度介于行级锁和表级锁中间的一种锁。表级锁速度快，但冲突多，行级冲突少，但速度慢。所以取了折衷的页级，一次锁定相邻的一组记录。存储引擎 BDB 支持页级锁。（注：BDB 已经被 InnoDB 所取代）。

乐观锁和悲观锁

乐观锁（乐观并发控制)和悲观锁（并发控制）是控制并发采用的主要采用技术手段。

悲观锁，正如其名，它指的是对数据被外界修改持保守态度（悲观），因此，在整个数据处理过程中，将数据处于锁定状态。悲观锁的实现，往往依靠数据库提供的锁机制，也只有数据库层提供的锁机制才能真正保证数据访问的排他性，否则，即使在本系统中实现了加锁机制，也无法保证外部系统不会修改数据。

乐观锁相对悲观锁而言，乐观锁假设认为数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突与否进行检测，如果发现冲突了，则让返回用户错误的信息，让用户决定如何去做。相对于悲观锁，在对数据库进行处理的时候，乐观锁并不会使用数据库提供的锁机制。一般的实现乐观锁的方式就是记录数据版本。

无论是悲观锁还是乐观锁，都是人们定义出来的概念，可以认为是一种思想。其实不仅仅是关系型数据库系统中有乐观锁和悲观锁的概念，像 redis、memcache、hibernate、tair等 NoSQl 数据库都有类似的概念。

针对于不同的业务场景，应该选用不同的并发控制方式。所以，不要把乐观并发控制和悲观并发控制狭义的理解为 DBMS 中的概念，更不要把他们和数据中提供的锁机制（行锁、表锁、排他锁、共享锁）混为一谈。其实，在 DBMS 中，悲观锁正是利用数据库本身提供的锁机制来实现的。

悲观锁的优点和不足：

悲观锁实际上是采取了“先取锁在访问”的策略，为数据的处理安全提供了保证，但是在效率方面，由于额外的加锁机制产生了额外的开销，并且增加了死锁的机会和降低了并发性；

乐观锁的优点和不足：

乐观并发控制相信事务之间的数据竞争的概率是比较小的，因此尽可能直接做下去，直到提交的时候才去锁定，所以不会产生任何锁和死锁。但如果直接简单这么做，还是有可能会遇到不可预期的结果，例如两个事务都读取了数据库的某一行，经过修改以后写回数据库，这时就产生了冲突。

InnoDB 的三种锁

（1）记录锁（Record Lock）

单条索引上加锁，记录锁永远锁的是索引，而非数据本身，如果innodb表中没有索引，那么会自动创建一个隐藏的聚集索引，锁住的就是这个聚集索引。所以说当一条sql没有走任何索引时，那么将会在每一条聚集索引后面加X锁，这个类似于表锁，但原理上和表锁应该是完全不同的。

（2）间隙锁（Gap Lock）

间隙锁是在索引的间隙之间加上锁。

编程的思想源于生活，生活中的例子能帮助我们更好的理解一些编程中的思想。

生活中排队的场景，小明，小红，小花三个人依次站成一排，此时，如何让新来的小刚不能站在小红旁边，这时候只要将小红和她前面的小明之间的空隙封锁，将小红和她后面的小花之间的空隙封锁，那么小刚就不能站到小红的旁边。

这里的小红，小明，小花，小刚就是数据库的一条条记录。他们之间的空隙也就是间隙，而封锁他们之间距离的锁，叫做间隙锁。

间隙锁锁定的区域：

根据检索条件向左寻找最靠近检索条件的记录值 A 作为左区间，向右寻找最靠近检索条件的记录值 B 作为右区间，即锁定的间隙为闭区间A,B。

间隙锁的目的是为了防止幻读，其主要通过两个方面实现这个目的：

（a）防止间隙内有新数据被插入；

（b）防止已存在的数据，更新成间隙内的数据。

解决幻读的方式很简单，就是需要当事务进行当前读的时候，保证其他事务不可以在满足当前读条件的范围内进行数据操作。

InnoDB 自动使用间隙锁的条件：

（a）事务隔离级别必须在 RR 级别下；

（b）检索条件必须有索引（没有索引的话，MySQL 会全表扫描，那样会锁定整张表所有的记录，包括不存在的记录，此时其他事务不能修改不能删除不能添加）。

（c）使用普通索引或多列唯一索引；

注意：对于使用唯一索引来搜索并给某一行记录加锁的语句，不会产生间隙锁。例如，如果 id 列具有唯一索引，则下面的语句仅对具有id值100的行使用记录锁，并不会产生间隙锁：

SELECT * FROM child WHERE id = 100 FOR UPDATE;

（3）临键锁（Next-key lock）

临键锁，是记录锁与间隙锁的组合，它的封锁范围，既包含索引记录，又包含索引区间。InnoDB 默认加锁方式是临键锁。

注：临键锁的主要目的，也是为了避免幻读。如果把事务的隔离级别降级为 RC，临键锁也会失效。

死锁

MyISAM 是不会产生死锁的，因为 MyISAM 总是一次性获得所需的全部锁，要么全部满足，要么全部等待。而在 InnoDB 中，锁是逐步获得的，就造成了死锁的可能。

在 InnoDB 中，行级锁并不是直接锁记录，而是锁索引。索引分为主键索引和非主键索引两种，如果一条 sql 语句操作了主键索引，MySQL 就会锁定这条主键索引；如果一条语句操作了非主键索引，MySQL 会先锁定该非主键索引，再锁定相关的主键索引。

当两个事务同时执行，一个锁住了主键索引，在等待其他相关索引。另一个锁定了非主键索引，在等待主键索引。这样就会发生死锁。

避免死锁，这里只介绍常见的三种

（1）如果不同程序会并发存取多个表，尽量约定以相同的顺序访问表，可以大大降低死锁机会；

（2）在同一个事务中，尽可能做到一次锁定所需要的所有资源，减少死锁产生概率；

（3）对于非常容易产生死锁的业务部分，可以尝试使用升级锁定颗粒度，通过表级锁定来减少死锁产生的概率。

10.使用过设计模式吧，你最常用的是哪种设计模式？

设计模式（Design Pattern）是一套被反复使用、多数人知晓、分类编目、代码设计经验的总结。使用设计模式是为了提高代码的可复用性、可扩充性可维护性，让代码易于被他人理解且保证软件的可靠性。毫无疑问，我们在平时的开工工作中，多少都会用到设计模式。

这些设计模式被分为三大类：创建型、结构型和行为型，分别包括内容如下：

创建型模式5个：单例模式（Singleton）、抽象工厂模式（Abstract Factory）、建造者模式（Builder）、工厂模式（Factory）、原型模式（Prototype）。

结构型模式7个：适配器模式（Adapter）、桥接模式（Bridge）、装饰模式（Decorator）、组合模式（Composite）、外观模式（Facade）、享元模式（Flyweight）、代理模式（Proxy）。

行为型模式11个：模版方法模式（Template Method）、命令模式（Command）、迭代器模式（Iterator）、观察者模式（Observer）、中介者模式（Mediator）、备忘录模式（Memento）、解释器模式（Interpreter）、状态模式（State）、策略模式（Strategy）、责任链模式（Chain of Responsibility）、访问者模式（Visitor）。

事实上，除了GoF的23个著名设计模式之外，还有很多别的设计模式，Wrapper 模式、DAO（Data Access Object）模式、MVC（Model-View-Control）模式等。设计模式的学习是一个艰苦漫长的过程，需要大量的实践、思考和总结，即便如此，我们首先要有这个学习的意识。

下面以最为常用的单例模式为例，以 Golang 演示线程安全的单例创建方法。

var (
	ins  *Singleton
	once sync.Once
)

type Singleton struct{}

func GetIns() *Singleton {
	once.Do(func() {
		ins = &Singleton{}
	})
	return ins
}

11.问几个算法的问题。简单介绍一下快速排序的实现思想。

常见排序算法必须烂熟于心，尤其是使用了分治思想的快速排序。快排也经常被作为手写代码的算法题。

快速排序又称分区交换排序，属交换类排序，是对冒泡排序的改进，快速排序采用的思想是交换+分治。

算法原理：

（1）从待排序的 n 个记录中任意选取一个记录（通常选取第一个记录）为分界值；

（2）把所有小于分界值的记录移动到左边，把所有大于分界值的记录移动到右边，中间空地位置填分界值，称之为第一趟排序；

（3）然后对前后两个子序列分别重复上述过程，直到所有记录都排好序。

稳定性：不稳定排序。

时间复杂度：O(nlog2n) 至 O(n2)，平均 O(nlgn)。

12.给你一个文件，文件中存有10亿+个整型数值，每行一个，如果需要对其进行递增去重排序，该如何实现呢？

待排序元素数量过大，一次性无法载入内存进行排序，这种情况应该想到使用分而治之的思想。

实现思路：