ITeye博客

murray2081的博客

murray2081 · 共 28 篇文章

语句倒装和语音图像压缩的科学原理

今天吴军老师讲了一道简单谷歌面试题, 把语句倒装和语音图像压缩的科学原理结合 了起来,很有启发。 面试题目是说“如何不使用额外的存储空间完成语句倒装?”,例如要把“London bridge is falling down”倒装成“down falling is bridge London”,这道题的难度在于不使用“额外的存储空间”,而 最大思维陷阱在于人会陷入自己固有的思维方式 ,或者说常人的思维。 这道题最简单的做法如下: 第一步、先将整个句子看成是一个完整的字符串,以字母为单位头尾对调。 第二步、把用空格分割的每一个字串以字母为单位,头尾对调。 很多人想不到先要把整个句子变得无意义,才…

2018-06-20 19:57 · 评论(0)

如何设计一个地图功能,找到当前最近的加油站?

吴军老师的《硅谷来信》中的第080封信,讲了一道Google面试题。 题目如标题,主要考察两方面: 1、考察计算机科学的基本知识 2、看候选人分解问题、解决问题的能力 首先处理一个问题要先全面了解问题,否则答非所问或者没有体会出题人的考察点。我刚开始思考这道题,忽略掉了有点个关键点: 1、汽车是移动的,结果会不断更新,计算速度不能很慢。 **2、这个产品不同的使用场景,对准确度接受度是不同的。**如果两个加油站差200米,司机和行人对200米感受是不一样的。 **3、汽车是有方向且移动的。**汽车位置只有GPS定位,需要转换成街道地址的范围等。 **4、距离的计算。**在现实中两点之间的距离…

2018-04-19 12:57 · 算法 · 评论(0)

锦标赛排序算法

今天听了吴军老师的《硅谷来信》中的第079封信,了解到了锦标赛算法。 首先锦标赛排序又叫树型选择排序,也是用二叉树这种数据结构。这种排序方法比快速排序快,主要是在N个选手中选出K个选手中有优势。这封信中说了一道高盛面试题,即如何从25个选手中决出前三名,就使用了这种算法。 这封来信中讲解的方式和标准的锦标赛排序算法不太一样( 标准的锦标赛排序算法见文末链接 ),共分三大步: **第一步:**25个选手分成5组,A1~A5,B1~B5,C1~C5,D1~D5,D1~D5,进行5次比赛,结束后5组内部排名就决出了。 **第二步:**5组中第一名进行第6次比赛,决出第一名。 **第三步:**剩下的…

2018-04-11 22:55 · 算法 · 评论(0)

同程凤凰缓存系统基于Redis的设计与实践(转)

本文摘自《深入分布式缓存》,此文中提到的同程在使用Redis过程中踩过的坑,非常真实也很有借鉴性,读文有感Mark如下: 1、Redis主从+Keepalived方案,存在的问题! 这本来是个很好的方案,但是忽略了主数据节点挂掉的情况。Redis的单进程、单线程设计是其简单和稳定的基石,只要不是服务器发生了故障,在一般情况下是不会挂的。但同时,单进程、单线程的设计会导致Redis接收到复杂指令时会忙于计算而停止响应,可能就因为一个zset或者keys之类的指令, Redis计算时间稍长,Keepalived就认为其停止了响应,直接更改虚IP的指向,然后做一次主从切换 。过不了多久,zset和…

2017-12-28 21:15 · redis · 评论(0)

限流功能设计

很早以前做过一个限流的功能,设计地很ugly。今天看到Log4j2的限流过滤器设计的非常好,花了一些时间研究感觉很不错,以后可能还会再用,总结一下吧。 首先我们要先聊一下限流功能主要是做什么?其实就是限制某种操作在某段时间内,限制做多少次。 Log4j2的使用了一个 DelayQueue 和一个 ConcurrentLinkedQueue 开发了一个过滤器(burstFilter)比较优雅解决了这个问题。 整体架构如下: 设计核心逻辑如下: burstFilter初始化辑如下:

2017-12-15 19:30 · log4j2 · DelayQueue · 评论(0)

kafka主题消费积压问题总结

故障描述: 12月6日下午运维反馈说,某个主题的一个分区消费积压,由于这个主题非常重要,且已经有用户投诉所以运维很紧张,紧急打印堆栈并Dump堆内存后,就重启了这台机器。 故障分析1: 消费这个主题的集群的业务逻辑相对比较简单,主要就是读取某些主题,然后逻辑判断+DB操作后,分流写入到另外某些主题。运维通过kafka监控平台找到积压的主题,发现主题的某个分区积压了几万消息后,找到了消费这个分区的应用程序结点。 故障分析2: 通过对结点堆栈信息分析并未看出什么问题,又通过MAT(Eclipse Memory Analyzer)打开堆Dump文件,通过积压主题名称找到所有和此主题相关的线程,发现…

2017-12-09 23:43 · kafka · mysql · 评论(0)

httpclient连接池相关参数的坑

今天早上UIOC,现象是发现调用某个服务的接口总是超时,这个环境昨晚没有发版本无缘无故就出问题很是奇怪。到公司各种查,最终通过问题服务重启前打印的堆栈信息看到几乎所有的线程都在等待连接池释放连接后获取空闲连接。错误如下: "xxxxxxxxxxxxx" prio=10 tid=0x00007f6b7c002800 nid=0x40ff waiting on condition [0x00007f6b37020000] java.lang.Thread.State: TIMED_WAITING (parking) at sun.misc.Unsafe.park(Native Method) -…

2017-07-28 22:59 · httpclient · 评论(0)

关于dubbox部分rest接口超时问题研究

业务高峰期部分rest接口超时有一段时间了,之前一直怀疑是kafka、nginx、log4j、网络等原因并进行优化,一直没有太大改观。我们生产共有四台nginx反向代理网关,运维在某台nginx中通过日志grep看到,高峰期 nginx反向代理到后端某台tomcat,每秒达到100+,4台nginx则为400+,已超过tomcat设置的并发连接数和完全连接队列的大小(200+100=300)。前两天运维说把tomcat线程数调大到600之后(原来是200),超时问题就没有再出现了。 事后考虑原因分析如下: tomcat配置中有一个参数叫acceptCount,这个参数在tomcat中指ser…

2017-07-28 00:32 · TCP/IP · tomcat · 评论(0)

非阻塞I/O及epoll理解新方式?

阻塞I/O与非阻塞忙轮询I/O的缺点 阻塞I/O:一个线程只能处理一个流的I/O事件。如果想要同时处理多个流,要么多进程(fork),要么多线程(pthread_create)。 非阻塞忙轮询I/O:循环轮询所有流,没有I/O时CPU空转。 以上两种方式缺点很明显,阻塞I/O一个线程(或进程)处理一个流不适合高并发和大量长连接场景,非阻塞忙轮询I/O的主要问题需要主动轮询流的状态,无I/O时CPU空转。 非阻塞I/O及epoll理解新****方式 非阻塞I/O可以理解为引入一个代理**(select、poll、epoll等)**,这个代理比较厉害,可以同时观察许多流的I/O事件,在空闲的时候…

2017-01-18 18:14 · epoll 非阻塞I/O · 评论(0)

OpenResty?ngx_lua?Nginx与ngx_lua结合?

什么是OpenResty? 将Lua和Nginx粘合ngx_lua模块,并且将Nginx核心、LuaJIT、ngx_lua模块、许多有用的Lua库和常用的第三方Nginx模块组合而成。 什么是ngx_lua及原理? ngx_lua是Nginx的一个模块,将Lua嵌入到Nginx中,从而可以使用Lua来编写脚本,这样就可以使用Lua编写应用脚本,部署到Nginx中运行,即Nginx变成了一个Web容器。 注:Tengine也包含ngx_lua模块。至于二者的区别:OpenResty是Nginx的Bundle;而Tengine则是Nginx的Fork。 ngx_lua模块的原理: 1、每个wor…

2017-01-18 17:04 · nginx openresty · 评论(0)

Mysql复合索引的坑!!!

问题发生! 上周五公司年会,一早运维电话说UIOC,IMS应用的CPU持续飙高,立马启动UIOC。迅速赶到公司情况属实,各种查最终发现DB并发连接数超高,DB负载超高,kafka积压严重,并且持续时间已经有一两个小时了。 解决方案第一波! 查看IMS应用线程堆栈(ThreadDump)信息发现200个运行线程有167个都在做同一个操作,这个操作是每个用户登录时都要加载自己当天所有的任务并缓存到redis,加载自己所有任务的mysql语句基本如下: select * from A left outer join B on A.taskid=B.taskid where A.resourceid…

2017-01-11 23:21 · mysql 复合索引 · 评论(0)

TCP分段和IP分片

主要讲TCP/IP协议中传输层的分段和网络层的分片 **1、**TCP分段是指在经三次握手后,收发双方建立起连接通过后,双方已经协商好并确定彼此要采用的MSS(最大分段长度B),MSS一般都是按照接受方确定。然后把用户数据payload按照MSS大小进行分段,各个分段数据被逐一添加TCP报头后(20B),送给下一层网络层。 **2、**网络层接收到这些分段后,在添加端主要的IP报头前,按照主机所在的局域网链路层MTU(最大传输单元B),进行分片,即当TCP分段大小超过该局域网链路上的MTU的大小才会发生,并在分片后在每个IP分片前添加IP报头20字节。 注:为了避免频繁IP层分片,一般MTU…

2016-03-31 09:39 · TCP/IP · 评论(0)

深入浅出协程(Coroutine)

目录: 1、协程是什么 2、协程新思路 3、协程与GreenThread 4、协和调度器实现策略 1、协程是什么? (1)线程 每一个线程都代表一个执行序列。当我们在程序中创建多线程的时候,看起来,同一时刻多个线程是同时执行的,不过实质上多个线程是并发的,因为只有一个CPU,所以实质上同一个时刻只有一个线程在执行。在一个时间片内执行哪个线程是不确定的,我们可以控制线程的优先级,不过真正的线程调度由CPU的调度决定。 (2)协程 协程跟线程都代表一个执行序列。不同的是,协程把线程中不确定的地方尽可能的去掉,执行序列间的切换不再由CPU隐藏的进行,而是由程序显式的进行。 所以,使用协程实现并发,…

2016-03-29 09:45 · nginx openresty · 评论(0)

性能测试发现“redis cannot assign requested address”问题

**场景描述:**test_client(jmeter) -> nginx -> redis **问题表现:**nginx频繁报错redis cannot assign requested address,查看nginx网络连接情况,发现有大量TIME_WAIT的连接,并且test_client的tps上不去。大量的TIME_WAIT状态使得local port在TIME_WAIT持续期间不能被再次分配,即没有可用的local port,最终导致新建连接失败。 问题分析一: 大量TIME_WAIT出现的主要原因是nginx频繁与服务端建立tcp短连接后,又主动关闭tcp连接引起的。我们使用的…

2016-03-17 17:14 · nginx openresty · 评论(0)

Java线程结束/中断退出

SelectorManager包含Reactor(extends Thread)数组,要停止SelectorManager所以要先停掉各个Reactor,查看代码如下: public synchronized void stop() { if (!started) { return; } started = false; for (Reactor reactor : reactorSet) { reactor.interrupt(); }} 为什么要使用reactor.interrupt()呢?查看Reactor.run()如下代码: public void run() { selector…

2015-08-19 14:17 · 评论(0)