<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Jason Xu on Medium]]></title>
        <description><![CDATA[Stories by Jason Xu on Medium]]></description>
        <link>https://medium.com/@weixu?source=rss-96bde300b248------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*5iLBoCeAu2KuKScs.jpg</url>
            <title>Stories by Jason Xu on Medium</title>
            <link>https://medium.com/@weixu?source=rss-96bde300b248------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 03:27:17 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@weixu/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Designing Data-Intensive Applications, Part II]]></title>
            <link>https://medium.com/@weixu/designing-data-intensive-applications-part-ii-2a55ea4f3ee2?source=rss-96bde300b248------2</link>
            <guid isPermaLink="false">https://medium.com/p/2a55ea4f3ee2</guid>
            <category><![CDATA[design-systems]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Jason Xu]]></dc:creator>
            <pubDate>Wed, 16 Jan 2019 04:42:19 GMT</pubDate>
            <atom:updated>2019-01-16T04:42:19.131Z</atom:updated>
            <content:encoded><![CDATA[<h3>Part II. Distributed Data</h3><p>Distribute data across multiple machines for scalability, fault tolerance and lower latency.</p><h4>Scaling to Higer Load</h4><p><strong><em>Shared-memory architecture</em></strong>: scale up, and cost increase faster than linearly, not working well for fault tolerance or reducing latency in multi-geolocation.</p><p><strong><em>Shared-nothing architecture</em></strong>: scale out, cost increase linearly (likely). This part focus on shared-nothing architecture not because it’s always the best, but because it requires more caution from application developers — trade offs, advantages and complexity.</p><p><strong><em>Replication vs Partition</em></strong>: 2 ways to distribute data in multiple machine, copy vs split.</p><h3>Chapter 5. Replication</h3><blockquote>All of the difficulty in replication lies in handling <strong><em>changes</em></strong><em> </em>to replicated data. We will discuss three popular algorithms for replicating changes between nodes:<strong> <em>single-leader</em></strong>, <strong><em>multi-leader</em></strong>, and <strong><em>leaderless</em></strong><em> </em>replication.</blockquote><h4>Leaders and followers</h4><p><em>Leader-based / active-passive / master-slave</em> replication: 1) one replica designated as <em>leader</em> and data is written to leader first; 2) leader send changes to all the other replicas (<em>followers</em>) and follower apply the changes; 3) leader allows read and write, followers are read-only</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WTkANoAmRq9WUmU0v9sV9Q.png" /></figure><p><strong><em>Synchronous vs Asynchronous Replication</em></strong>: synchronous replication provides better consistency, exact copy of leader but introduce latency in confirming to client. Usually in a database system, there will be one or more synchronous replication and multiple asynchronous replication.</p><p><strong><em>Handling Node Outage in Leader-based replication</em>: </strong>handing <em>follower</em> failure is easy: catch-up recovery (apply all changes from leader during outage).</p><p>But handling <em>leader</em> failure is trickier: <strong><em>failover</em></strong> — 1) determine that leader has failed, 2) elect the new leader and 3) reconfigure the system to use the new leader.</p><p><strong><em>Failover</em></strong> is fraught with thing that can go wrong: 1) asynchronous replication is used and follower is actually not up-to-date; 2) lost write create <em>inconsistency</em> to other systems like Redis; 3) <em>split-brain</em> — both replica believe they are new leader; 4) long timeout leads to delayed recovery, short timeout leads to unnecessary failover.</p><p><strong><em>Implementation of Replication Logs</em></strong></p><ol><li>statement-based replication: leader send executed write statement to followers. Works well until there’s non-deterministic functions like NOW() , RAND() .</li><li>write-ahead log shipping: for log-structured storage (refer to Part I), or a B-tree structure which requires write-ahead log for restoring index, these logs can be used to build the exact replica. Relies on storage engine, so if storage engine change, a downtime will be required.</li><li>logical (row-based) log replication: a sequence of statements describing what changed for a row, decoupled from storage engine, easier for external application to parse (<em>change data capture</em>).</li><li>trigger-based replication : register trigger on data change, more flexible but has overhead.</li></ol><p><strong><em>Problem of Replication Lag</em></strong></p><p>Leader-based replication is ok for read-scaling architecture — only write to one node and read from many nodes. But the lagging of update in the followers (when using asynchronous replication) will cause inconsistency and may cause problem in the real application.</p><ol><li>reading-your-own-write: user should always see the update he/she just made. Asynchronous replication lead to inconsistency in read. This can be alleviated by always reading from leader if user can modify the data.</li><li>monotonic-reads : making multiple request to different replicas may give inconsistent data. one way to solve it is to ensure each user only read from the same replica.</li><li>Consistent Prefix Reads : in a partitioned (sharded) database, each partition operates independently, so there’s no global ordering of writes. Thus, if 2 data has a causality / sequence but they are written to different partition, the read may give different order.</li></ol><h4>Multi-Leader Replication</h4><p>One downside with the single leader-follower replication is that, all writes go into one node. Mutli-leader replication allows write to multiple nodes and the changes are propagated to other nodes.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2a55ea4f3ee2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Designing Data-Intensive Applications, Part I]]></title>
            <link>https://medium.com/@weixu/designing-data-intensive-applications-part-i-7af77b300575?source=rss-96bde300b248------2</link>
            <guid isPermaLink="false">https://medium.com/p/7af77b300575</guid>
            <category><![CDATA[software-architecture]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Jason Xu]]></dc:creator>
            <pubDate>Sun, 22 Apr 2018 07:36:27 GMT</pubDate>
            <atom:updated>2018-04-22T07:36:27.436Z</atom:updated>
            <content:encoded><![CDATA[<p>Recently I have been reading the book “<a href="https://dataintensive.net/"><strong><em>Designing Data-Intensive Applications</em></strong></a>”. I found many inspiration from this book for the challenges and design decisions in my daily work.</p><p>As it’s written in such a structured way, I think it’s worthwhile to have a summary of this book for future reference. I will break down the summary into a series of articles. And this is the first article for the first part of the book.</p><blockquote><em>“This book is awesome. It bridges the huge gap between distributed systems theory and practical engineering.”</em> — <a href="https://twitter.com/jaykreps">Jay Kreps</a>, creator of <a href="http://kafka.apache.org/">Apache Kafka</a> and CEO at <a href="https://www.confluent.io/">Confluent</a></blockquote><h3>Part I. <strong>Foundation of Data Systems</strong></h3><h3>Chapter 1. Reliable, Scalable and Maintainable Application</h3><h4><strong>Reliability: </strong>system should work even in the face of adversity.</h4><ol><li><strong><em>Hardware fault </em></strong>— e.g. disk failure (hardware redundancy), aws instance went down (software level fault-tolerance technique such as running multiple instances of an application and using heart-beat exchange).</li><li><strong><em>Software error</em></strong> — a systematic error, should be addressed with testing, monitoring and constant self-checking.</li><li><strong><em>Human error </em></strong>— human operation could be unreliable, system need to provide clear interface, sandbox, easy recovery of human errors.</li></ol><h4><strong>Scalability</strong>: maintaining performance when load increase</h4><ol><li><strong><em>Describe Load</em></strong><em> </em>— load parameter depends on system architecture, it could be request per second, number of active users or something else that will increase and create problem for the system.</li><li><strong><em>Describe Performance</em></strong><em> </em>— could be the throughput (number of data processed per second), or response time (time to handle a request). Usually better to use percentiles e.g. 99th percentile response time is 1 second.</li><li><strong><em>Cope with Load</em></strong> — scale up /scale out. “While distributing stateless services across multiple machines is fairly straightforward, taking stateful data systems from a single node to a distributed setup can introduce a lot of additional complexity.”</li></ol><h4><strong>Maintainability</strong></h4><ol><li><strong><em>Operability</em></strong> — easy to monitor system, track problem, gain visibility of runtime behaviour, deploy new change, update configuration.</li><li><strong><em>Simplicity</em></strong> — symptoms of complexity: special casing to work around issue, explosion of state space, hidden assumptions, unintended consequences and many more. Complexity makes it easy to introduce bug when making a change. One of the tools to reduce complexity is abstraction .</li><li><strong><em>Evolvability</em></strong> — agility to changes in system requirements.</li></ol><h3>Chapter 2. Data Models and Query Language</h3><p>Most applications are built by layering one data model on top of another. The idea is that each layer hides the complexity of the layer below by providing a clean data model.</p><h4>Relational Model vs Document Model</h4><p>Fault-tolerance properties (see Chapter 5) and handling of concurrency (see Chapter 7) will be discussed later, we will focus on data model. General pros for document database: schema flexibility (schema-on-read), better performance due to locality, closer to application data models. While pros for relational database: better support for join, many-to-many relationship.</p><ol><li>Which lead to simpler application code: depends on relationship of data. If there’s many-to-many relationship, using document model will move the complexity to application and is slower due to multiple queries. if the relationships is mainly one-to-many , using relational model may lead to complex application code.</li><li>Schema flexibility: document database(schema-on-read), relational database( schema-on-write ). schema-on-read will be more reasonable if 1) there are many types of objects and not practical to keep each type of object in its own table 2) the schema is determined by third party and may change in the future</li><li>Data locality: document model will be more performant if the complete object needs to be accessed (relational database will need to look up multiple index), the object size is small and update is not frequent.</li><li>Convergence of both: postgresql, mysql and some other relational database supports JSON/XML column type</li></ol><h4>Graph Data Model</h4><p>Graph data model is more useful if many-to-many relationship is very common (social graph, web graph, road graph). 2 types of structuring are discussed: property graph and triple-store graph .</p><ol><li>property graph: vertex(id, incoming edges, outgoing edges, properties) and edge(id, head vertex, tail vertex, label, properties)</li><li>triple-store graph: all information is stored in the form of very simple three-part statements: (<em>subject</em>, <em>predicate</em>, <em>object</em>)</li></ol><h3>Chapter 3. Storage and Retrieval</h3><h4>Data structure that power your database</h4><p>The simplest database we can implement is an <em>append-only</em> file (log). Appending to a file is generally efficient (better than random write due to disk seek time), but to look up a record is not — need to scan the whole file. That’s why we need another <em>additional</em> data structure — index.</p><p>However, there’s an important trade-off with index : well-chosen index speedup read but every index slow down write.</p><ol><li><strong>Hash indexes </strong>keep a hash map in memory. It provides good performance in query but it 1) requires the hash map can fit in the memory; 2) not efficient in range query. <strong>Compaction</strong>: we store the data logs in small segments and merge them from time to time, which removes duplicated keys and keeps the latest update for each key.</li><li><strong>SSTables and LSM-Trees</strong> SSTable is Sorted String Table , which enforces that 1) keys in each segment is sorted 2) keys are unique in each segment. It gives the benefits: 1) enable mergesort kind of operation which does not require loading all logs in memory; 2) enable sparse keys in the in-memory hash map because keys are sorted. The basic idea of <em>LSM-Tree (log-structured Merge-Tree) </em>is keeping a cascade of <em>SSTables</em> that are merged in the background — <em>as the writes are sequential the LSM-Tree can support remarkable high write throughput</em>. (RocksDB, Cassandra, HBase)</li><li><strong>B-Tree</strong>. Each page can be identified using an address or location, which allows one page to refer to another—similar to a pointer, but on disk instead of in memory.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*euhePwmpxpKHBg0aI2Qlvg.png" /></figure><p>4. <strong>LSM-Tree vs B-Tree</strong>. Generally LSM-Tree index offers better write throughput than B-Tree index, however, since there’s multiple copy of keys in different segments, read could be slow in LSM-Tree index.</p><p>5. <strong>Other indexing structures</strong>. 1) Storing value with index (clustered index); 2)multi-column index; 3) full text search and fuzzy indexes; 4) keep everything in memory: “<em>Counterintuitively, the performance advantage of in-memory databases is not due to the fact that they don’t need to read from disk. Even a disk-based storage engine may never need to read from disk if you have enough memory, because the operating system caches recently used disk blocks in memory anyway. Rather, they can be faster because they can avoid the overheads of encoding in-memory data structures in a form that can be written to disk</em>”.</p><h4>Transaction Processing or Analytics</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4JllcQfjMEg3d8xoAkDgfw.png" /><figcaption>compare OLTP and OLAP</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-5PVqXqqMR7CmE1aVYCO_w.png" /><figcaption>extract-transform-load</figcaption></figure><p><strong>Schema for analytics</strong>: <em>Stars</em> (<em>fact table</em> —describing events, is in the middle, surrounded by its <em>dimension tables</em> — describing attributes), <em>Snowflake</em> (dimension table further broken down to subdimensions).</p><h4>Column Oriented Storage</h4><p>The idea behind <em>column-oriented storage </em>is simple: don’t store all the values from one row together, but store all the values from each <em>column </em>together instead. If each column is stored in a separate file, a query only needs to read and parse those columns that are used in that query, which can save a lot of work (memory bandwidth from disk to memory).</p><ol><li>Sort order in column-oriented storage: store the same data in different sorted order, since the data needs to be replicated anyway.</li><li>Write to column-oriented storage: LSM-Tree. Writing in the mid of a sorted columns almost require a rewrite, so B-Tree not a good idea. LSM-tree merges segments will be more useful.</li></ol><h4>Data Cube and Materialised Views</h4><p>In relational database, aggregation can usually be defined into a materialised view which will update itself when underlaying data change. Trade-off is the performance impact in writes.</p><h3>Chapter 4. Encoding and Evolution</h3><h4>Format of encoding data</h4><ol><li><em>encoding / serialisation / marshalling</em>: from in-memory data representation to byte sequence</li><li><em>decoding / deserialisation / unmarshalling</em>: from byte sequence to in-memory representation</li></ol><h4>JSON, XML, and Binary Variants</h4><p>Textual format, a bit more human-readable, but 1) has ambiguity in encoding numbers; 2) not support binary string; 3) optional schema support, leading to many manual encoding/decoding code.</p><h4>Thrift and Protocol Buffers</h4><p>Both require a schema for any data to encode. Both provide code generation tool that takes a schema definition file and generate classes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/810/1*h_kRHnpnpXhCrGcaIVniXA.png" /></figure><p><em>Field tags</em> are important to schema evolution — field tags are used in the encoding but not the field name.</p><h4>Merits of Schemas</h4><p>Although textual data formats (JSON, XML, CSV) are wide-spread, binary encodings based on schemas have their merits.</p><ol><li>more compact by omitting field name in the encoded data</li><li>a form of documentation</li><li>check for forward/backward compatibility</li><li>type checking in compile time for statically typed language</li></ol><h4>Modes of Dataflow</h4><p>Compatibility is the relationship between one process that encodes the data, and another process that decodes the data. <strong><em>Forward compatibility</em></strong> — old code able to read data written by new code; <strong><em>backward compatibility</em></strong> — new code able to read data written by old code. Compatibility is important for <strong><em>rolling upgrade</em></strong> for deployment without downtime — hugely beneficial for <strong><em>evolvability</em></strong>.</p><p><strong>Via database</strong>: new code will need to maintain backward compatibility, or migrate the data to new schema</p><p><strong>Via service call</strong>: a key design goal of a service-oriented/microservices architecture is to make the application easier to change and maintain by making services independently deployable and evolvable.</p><ol><li>Network API request: REST (not protocol, more like a philosophy ), SOAP (XML-based network protocol).</li><li>RPC (remote procedure call): the idea to make network request similar to local function call, which does not work well due the fundamental difference between network request and function call — network request is less predictable than local function call</li></ol><p><strong>Via asynchronous message passing</strong>: passing message through a message broker / queue, the recipient process message but does not reply (but you can make the recipient send reply message in another queue). The advantages:</p><ol><li>act as buffer if the recipient is overloaded or unavailable — improve reliability</li><li>redeliver message in case of recipient crash — prevent message lost</li><li>avoid senders needing to know ip and port of recipient — decouple</li><li>allow one message to be send to multiple recipients</li></ol><p>Distributed actor framework</p><ol><li><em>actor model</em>: concurrency model in a single process. Not directly working with thread, each actor communicate with another actor by <em>sending and receiving asynchronous message</em>.</li><li><em>distributed actor framework</em>: using the same message-passing mechanism as actor model, but across multiple nodes — enable scaling the application.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7af77b300575" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Service discovery in microservice architecture]]></title>
            <link>https://medium.com/hackernoon/understand-service-discovery-in-microservice-c323e78f47fd?source=rss-96bde300b248------2</link>
            <guid isPermaLink="false">https://medium.com/p/c323e78f47fd</guid>
            <category><![CDATA[microservices]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[software-architecture]]></category>
            <dc:creator><![CDATA[Jason Xu]]></dc:creator>
            <pubDate>Fri, 09 Mar 2018 15:13:20 GMT</pubDate>
            <atom:updated>2018-03-15T04:08:07.348Z</atom:updated>
            <content:encoded><![CDATA[<p>Many years ago, the easiest way to lose contact with your friend is to change your phone number without informing them.</p><p>Same applies to services in a microservice architecture system. Two services may be happily talking to each other until one of them moves to another ip address.</p><h4>What is service discovery</h4><p>Service discovery is about finding the network location of a service provider.</p><h4>Why do we need it</h4><p>If a team is maintaining physical servers, a configuration file will mostly satisfy the need.</p><p>However, if you are using cloud, your services may have dynamic network location due to restart, failure and scaling. Maintaining a configuration file manually is just not feasible.</p><h4>What are the components</h4><p>Service discovery involves 3 parties: service provider, service consumer and service registry.</p><ol><li>service provider registers itself with service registry when it enters and deregister itself when it leaves the system</li><li>service consumer gets the location of a provider from registry, and then talks to the provider</li><li>service registry maintains the latest location of providers</li></ol><p>There are many existing service discovery tools to use. But what if we want to build our own?</p><h4>Designing service discovery</h4><p>As service registry is basically maintaining key-value pairs (provider name, provider locations) , redis can be a good choice. Let’s simulate the service discovery process with redis as registry.</p><p>When a service provider inventory_service registers itself in registry, we use SADD to add its locations to a set :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/832/1*cQ3z4qaLCXHNXNZwdyuHWA.png" /></figure><p>When a service consumer query for the location of inventory_service , we can either use SMEMBERS to get the all locations, or we can randomly pick one with SRANDMEMBER :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/948/1*ZxGhgNpCsph8mvIpUYLx2Q.png" /></figure><p>When inventory_service deregister itself, we use SREM to remove it from the set:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/944/1*Udx3gW8ljbq7tWw9YSPKyQ.png" /></figure><p>But there’s complexity to handle:</p><ol><li><strong>The service may not deregister itself when it’s gone</strong>. Then the registry provides an invalid address to the consumer. To tackle this problem, service provider needs to send its <strong><em>heartbeat</em></strong> periodically (every 5 second maybe). If the provider hasn’t send any heartbeat for sometime, the registry will assume the death of provider, and deregister it.</li><li><strong>Querying registry before calling provider every time?</strong> It’s place too much load on registry and impose unnecessary performance impact. It’s better to keep a copy in consumer itself.</li><li><strong>If kept in consumer, how to notify consumer about the changes in provider?</strong> There are 2 ways to do it. 1) consumer use <strong><em>polling</em></strong> to get latest version. Since the locations usually don’t change so frequently, this still works. The drawback is the possible downtime between polling. 2) <strong><em>pubsub</em></strong> pattern. It provides more immediate update of locations, but it will hold up additional thread of consumer.</li><li><strong>Sending back all data of a provider may not be necessary.</strong> We can keep a <strong><em>global versioning</em></strong> of providers and consumer only needs to update its local copy when version got incremented.</li><li><strong>Single point of failure</strong>. If the service registry (e.g. the redis instance we are using here) is down, all consumer and provider will be affected. To alleviate this, we can use a<strong><em> distributed database</em></strong> as service registry, such as zookeeper/etcd/consul .</li></ol><h4>Client-side discovery or server-side discovery</h4><ol><li>client-side discovery: service consumer keep all locations of providers and load balance the requests across locations. Pros: registry is the only one more component. Cons: need to implement service discovery client for different languages/frameworks used in your system.</li><li>server-side discovery: consumer send requests to a load balancer, the load balancer query from registry and decide which location of providers to send to. Pros: language/ framework agnostic. Cons: now you need to manage another moving part — the load balancer.</li></ol><h4>Conclusion</h4><p>This article explains how service discovery works in a microservice architecture system. It helps reader to understand or debug when they work with open source tools like <a href="https://github.com/Netflix/eureka">Netflix Eureka</a>.</p><p>Reference and recommend reading:</p><ol><li><a href="https://github.com/Netflix/eureka/wiki/Understanding-eureka-client-server-communication">https://github.com/Netflix/eureka/wiki/Understanding-eureka-client-server-communication</a></li><li><a href="https://www.nginx.com/blog/service-discovery-in-a-microservices-architecture/">https://www.nginx.com/blog/service-discovery-in-a-microservices-architecture/</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c323e78f47fd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/understand-service-discovery-in-microservice-c323e78f47fd">Service discovery in microservice architecture</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Developing a flash sale system]]></title>
            <link>https://medium.com/hackernoon/developing-a-flash-sale-system-7481f6ede0a3?source=rss-96bde300b248------2</link>
            <guid isPermaLink="false">https://medium.com/p/7481f6ede0a3</guid>
            <category><![CDATA[flash-sale]]></category>
            <category><![CDATA[software-architecture]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[flash-sale-system]]></category>
            <dc:creator><![CDATA[Jason Xu]]></dc:creator>
            <pubDate>Sun, 21 Jan 2018 09:32:10 GMT</pubDate>
            <atom:updated>2018-01-21T21:48:50.329Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IDV0DLWDt0EVMh0BAML5NA.png" /><figcaption><a href="http://www.internationalnewsandviews.com/wp-content/uploads/2017/03/flash-sale-banner.png">http://www.internationalnewsandviews.com/wp-content/uploads/2017/03/flash-sale-banner.png</a></figcaption></figure><p>There’s a well-known website in China that almost every Chinese use and we usually only use it once a year — 12306.com, the railway ticket booking system.</p><p>When the website open the sales for tickets for Chinese New Year, many people are waiting in front of their computer and get ready to click the reserve button at the exact time when sale starts.</p><p>Then, the website crashed and users complained.</p><p>(And then software engineers reflect how to fix it)</p><h3>What is flash sale system</h3><p>The example above is a typical flash sale system. It usually has the following characteristics:</p><ol><li>Large number of users come to the system at the same time, causing a spike in traffic. (Tickets sales starts at 6am and finishs at 6:30am)</li><li>Number of ordering request is much larger than inventory size. (1 million users competing for 10,000 tickets)</li></ol><h3>What are the challenges</h3><ol><li>Handle load on read. Users will constantly refresh the page to check available inventory. It’s also likely that all users will request for other similar resource at the same time, such as account, item description, etc.</li><li>Provide high throughput. There will be many concurrent read and write to the limited inventory records, so the database lock may result in timeout for some of the requests.</li><li>Avoid inventory from being oversold or undersold. how to handle the available inventory number? An item may be oversold if multiple requests reserved the same inventory. An item may be undersold if the inventory is hold but the process failed and inventory is not released. This happened to some e-commerce website, and usually they will call the customers to refund.</li><li>Prevent cheating with script. user could write a script to fire request in a loop. so this user may generate many repeated requests</li></ol><h3>Design considerations</h3><ol><li>Limit request from upstream: we have limited inventory, even if 1 million users come, we can only serve 1000 of them. Can reduce the number of unnecessary requests from users?</li><li>Split the traffic: the root cause is that we ask users to come at the same time and create a spike. Can we divide the sales into different time slots and invite users for different time slot?</li><li>Asynchronous processing: do we need to process the request immediately? Or we can accept the request, process it with the pace that our system can support and notify user within a acceptable time?</li><li>Cache, cache, cache: many repeated read on resource that never/seldom changes. Can we keep them in cache to relieve the load on database?</li><li>Understand tradeoff and make the sacrifice: do we really need to show the realtime inventory? we only have this flash sale once a year, does it make sense to dump so many resources on it?</li><li>Database design: different schema design for the same problem will have different tradeoffs.</li><li>Scalability: are we able to scale horizontally to support more users?</li></ol><h3>Optimisation by layers</h3><h4>Client</h4><p>When the user did not get the immediate response after submitting a request, they will tend to click the button again and again. However, those requests are duplicates and create unnecessary load for the system. (Just imagine every user resubmit 9 more requests, then 90% of the requests system received are redundant)</p><p>What we can do is to:</p><ol><li>disable submit button once it’s submitted</li><li>only send out the request if there’s no duplicated request in recent 1 minute.</li></ol><p>This will reduce most of the unnecessary requests from client side, however, it does not prevent user from writing a script to bypass the client side restriction. So we need to do more.</p><h4>Gateway</h4><p>When a request reached the gateway, we keep track of the request number by the same user. The simple and effective solution is to keep a counter for each user ID in memory.</p><p>We can drop the request or return the same response if the same request was made recently by this user.</p><p>However, what if this user created thousands of user accounts? We will handle it in the service layer.</p><h4>Services</h4><p>Now the requests that reached service layer are much less. Let’s start processing them.</p><ol><li><strong><em>Managing available inventory</em></strong></li></ol><p>The first thing we need to do is checking the available inventory. How do we get the remaining inventory size?</p><p>If we query the database with aggregation like COUNT , firstly, we may need to have a serialisable isolation level for the transaction which affects performance. If we do not apply this isolation level, we may end up with phantom read and thought that we still have enough inventory this request, and then we sell more than what we have.</p><p>To handle this, we can use a counter with atomicity. Redis will be a good choice for atomic decrement when a request need to be processed.</p><p><strong><em>2. Buffer with message queue</em></strong></p><p>Processing a transaction could be quite complex and heavy. For example, automatically applying promotion based on user’s loyalty points.</p><p>Thus, let’s use message queue to buffer the request and let the service to process it at its own pace.</p><h4>Database</h4><p>Now, the number of request that reaches database is very much reduced to an acceptable number.</p><p>We can focus on designing better schema, optimising queries and maybe sharding the table.</p><h3>Discussion</h3><blockquote>So now I can directly copy this design to my project?</blockquote><p>NO. Firstly, it depends on your requirements. Secondly, you may not need to spend this much effort, there might be other better ways.</p><h3>Conclusion</h3><p>This post is a brief case study of flash sale system design. It provides a general guideline and possibly inspiration to people who is solving similar problem.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7481f6ede0a3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/developing-a-flash-sale-system-7481f6ede0a3">Developing a flash sale system</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Transfer learning with MXNet Gluon]]></title>
            <link>https://medium.com/hackernoon/transfer-learning-with-mxnet-gluon-8203005afafe?source=rss-96bde300b248------2</link>
            <guid isPermaLink="false">https://medium.com/p/8203005afafe</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[convolutional-network]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[mxnet]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Jason Xu]]></dc:creator>
            <pubDate>Sun, 07 Jan 2018 06:15:04 GMT</pubDate>
            <atom:updated>2018-01-08T19:11:41.787Z</atom:updated>
            <content:encoded><![CDATA[<p>A year ago, I started learning neural network with Tensorflow. The journey is not as smooth as I thought. Thanks to <a href="https://medium.com/u/592ce2a67248">Andrew Ng</a>’s online course and several books, I have a basic understand of the theory, however, when I try to apply it in real-life projects, the syntax and api of Tensorflow sometimes confused me (Maybe I wasn’t spending enough time with it).</p><p>To get early result for my project, I directly applied the Tensorflow computer vision api. However, when it came to customising models, it took me a long time get everything sorted.</p><p>Until one day, I found <a href="https://mxnet.incubator.apache.org/api/python/gluon.html">MXNet Gluon</a>.</p><h3>What is MXNet Gluon</h3><p>Gluon is an interface for MXNet — the deep learning framework supported by Amazon. Gluon is similar to other higher level api like Keras, Pytorch and Chainer. But it has its unique points to be loved:</p><ol><li>Imperative, and symbolic: Gluon enables you to enjoy the good part of both imperative framework and symbolic framework with its <a href="https://mxnet.incubator.apache.org/api/python/gluon.html#mxnet.gluon.HybridBlock">HybridBlock</a> . So you can develop and debug easily with your jupyter notebook, and enjoy the performance optimisation when you convert it to symbolic.</li><li>Simple API without compromising flexibility: Unlike Pytorch or Chainer, you don’t need to remember the output size of each layer. The API definition is very similar to Keras. You can extend and build your own block with ease.</li></ol><h3>What is transfer learning</h3><p>Transfer learning is a technique to reuse the learned representation of an existing model and apply it to a different but related domain.</p><p>The reason to use transfer learning is that it takes a long time and a lot of resources to train a neural network from scratch. Usually we use transfer learning in 2 ways:</p><ol><li>Initialise parameter with pretrained model</li><li>Use pretrained model as fixed feature extractor and build model based on feature</li></ol><p>Transfer learning as a topic itself can involve a long discussion. In this article, we will mainly look at using it to initialise parameters.</p><h3>Let’s start</h3><h4>Problem definition</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*9JKUeiZP2BLP0L9u-qb3Gw.jpeg" /><figcaption>husky or akita</figcaption></figure><p>Given a photo of our favourite pet dog, is it a husky or akita.</p><p>Why this problem? It’s better to work on problem that interests you and dataset should be easy to find. (They are cute and it’s easy to find their photo)</p><h4>Prerequisite</h4><ol><li>install MXNet: pip install mxnet</li><li>install Jupyter Notebook: pip install jupyter</li></ol><h4>Prepare Dataset</h4><p>Data source: google images by keyword husky and akita.</p><p>The dataset will be divided into 4 parts:</p><ol><li>sample: 16 images for development and debug</li><li>train: 70%, to train model</li><li>validation: 15%, to diagnose model, detect overfitting/underfitting and choose models if we have multiple versions</li><li>test: 15%, to evaluate the accuracy of the model</li></ol><p>MXNet provides a <a href="https://github.com/apache/incubator-mxnet/blob/master/tools/im2rec.py">im2rec.py</a> script to generate rec file, it requires a lst file to specify file locations and labels. The notebook for generating the lst file and rec file can be found <a href="https://github.com/MrXu/transfer-learning-with-gluon/blob/master/prepare-dataset.ipynb">here</a> .</p><p>After generating the dataset, your directory structure will look like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lN_F32pg3h11gjUrjEB0SQ.png" /></figure><h4>Build the model</h4><p>We will use <a href="https://arxiv.org/abs/1704.04861">MobileNet</a> for our transfer learning task. MobileNet is an efficient convolutional neural network architecture. It applies 3x3 depthwise conv and a 1x1 pointwise conv to replace regular convolution layer, which reduces computation complexity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7XhU6VXW9mq9uaWYsk5BAw.png" /><figcaption>regular convolution vs depthwise separable convolution (<a href="http://machinethink.net/blog/googles-mobile-net-architecture-on-iphone/">reference</a>)</figcaption></figure><p>Thanks to the community of Gluon, we have the MobileNets pretrained on ImageNet. Let’s explore a bit on it with Jupyter notebook.</p><pre>from mxnet.gluon.model_zoo.vision import mobilenet1_0<br>pretrained_net = mobilenet1_0(pretrained=True)<br>print(pretrained_net)</pre><p>Once you run it, you will find that the model consists of two high level blocks: features and output . As the output shape for ImageNet version is 1000, we need to create a model with output shape as 2.</p><pre>net = mobilenet1_0(classes=2)</pre><p>To reuse the weights of a pretrained model, we can directly assign it to the features block of the new model.</p><pre>from mxnet import init<br>net.features = pretrained_net.features<br>net.output.initialize(init.Xavier())</pre><p>That’s it ~</p><h4>Train the model</h4><p>Before training the model, let’s create the data loader for our husky &amp; akita dataset. We will use the <a href="https://mxnet.incubator.apache.org/api/python/image.html">image augmentation functions</a> provided by MXNet to generate new samples and help avoid overfitting.</p><pre>from mxnet.image import color_normalize<br>from mxnet import image</pre><pre>train_augs = [<br>    image.ResizeAug(224),<br>    image.HorizontalFlipAug(0.5),  # flip the image horizontally<br>    image.BrightnessJitterAug(.3), # randomly change the brightness<br>    image.HueJitterAug(.1)         # randomly change hue<br>]<br>test_augs = [<br>    image.ResizeAug(224)<br>]</pre><pre>def transform(data, label, augs):<br>    data = data.astype(&#39;float32&#39;)<br>    for aug in augs:<br>        data = aug(data)<br>    data = nd.transpose(data, (2,0,1))<br>    return data, nd.array([label]).asscalar().astype(&#39;float32&#39;)</pre><p>Now we can create a data iterator with the augmentations we defined.</p><pre>from mxnet.gluon.data.vision import ImageRecordDataset</pre><pre>train_rec = &#39;./data/train/dog.rec&#39;<br>validation_rec = &#39;./data/validation/dog.rec&#39;</pre><pre>trainIterator = ImageRecordDataset(<br>    filename=train_rec, <br>    transform=lambda X, y: transform(X, y, train_augs)<br>)<br>validationIterator = ImageRecordDataset(<br>    filename=validation_rec,<br>    transform=lambda X, y: transform(X, y, test_augs)<br>)</pre><p>Let’s define our training function.</p><pre>def train(net, ctx, <br>          batch_size=64, epochs=10, learning_rate=0.01, wd=0.001):</pre><pre>    train_data = gluon.data.DataLoader(<br>        trainIterator, batch_size, shuffle=True)<br>    validation_data = gluon.data.DataLoader(<br>        validationIterator, batch_size)</pre><pre>    net.collect_params().reset_ctx(ctx)<br>    net.hybridize()<br>    <br>    loss = gluon.loss.SoftmaxCrossEntropyLoss()<br>    trainer = gluon.Trainer(net.collect_params(), &#39;sgd&#39;, {<br>        &#39;learning_rate&#39;: learning_rate, &#39;wd&#39;: wd})<br>    <br>    train_util(net, train_data, validation_data, <br>               loss, trainer, ctx, epochs, batch_size)</pre><p>train_util function can be found <a href="https://github.com/MrXu/transfer-learning-with-gluon/blob/master/train.ipynb">here</a>. It’s usually reused, so I will not post it here.</p><p>There are some key points to highlight:</p><ol><li>hybridize : function that transforms your imperative model to symbolic model, and the computation graph is optimised for faster training.</li><li>Trainer : where we define our learning rate, optimisation function and weight decay</li></ol><p>With everything in place, we can kick start the training!</p><p>After 5 epochs, we can see that the training accuracy and validation accuracy both went up.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sXQZWPAbhP9pvNu0BMlFEg.png" /><figcaption>training process</figcaption></figure><h4>Test</h4><p>So we achieved 0.97 accuracy in training set, however, we can’t use training accuracy to evaluate a model. The reason is that this model maybe just overfitting the distribution of training data (Once I purposely overfitted training set and it goes to 99.9%, but it did poorly in real dataset).</p><p>To evaluate the performance of our model, we need to use our test dataset that is never used in training, model selection or parameter fine-tuning.</p><pre>test_data_loader = gluon.data.DataLoader(testIterator, 64)<br>test_acc = evaluate_accuracy(test_data_loader, net)</pre><p>The test accuracy is 0.93 , so our model is not as good as we thought.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/744/1*jjhhF9MpBMD04p3z4cXH7Q.png" /></figure><h3>Discussion</h3><blockquote>The validation accuracy reached 0.88 in first epoch, feels unreal</blockquote><p>Yes, the reason is that husky is an existing label in ImageNet and our dataset is not very big</p><blockquote>there’s always a gap between training accuracy and validation accuracy</blockquote><p>It shows that we are overfitting our model. We can applied more regularisation by increase weight_decay or we should try to get more training data.</p><h3>Conclusion</h3><p>This article shows you how simple it is to use MXNet Gluon for transfer learning. It is also a guide when you try to apply this technique to your own problem.</p><p>There are still many interesting topics I haven’t covered, such as customising block, building your own architecture and deploying models in different environments. I will try to cover them in future posts.</p><p>Source code: <a href="https://github.com/MrXu/transfer-learning-with-gluon">https://github.com/MrXu/transfer-learning-with-gluon</a></p><h3>Reference</h3><ol><li><a href="https://blog.keras.io/on-the-importance-of-democratizing-artificial-intelligence.html">On the importance of democratizing Artificial Intelligence</a></li><li><a href="http://cs231n.github.io/transfer-learning/">CS231n Convolutional Neural Networks for Visual Recognition</a></li><li><a href="https://mxnet.incubator.apache.org/api/python/gluon.html">MXNet Gluon documentation</a></li><li><a href="https://zhuanlan.zhihu.com/p/28648399">https://zhuanlan.zhihu.com/p/28648399</a></li><li><a href="https://arxiv.org/abs/1704.04861">MobileNets</a></li><li><a href="http://machinethink.net/blog/googles-mobile-net-architecture-on-iphone/">Google’s MobileNets on the iPhone</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8203005afafe" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/transfer-learning-with-mxnet-gluon-8203005afafe">Transfer learning with MXNet Gluon</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>