Wednesday, April 24, 2019

eCommerce Misc



https://mp.weixin.qq.com/s/wm5osOYgWj83XAtwZ00VdA
balance = dao.getBalance(userid)
balance = balance - cost
dao.setBalance(userid,balance)
余额修改,是交易系统里最常见的操作。上面的伪代码,大意是先取出余额,然后扣掉消费,然后再回写余额。通常情况下这不会发生问题。
除非是高并发,与你是否单机无关。
对单一余额的高并发操作自然不是正常人发起的,系统正在承受攻击,或者自以为是的使用了MQ。在攻击面前,上面的操作显得不堪一击。
拿一个最严重的例子说明:同时发起了一笔消费20元和消费5元的请求。在经过一波猛如虎的操作之后,两个请求都支付成功了,但只扣除了5元。相当于花了5块钱,买了25的东西。
划重点:把以上操作扩展到提现操作上,就更加的恐怖。比如你发起了一笔100元的提现和0.01元的提现,结果余额被扣减0.01元的提现给覆盖了。这相当于你有了一个提款机,非要薅到平台倒闭为止。

通过SQL解决

update user set balance = balance - 20
    where userid=id
这条语句就保险了很多,如果考虑到余额不能为负的情况,可以把sql更加精进一点。
update user set balance = balance - 20
    where userid=id and balance >= 20
以上sql,就可以保证余额的安全,高并发下的攻击就变得意义不大了。但会有别的问题,比如重复扣款。

通过锁解决

现实中,这种直接通过sql扣减的应用,规模都比较小。当你的业务逐渐复杂,又没有进行很好的拆分的情况下,先读再设值的情况还是比较普遍的。比如某些营销操作、打折、积分兑换等。
这种情况,可以引入分布式事务。简单点的,只需要使用redis的setnx或者zk来控制就可以;复杂点的方案,可以使用二阶段提交之类的。
分布式锁的业务粒度,要足够粗,才能保护这些余额操作;加锁的粒度,要足够细,才能保证系统的效率。
begin transition(userid)
    balance = dao.getBalance(userid)
    balance = balance - cost
    dao.setBalance(userid,balance)
end

类CAS方式解决

java的朋友可以回想下concurrent包的解决方式。那就是引入了CAS,全称Compare And Set
扩展到分布式环境下,同样可以采用这一策略。即先比较再设值。如果初始值已经变化了,那么不允许set设值。
cas一般通过循环重试的方法进行状态更新,但余额操作一般都是比较单一的,你也可以直接终止操作,并预警风险。
sql类似于:
update user set balance = balance - 20
    where userid=id
    and balance >= 20
    and balance = $old_balance
当然,你也可以通过加入版本号概念,而不是余额字段来控制这个过程,但都类似。

变种:版本号

通过在表中加一个额外的字段version,来控制并发。这种方式不去关注余额,可扩展性更强。
version的默认值一般是1,即记录创建时的默认值。
操作的伪代码如下:
version,balance = dao.getBalance(userid)
balance = balance - cost
dao.exec("
    update user
    set balance = balance - 20
    version = version + 1
    where userid=id
    and balance >= 20
    and version = $old_version
")
上面的并发攻击,将会只有一个操作能够成功,我们的余额安全了。

Tuesday, April 16, 2019

Design Amazon Product Page



求问LinkedIn设计题:设计Amazon Product Page
设计Amazon Product Page, 在SQL里面一个产品有多个图片多个价格的话怎么设计数据库。后台提取数值render到页面上得时候,class怎么设计,服务器怎么安排,另外怎么考虑suggest product。

为什么要定死是SQL。。。其实column based是更合适的数据库。

Amazon有一个概念叫ASIN,http://www.amazon.com/gp/seller/asin-upc-isbn-info.html Amazon Standard Identification Number
无论是你用SQL还是HBase,对应这个产品这个detail page的asin是你设计的这个table的primary key。

然后因为有不同颜色的variation,这个table有一列应该是指明该asin是否是parent asin:http://docs.aws.amazon.com/AWSECommerceService/latest/DG/VariationParent.html

Parent asin的price之类的column都可以缺失。

然后它对应的variation是一个map,以各种不同的configuration对应不同的子asin。

子asin也同样是这个表中的条目,但是它们有price,可以被purchase。

设计class主要是围绕着ProductItem来,就不细说了。

要有一个默认的子asin,而每个asin有对应的一系列图片url,这样你切换颜色的时候就可以切换一系列图片。
这里比较tricky的地方是当有多个变化维度的时候(比如说color和size),如何去让上面的设计adapt这个新的需求(先卖个关子。。提示:多重parent asin可以解决这个问题,或者要改schema

suggest product属于recommendation system的内容,基本上做个简单的只要搞聚类就行了。后端处理推荐的时候主要是offline,因为这玩意实时性要求不高

这个问题是地里发的面经,我想面试官大概并不是想看面试者是不是actually了解amazon的架构,而是给出购物平台/网站这样的一个scenario,想让设计database schema以及前后台怎么更高效地交互。
我自己本身并没有在实际工作中整体设计system或者database的机会,我在准备这道题的时候自己列了一下需要的table,按照relational db的一些原则设计的,你说得很对在一些特定的query条件下nosql应该更合适,尤其当涉及到要经常join很多table的时候mysql比较就昂贵。之前没有想到引入parent的设计,看了你的回复非常受启发,这点确实是不是relational都可以用,应该可以improve一下。非常感谢

本帖最后由 staycrazy 于 2016-2-5 00:21 编辑
icynell@hotmail 发表于 2016-2-4 15:36
学习了,非常感谢~!!! 这个问题是地里发的面经,我想面试官大概并不是想看面试者是不是actually了解am ...

这个就从用户交互往回推吧。。你的想法基本是对的

因为是一个物品的detail page,所以说在更换颜色或者大小的时候,最好用ajax来取得新setting的信息,这就要求我们要有一个办法把db里面的数据转成json

(但是我们为了降低latency不可能每一次都ajax——第一次render的时候,假设我们用的是Spring框架,那么jsp里面的数据是dispacth的时候已经填好的,还有为了兼容不支持javascript的browser也不能只支持ajax——这也就应和了第一次render不用ajax的要求。。)

这里有一个考虑就是我们要不要在web app这一层引入一个对象映射,还是说直接把数据库里面的内容映射成map或者json。我个人偏好是应该还是要有一个DAO。否则的话我们在web app层会引入一些维护问题——如果我们用的是no sql,schema definition就无处可寻了。当然如果你用relational,基本是hibernate orm那一套,这个就不用担心了。

所以流程大概就是,第一次load的时候从db读出一个item,然后render到template上(jsp/ejs/...),发回给用户。

用户改变产品颜色,javascript代码发一个ajax请求给服务端,服务端读出对应的product,序列化成json然后发还给browser。javascript处理json然后用无论什么奇特的方法(jQuery)去改变页面内容。

如果browser不支持javascript,则直接加url参数load新页面。


OOD Interview Summary



Traffic light oo design
地里有同学知道traffic light design题的相关步骤或者分享吗?经常看见这题但基本没搜出来适合面试但相关答案呀
这种设计OO题,我经常搞不懂的是题目中什么Objects我需要设计。中央控制系统我明白是本题要做的。但是有些真实世界里的联动装置,中央是不应该管的。

举个例子,中央说你绿灯3号由灭变亮。可是灯里电子系统出了故障灯不亮,中央还管这些?

什么objects在题目考核范围,什么不再,如何划线。这是我的难点


我真心觉得跟Design pattern 关系没那么大,design pattern主要考虑设计的扩展,复用等,如何利用OO思想设计,但是OOD题目首先要考虑设计出来功能,比如停车场设计,LRU  这种,开放什么方法,写什么属性在Class中。如果是经验一般的人,弄完这些了才考虑用design pattern 重构,经验充足的当然一上来考虑当前模型适用什么design pattern了,但是如果new grad,没那么多开发经验,根本做不到
推荐《大话设计模式》。这本书写得深入浅出,以至于我用了两天就看完了,明白了不少有用的设计模式

先想想都涉及到什么物体(即名词),然后这些一般就是类。
然后想想继承,多态。比如都是车,但是有不同的类型,大小也会对停车位有影响。
Gayle的书里讲了停车场,但是那种复杂的停车场我不太懂,那停车场还分好多层。

听说amazon还问过棋类的设计。

我写过一个中国象棋。

https://github.com/Linzertorte/ChineseChess

视频 https://www.youtube.com/watch?v=a0cOULTFbTM

Design Pattern Interview Summary



Design Pattern 设计 - 请看应该选择那种模式
讨论如下设计题Task
  • Implement a type "Robot" with the following requirements
    • Robot must support pluggable chips that allow him to do different operations on numeric arrays
    • Only one chip can be plugged at a time and robot can't function without a chip
    • Chips can be swapped at runtime, since you have only one robot instance (robots are expensive)
  • Robot should have only two functions/methods
    • A function that executes current chip's logic and returns result, it should accept an array and return whatever current chip is returning
    • A function that installs a chip into a robot, it should accept a chip and should not return anything
  • Implement two chips
    • "Chip of Sorts" — sorts an array in the order and can have an option to specify ascending or descending type of sorting. (Sorting algorythm is not important, use standard one from any library you want.)
    • "Total Chip" — finds a total sum of all elements of an array
  • Add a property to your robot that represents total number of different chips installed through robot's lifetime. It should only count unique chips being installed.
  • Write one simple test function that tests logic from 4, you don't have to use any Unit Testing framework, just a simple function would be fine
  • It's up to you how do design your robot and types. Pay attention to make design simple and intuitive.
Bonus
There is no right or wrong solution as long as code works, but we give bonus points for a plain-text explanation on why particular design decisions were made and what are the tradeoffs. Put it right into the code in a form of a comment at the beginning of the main file.

Eviction policy - Design Pattern



关于cache的 eviction policy设计
TODO: https://github.com/apache/ignite/tree/master/modules/core/src/main/java/org/apache/ignite/cache/eviction
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=316982

我觉得可能strategy看起来更好些,考虑到是个behavioral pattern,不同algorithm 重写同一个方法, 但是需要考虑的重点应该变成了如何使得这个重写的方法尽可能够都使用公共的数据存储结构。最坏不做抽象的情况,就是数据结构保存在当前类中,就变成了类似于factory模式的模式了

我刚搜了圈,发现 apache ignite 有类似的抽象的例子
https://ignite.apache.org/releas ... EvictionPolicy.html,不过好像就是把evictionPloicy抽象成abstract class了,然后数据结构也是在子类中定义的。就如同你说的,不一样的policy的数据结构是不一样的,强行去abstract common 数据结构会有点得不偿失,所以用个工厂模式可能会比较好懂,代码也比较直观

就是设计一个cache的eviction policy,你可以选择是LRU, 还是LFU,还是其他eviction policy. 选择哪个,就按照哪个eviction policy执行。
大家认为这种情况,用哪个pattern比较好?


首先回顾一下LeetCode的LRUCache这道题目所设计的接口:
  1. class LRUCache {
  2. public:
  3.   // Get the value (will always be positive) of the key if the key exists in the
  4.   // cache, otherwise return -1.
  5.   int get(int key);

  6.   // Set or insert the value if the key is not already present. When the cache
  7.   // reached its capacity, it should invalidate the least recently used item
  8.   // before inserting a new item.
  9.   void put(int key, int value);
  10. };
复制代码


当然这个接口非常简陋,至少有两个问题:

(1) Cache和eviction policy(LRU)的逻辑是合并在一起的

这也正是我们这里OOD设计所要解决的问题:将eviction policy解耦(decouple)出来,使得其可以作为一个参数(或者模板参数)被传入Cache类,那么得到的Cache对象就会使用对应的policy。

(2) 没有触及cache设计的一个重要部分:value的生存期的管理

如果value是占用较多内存空间的大对象(而不是LeetCode题中仅占用4个字节的栈区int),或者是C/C++写的代码,一般是由cache管理生存期。
也就是说当evict一个value时,其占用内存应该立刻被回收,而这时所有对该value对象的引用应当立刻失效 —— 在这种情况下要避免代码出bug(非法内存访问),必须由cache对value进行引用计数,且返回值使用"counted reference"(类似于C++ shared pointer)。
不过如果返回的是栈区对象/对象的拷贝/带GC语言下(例如Java)的对象引用,那么不需要考虑引用计数问题,但是这时cache就无法保证内存的使用量被控制在规定范围内。

第(2)点其实是为了说一下eviction policy设计时关于引用计数的接口 —— 下面简化的代码中没有实现这一接口,但是需要了解一下,因为很多实际系统中是有相关内容的,例如PostgreSQL:https://github.com/postgres/postgres/blob/master/src/backend/storage/buffer/bufmgr.c#L139

现在回到(1),下面贴的代码主要包含了:
(a) EvictionPolicy的抽象类
(b) 继承了EvictionPolicy的LRU/LFU实现
(c) 一个EvictionPolicy工厂,使得可以比较容易地添加新的Policy实现
(c) 使用EvictionPolicy实现的Cache类


  1. // Eviction policy的抽象
  2. template <typename Entry>
  3. class EvictionPolicy {
  4. public:
  5.   virtual Entry chooseEntryToEvict() = 0;

  6.   virtual void entryCreated(const Entry &entry) = 0;

  7.   virtual void entryReferenced(const Entry &entry) = 0;

  8.   // 如果维护引用计数的话需要这个接口
  9.   // virtual void entryUnreferenced(const Entry &entry) = 0;

  10.   virtual void entryEvicted(const Entry &entry) = 0;
  11. };


  12. // Eviction policy的类型
  13. enum class EvictionPolicyType : int {
  14.   kLRU = 0,
  15.   kLFU,
  16.   kClock,
  17.   // ...
  18. };


  19. // 一个简单的LRU实现,不支持并发访问
  20. template <typename Entry>
  21. class LRUPolicy : public EvictionPolicy<Entry> {
  22. public:
  23.   Entry chooseEntryToEvict() override {
  24.     return list_.back();
  25.   }

  26.   void entryCreated(const Entry &entry) override {
  27.     list_.push_front(entry);
  28.     index_.emplace(entry, list_.begin());
  29.   }

  30.   void entryReferenced(const Entry &entry) override {
  31.     const auto &it = index_.at(entry);
  32.     if (it != list_.begin()) {
  33.       list_.splice(list_.begin(), list_, it, std::next(it));
  34.     }
  35.   }

  36.   void entryEvicted(const Entry &entry) override {
  37.      const auto it = index_.find(entry);
  38.      list_.erase(it->second);
  39.      index_.erase(it);
  40.   }

  41. private:
  42.   using EntryList = std::list<Entry>;
  43.   using EntryListIterator = typename EntryList::iterator;

  44.   std::list<Entry> list_;
  45.   std::unordered_map<Entry, const EntryListIterator> index_;
  46. };


  47. // 一个简单的LFU实现,不支持并发访问
  48. template <typename Entry>
  49. class LFUPolicy : public EvictionPolicy<Entry> {
  50. public:
  51.   Entry chooseEntryToEvict() override {
  52.     return std::get<0>(*list_.begin());
  53.   }

  54.   void entryCreated(const Entry &entry) override {
  55.     const auto ret = list_.emplace(entry, Clock::now(), 1);
  56.     index_.emplace(entry, ret.first);
  57.   }

  58.   void entryReferenced(const Entry &entry) override {
  59.     auto &it = index_.at(entry);
  60.     const std::size_t count = std::get<2>(*it);
  61.     list_.erase(it);
  62.     const auto ret = list_.emplace(entry, Clock::now(), count + 1);
  63.     it = ret.first;
  64.   }

  65.   void entryEvicted(const Entry &entry) override {
  66.     const auto it = index_.find(entry);
  67.     list_.erase(it->second);
  68.     index_.erase(it);
  69.   }

  70. private:
  71.   using Clock = std::chrono::high_resolution_clock;
  72.   using TimePoint = std::chrono::time_point<Clock>;
  73.   using Record = std::tuple<Entry, TimePoint, std::size_t>;
  74.   struct RecordComparator {
  75.     inline bool operator()(const Record &lhs, const Record &rhs) const {
  76.       if (std::get<2>(lhs) != std::get<2>(rhs)) {
  77.         return std::get<2>(lhs) < std::get<2>(rhs);
  78.       }
  79.       if (std::get<1>(lhs) != std::get<1>(rhs)) {
  80.         return std::get<1>(lhs) < std::get<1>(rhs);
  81.       }
  82.       return std::get<0>(lhs) < std::get<0>(rhs);
  83.     }
  84.   };
  85.   using SortedList = std::set<Record, RecordComparator>;
  86.   using SortedListIterator = typename SortedList::iterator;

  87.   SortedList list_;
  88.   std::unordered_map<Entry, SortedListIterator> index_;
  89. };


  90. // Eviction policy的单例工厂
  91. template <typename Entry>
  92. class EvictionPolicyFactory {
  93. public:
  94.   static const EvictionPolicyFactory& Instance() {
  95.     static EvictionPolicyFactory<Entry> instance;
  96.     return instance;
  97.   }

  98.   EvictionPolicy<Entry>* createEvictionPolicy(const EvictionPolicyType type) const {
  99.     switch (type) {
  100.       case EvictionPolicyType::kLRU:
  101.         return new LRUPolicy<Entry>();
  102.       case EvictionPolicyType::kLFU:
  103.         return new LFUPolicy<Entry>();
  104.       default:
  105.         break;
  106.     }
  107.     throw std::runtime_error("Unsupported eviction policy type");
  108.   };
  109. };


  110. // 一个简单的泛型Cache实现
  111. template <typename Key, typename Value>
  112. class Cache {
  113. private:
  114.   using Storage = std::unordered_map<Key, Value>;
  115.   using Entry = const typename Storage::value_type*;
  116.   using Factory = EvictionPolicyFactory<Entry>;

  117. public:
  118.   Cache(const std::size_t capacity, const EvictionPolicyType type)
  119.       : capacity_(capacity),
  120.         eviction_policy_(Factory::Instance().createEvictionPolicy(type)) {
  121.   }

  122.   const Value* get(const Key &key) {
  123.     const auto it = storage_.find(key);
  124.     if (it == storage_.end()) {
  125.       return nullptr;
  126.     }

  127.     eviction_policy_->entryReferenced(&(*it));
  128.     return &it->second;
  129.   }

  130.   void put(const Key &key, const Value &value) {
  131.     const auto it = storage_.find(key);
  132.     if (it == storage_.end()) {
  133.       if (storage_.size() >= capacity_) {
  134.         const auto ev = eviction_policy_->chooseEntryToEvict();
  135.         eviction_policy_->entryEvicted(ev);
  136.         storage_.erase(ev->first);
  137.       }
  138.       const auto ret = storage_.emplace(key, value);
  139.       eviction_policy_->entryCreated(&(*ret.first));
  140.     } else {
  141.       it->second = value;
  142.       eviction_policy_->entryReferenced(&(*it));
  143.     }
  144.   }

  145. private:
  146.   const std::size_t capacity_;
  147.   Storage storage_;
  148.   std::unique_ptr<EvictionPolicy<Entry>> eviction_policy_;
  149. };

  150. /*******************************************************************************
  151. * 可以用于提交LeetCode 146的代码

  152. class LRUCache {
  153. public:
  154.   LRUCache(int capacity)
  155.       : cache_(capacity, EvictionPolicyType::kLRU) {
  156.   }

  157.   int get(int key) {
  158.     const int *value = cache_.get(key);
  159.     return value == nullptr ? -1 : *value;
  160.   }

  161.   void put(int key, int value) {
  162.     cache_.put(key, value);
  163.   }

  164. private:
  165.   Cache<int, int> cache_;
  166. };

  167. *******************************************************************************/

  168. template <typename C, typename T>
  169. void Print(C &cache, const T &key) {
  170.   const auto *value = cache.get(key);
  171.   if (value == nullptr) {
  172.     std::cout << "[" << key << "] NULL\n";
  173.   } else {
  174.     std::cout << "[" << key << "] " << *value << "\n";
  175.   }
  176. }

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts