题目： Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation. Example 1: Input: ["2", "1", "+", "3", "*"] Output: ...
Timing Measurement Linux 内核的Timer必须要完成两种定时测量（timing measurement） 保存当前的日期时间 维护定时器（Timer） 保存当前时间提供给相关系统调用time(), ftime(),gettimeofday(),以便他们将日期时间返回给用户程序；维护定时器提醒内核某一段时间已经过去。要实现以上定时测量就离不开相关硬件的支持，下面看下X86体系下相关时钟和定时电路有哪些。 时钟和定时电路 下面仅列出X86体系结构下常见的时间相关硬件定时器、时钟。 RTC ：Real Time Clock 实时时钟， 依靠电池供电，集成在CMOS芯片上（结合NVRAM和RTC），可以得到日期和时间 TSC ：Time Stamp Counter 80x86处理器通过CLK引线，接收外部时钟信号，从Pentium开始 80x86处理器提供了一个TSC寄存器， 收到时钟信号后加一。可以通过rtdsc指令获取该值。因此TSC可以做为时钟设备。 PIT ：Programmable Interval Timer 又被称作8253/8254芯片， 这种设备不是通过振铃而是通过发出一种特殊中断，时钟中断通知内核一个时间间隔又过去了。时钟频率大约1.193182 MHz CPU Local APIC Timer： APIC timer 由于是CPU内部的振荡器所有避免了资源抢占，APIC timer分为三种模式： Periodic Mode（周期模式），One-Shot Mode（一次性模式），TSC-Deadline Mode（Deadline模式） HPET： High Precision Event Timer 是Intel和Microsoft设计的硬件，用于替换PIT，RTC, 提供更高的频率， 包含一个64位的主计数器和3到32个32位或64位的比较器。工作模式分为： eriodic Mode（周期模式），One-Shot Mode（一次性模式） ACPI PMT: ACPI Power Management Timer 在所有基于 ACPI 的主板， 频率为 3.579545 MHz 关于 Timer Interrupt Sources 的比较 ...
问题： 本周在配合系统测试过程中，发现系统报文接收异常， 排查过程中发现应用进程启动异常。 当时状态模拟如下： [root@centosgpt server]# ps -ef|grep daemon dbus 934 1 0 Jul22 ? 00:01:15 /usr/bin/dbus-daemon --system --address=systemd: --nofork --nopidfile --systemd-activation root 941 1 0 Jul22 ? 00:00:15 /usr/sbin/NetworkManager --no-daemon root 81345 1 0 09:27 ? 00:00:00 daemon root 81348 1 0 09:27 ? 00:00:00 daemon root 81351 1 0 09:27 ? 00:00:00 daemon root 81354 1 0 09:27 ? 00:00:00 daemon root 81357 1 0 09:28 ? 00:00:00 daemon root 81360 1 0 09:28 ? 00:00:00 daemon status root 81364 1 0 09:28 ? 00:00:00 daemon start root 81367 1 0 09:28 ? 00:00:00 daemon status root 81370 1 0 09:28 ? 00:00:00 daemon root 81372 80347 0 09:28 pts/2 00:00:00 grep --color=auto daemon daemon status， daemon start 都属于异常进程。 ...
这篇文章 Measuring Transactional Integrity in Airbnb’s Distributed Payment Ecosystem 是出自 Airbnb Blog。 由于Airbnb的全球品牌， 其支付生态系统也异常复杂，目前支持190多个国家和全球40种货币， Airbnb与少数网关以及十多个支付机构对接，实现全球支付的覆盖。但是对接的系统中成熟度不通， 对接模式不通， 清算方式不通，而且由于其业务模式要求， 对于一笔付款需要其拆分成两笔交易， 一笔是旅行者支付到平台， 另一个笔是平台支付给房东。 在旅行者支付过程中还会涉及更改， 存款， 分期， 增值税等相对负责的交易， 在通过银行给房主付款过程中由于大多数银行采取批量模式，使得清算过程异常艰辛和漫长。 在此情况下Airbnb打造了自己新的支付网关 参考现有支付平台以及银行系统方式，新的支付网关提供商户，对账报表和流水。 但是传统的工具对账并不充分。尤其是对一些历史交易，比如撤销授权， 虽然不涉及资金但是由于是跨天交易，所以也会影响我们对账交易的范围， 数据量的增加， 从而影响系统性能。 Airbnb这里采用 Hive ， Hadoop， HDFS， Airflow， S3 系列工具包， Hive提供类似SQL的界面查询数据，可以大规模的执行map-and-reduce作业。 Hadoop提供可扩展性， 适用于大型不断增长的数据集之间比较， HDFS使我们能够定期快照事务完整性， S3可以做为经济性的数据存储。Airflow是Airbnb自己开发调度工具， 用于协调各个计算步骤从而生产相关报告。 除了保障性机制外， 其还有对应的监控机制主要是通过Druid获取香瓜事务数据， Superset生成自动报告， 通过灵活配置异常检测算法， 能够支持email/slack通知。 交易完整性分析帮助识别调整问题 并有助对系统参数进行微调。 通过以上辅助工具的在保障完整性使得财务报告准确简化运营， 深度学习分析帮助轻松监控分析问题并进行报警 。 未来的一些展望， 针对自动重试， 幂等性（idempotence guarantee ）事务跟踪进行了一些探讨。 由于本身工作原因也接触了银行收单方面的工作，接触过银行收单系统， 清算机构，第三方支付系统，在银联出现之前， 普通商户银行卡支付支付要支持多家银行，是需要分别对接各家银行的， 后来出现了银联系统， 我理解就是文中的网关，对于接触过的一些商户对于如果需要支持银行的特殊的交易如分期， 积分， 商户还是要直接对接某一个银行， 而要做跨行，由对接银行链接银联实现跨行，再后来出现了 微信支付， 支付宝支付，其实还是由银行或第三方/第四方支付机构做了这个网关的工作。 随着不断的发展还会出现新的支付方式， 新的网关，必然使得支付系统会越来越复杂。 网关是个不错的选择， 真正能做到网关级别的都是相当多的资源， 当然也会从中获取相应的利益。 前一阵facebook推出的 Libra或许是一个新的解决方案。
题目： Daily Temperatures Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead. For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0]. ...
这篇文章Re-Architecting the Video Gatekeeper 是出自 Netflix Technology Blog。 Netflix上的视频需要通过Title Operations 团队的策划，使其遵守的合同；字幕、配音、翻译能够提供给合适的人群；标题名称和概要可供使用和翻译；满足各个国家的成熟度等级（分级）。 Gatekeeper是Netflix的系统， 他通过汇集多个上游系统数据， 应用一些业务逻辑，为每一个国家地区每一个视频状态的输出来完成器规定任务。GateKeeper 设置这些视频是否对用户可见。为Title Operations 指出缺少的内容， 协助其工作。 现存问题： GateKeeper是一个事件驱动的系统，上游系统每个改变都会向GateKeeper发送事件，GateKeep再通过访问每个上游服务来响应事件。可能会出现下问题： I/O 瓶颈 处理延时 事件丢失 而主动扫描处理一些指定目录可以缓解这些问题， 但是增加了更多的事件。 解决方案： 使用技术：Hollow 可以看下这篇文章使用技术 Hollow ( Drew Koszewnik)，（ 2016年，是这篇的作者） Netflix Hollow是一个java库和工具集，用于将内存数据集从单个生产者传播到许多消费者，以实现高性能的只读访问。 适合小到中级数据集 Hollow 第一阶段： 使用Hollow为每个上游系统在GateKeeper增加缓存， 在指定周期内循环迭代处理所有国家地区的视频，并生成完整输出。 第二阶段： 由于第一个阶段时间片相对较长， 整个数据来自实际数据源，一个迭代周期需要很长时间。需要进一步优化。 将Hollow分为更小时间片单位， 应用程序将每次的更改通过kafka推送 Hollow，辅助周期性的整个数据源扫描来防止数据遗漏。 效果： 性能及可用性提高：消除了I/O瓶颈，提高了性能，单个上游系统故障下可以通过过时数据进行评估。 对于新投产版本，将某一个时间X的数据做为输入， 将其输出结果其与生产版本应用的输出结果进行对比（diffed ）来准确判断是否达到预期效果。对于开发，验证，部署都比之前有了很大提高， 安全性方面也比以前架构更高。 在文末也写道将在未来几个季度实现这一目标。 对于文中描述的实时推送，全量补齐方式，实施的项目中也使用过，不过是联机+批量模式：报文从一个系统A实时推送到系统B， 夜间再通过下发批量进行全量更新补全推送时丢失的信息。 对于数据重放到预发布版本，与生产版本比较执行执行结果， 来验证新版本是否达到预期效果，和我现在项目中验证方式不一样， 目前投产后通过实际交易进行验证， 如果能方便将相关数据重放到新版本进行验证，确实将减少不少验证的工作， 不过也需要相应的应用做出相关的改造才可以。
主动调度与上下文切换 在学习极客时间刘超《趣谈Linux操作系统》 16 节时，讲到了主动调度， 通过__schedule() 函数让出cpu三个步骤： 1. 取出任务队列； 2. 从队列取下一个任务； 3. 进行上下文切换； 其中第三步中上下文切换中 调用switch_to函数， 通过调用switch_to_asm函数完成栈顶执政寄存器的交换。 代码如下： /arch/x86/include/asm/switch_to.h #define switch_to(prev, next, last) \ do { \ prepare_switch_to(next); \ \ ((last) = __switch_to_asm((prev), (next))); \ } while (0) /arch/x86/entry/entry_64.S ENTRY(__switch_to_asm) UNWIND_HINT_FUNC 。。。 /* switch stack */ movq %rsp, TASK_threadsp(%rdi) movq TASK_threadsp(%rsi), %rsp 。。。。 END(__switch_to_asm) 其中 %rdi代表第一个参数， %rsi代表第二个参数， 分别代表 prev task， next task 将当前栈顶指针放入prev task_struct 结构 thread_struct的 sp0 中。 将next_task栈顶 指做为当前栈顶指针，完成切换。 关于 TASK_threadsp，涉及以下几个文件:（当然一开始的时候正是因为找不到才有了有序寻找答案的过程） ...
运行环境： CentOS Linux release 7.5.1804 (Core)Linux centosgpt 5.2.0-rc4 #1 SMP Sun Jun 16 13:25:49 CST 2019 x86_64 x86_64 x86_64 GNU/Linux 进程的运行时间： 通过ps 查看 [root@centosgpt ~]# ps -o etime= -p "$$" 55:12 其中"$$"可以替换成具体的进程id， etime后的等号 man ps -o format ... If all column headers are empty (ps -o pid= -o comm=) then the header line will not be output. ... 上下文切换次数： 通过proc文件 /proc/{pid}/status [root@centosgpt ~]# grep ctxt /proc/1177/status voluntary_ctxt_switches: 248 nonvoluntary_ctxt_switches: 2 volutary_ctxt_switches : 表示主动调度； 发生场景 等待IO或资源 调用__schedule,主动让出cpu nonvolutary_ctxt_switches : 表示抢占式调度,； 发生场景：1时间片用完了， 需要切换到其他进程； 2 发生在高优先级进程被唤醒。 通过sysstat 前提：安装sysstat： ...
题目： Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. Example 1: Input: "()" Output: true Example 2: Input: "()[]{}" Output: true Example 3: Input: "(]" Output: false Example 4: ...
LINUX进程调度： 调度策略： 实时进程的调度策略： SCHED_FIFO SCHED_RR SCHED_DEADLINE 普通进程的调度策略： SCHED_NORMAL SCHED_BATCH SCHED_IDLE 调度类： stop_sched_class dl_sched_class rt_sched_class fair_sched_class idle_sched_class CFS调度策略： 普通进程使用的调度策略CFS调度策略，通过平衡各个进程vruntime来实现公平的调度， CFS维护了一个以时间为顺序的红黑树， 对处理器需求时间最多的，vruntime最小的存放在树的最左端. CPU取出运行完毕后，如果进程还在运行，增加运行时间计算vruntime后插会红黑树。 CFS相关结构： cfs_rq队列中存放树根节点和最左端节点rb_root_cached，每个节点都包含在 sched_entity，中，sched_entity中存放vruntime做为红黑树的索引， sched_entity 又属于 task_struct, task_struct 中通过 sched_class 指定调度类 具体可以参考是极客时间 《趣谈操作系统》 15-17节 LINUX进程调度API： sched - overview of CPU scheduling nice(2) 设置当前进程线程的优先级 getpriority(2) 获取指定用户的进程，进程组，线程优先级 setpriority(2) 设置指定用户的进程，进程组，线程优先级 sched_setscheduler(2) 设置调度策略 sched_getscheduler(2) 获取调度策略 sched_setparam(2) 设置调度参数. sched_getparam(2) 获取调度参数. sched_get_priority_max(2) 返回指定调度策略的优先级最大值 sched_get_priority_min(2) 返回指定调度策略的优先级最小值 sched_rr_get_interval(2) 获取SCHED_RR调度策略时间片长度 sched_yield(2) 主动让出CPU sched_setaffinity(2) (Linux-specific) 线程设置到指定CPU sched_getaffinity(2) (Linux-specific) 获取相关CPU设置 sched_setattr(2) 设置调度策略和参数 sched_getattr(2) 获取调度策略和参数 Posix Threads API ： ...