分布式Streaming Data Processing - Samza

作者：包子黑旋风老师

现在的主流的互联网应用越来越依赖streaming data来提供用户一些interesting statistics insights。以linkedin为例，最近90天有多少人看过你的linkedin profile。看过你profile的人都是什么job title，他们都在那些公司工作。如下图，你应该如何实现这个功能呢？

相信大家都听说过page view event，就是用户每次打开网站上的某个页面发出来的tracking event，各个大公司一般用这些event来做一些统计分析，business analysis。大家一般会利用一些吞吐量大的分布式消息系统来存储这些event，例如kafka。这是因为对于一些popular的网站，每天可能会有上亿或者10亿的page view event。我们可以利用对这个event的处理来实现我们之前提到的功能。

通常有两种方法可以实现以上的功能，一个是通过hadoop map reduce job，或者更抽象的hive pig query来实现这样的统计功能。但是这个方法有一个明显的劣势，就是处理速度慢，很难做到事实更新。对于我们以上的功能要求或许这个方法没有任何问题，因为我们只关注过去90天的统计信息而且不要求显示当天信息。但是今天我们要探讨另一个实现方法，利用多streaming data processing做到实时统计更新。其实有好多功能是需要事实更新的，例如search index update，twitter或者facebook一些hot topic/trent的发现。

1. Stream Data Repartition

我们可以通过对streaming data的repartition来实现同一个用户的page view events都聚集到了同一个机器上去处理，这样我们可以做到每个用户的统计数据都是准确的。这个功能基本所有主流的streaming data处理框架都支持，例如，kafka + samza，aws kinesis，storm。

2. Streaming Data Join

我们可以看到我们需要根据viewer的职位名称或者公司名称来做统计，但是我们的page view event只有viewer的id，没有职位或者公司这些信息，那我们改怎么实现呢？

一个非常简单的思路就是让我们的streaming processor去call profile的api来拿到职位或者公司名称的信息。这样子做有几个非常明显的劣势。1. 如果streaming processor停止工作半个小时或者更长时间，在重启streaming processor的时候由于积累了大量的未处理的events，streaming processor会flood我们之前说过的profile api。2. Streaming processor每次通过network来call另外一个api会增加额外的latency。3. 很难做到online和offline的isolation，因为这个统计功能还是属于offline或者nearline data processing，我们不希望因为这个功能影响了用户查询或者修改profile信息。比如第一个case发生的时候。

另一个思路就是可以加cache，来cache profile的查询request。但是这样子也有一个劣势，如果TTL设的很大，很难做到cache的数据是事实更新的，如果TTL设的特别短，cahe又基本不起什么作用，而且增加额外的network cost。

这里我们介绍一个samza引进的一个新功能，stream joining。我们可以join page view event和profile edit event，然后解决以上两个方案的劣势。我们的stream processor需要同时听两种events(PageViewEvent and ProfileEditEvent)，然后对这两种event进行同样的partition both by viewer id，对于profile edit events，我们可以在stream processing机器上建立一个小的数据库来存储profile的实时数据，这样子我们可以对viewer进行快速查询来enrish page view event with viewer job title和company information。然后我们再将enriched的page view event重新partition by user id。然后进行统计。这样子我们就做的了profile数据的isolation，也解决了network call的latentcy cost。

Leetcode solution 291: Word Pattern II

Problem Statement 

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Example 1:

Input: pattern = "abab", str = "redblueredblue"
Output: true

Example 2:

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true

Example 3:

Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false

Notes:
You may assume both pattern and str contains only lowercase letters.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

It is quite similar to Word Pattern and Isomorphic String problem, where we would keep a mapping from char to a string while also ensure there would be a one to one mapping, i.e., bijection mapping. The tricky part is it seems there are way many combinations of the mapping, how can we efficiently solve them?

Maybe we could list all the combinations? Maybe we could use DP since it is string related and only ask for true/false result?

How to list all combinations? Think about this way, let's say you have pattern = "aba" and str = "redbluered", since one char in pattern can map to any string length >= 1 in str, it is equivalent to divide up str into 3 parts (length of pattern) and check all cases. For instance, the cut of the words is like below:

1. r | e | d b l u e r e d
2. r | e d | b l u e r e d
3. r | e d b | l u e r e d
4. r | e d b l | u e r e d
5. r | e d b l u | e r e d
6. r | e d b l u e | r e d
7. r | e d b l u e r | e d
8. r | e d b l u e r e | d
9. r e | d | b l u e r e d 
10. r e | d b | l u e r e d 
11. r e | d b l | u e r e d  
12. r e | d b l u | e r e d 
13. r e | d b l u e | r e d  
14. r e | d b l u e r | e d 
15. r e | d b l u e r e | d  
16. r e d | b | l u e r e d  
17. ..... 

 In general, if the length of pattern is M, the str length is N, the time complexity of this brute force method is O(N^M), more accurately, it should be

cmn=m!n!(n−m)!

DP solution does not work since we cannot easily get a deduction formula :(

Solutions

Brute force list all the combos

For each character in pattern, try to map any possible remaining strings in str from length 1 to the end. During this process, need to make sure the string mapping is bijection (no two chars in pattern map to the same string in str) and if a mapping has been seen before, continue use that mapping.

A DFS recursion would be the implementation. A few caveats in implementation

• Remember to reset the map and set after recursion returned false
• When there is a bijection mapping, should continue instead of directly break

Time Complexity: O(N^M), or C(N^M) to be exact. Pattern length is M, str length is N
Space Complexity: O(M), Pattern length is M, str length is N. We use a map and a set to store the lookup, but at one time, the map should not exceed the pattern size, so is the set

References

• Leetcode word pattern problem solution
• Leetcode isomorphic string problem solution 

Leetcode solution 205: Isomorphic Strings

Problem Statement 

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Note:
You may assume both s and t have the same length.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

A relatively straightforward problem, very similar to Word Pattern. All we have to do is check the one to one mapping from string a to string b, also it needs to maintain a bijection mapping (meaning no two different characters in a should map to the same character in b)
 

Use bijection mapping

Check character one by one from a and b. If char in a hasn't been seen before, create a one to one mapping between this char in a and the char in b so later if this char in a is seen again, it has to map to b, else we return false. Moreover, need to make sure the char in b is never mapped by a different character.

An explanation int the video

Solutions

Time Complexity: O(N), N is the length of string a or string b
Space Complexity: O(N), N is the length of string a or string b because the hashmap and set we use

References

• Leetcode word pattern problem solution

Leetcode solution 290: Word Pattern

Problem Statement 

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

A very simple problem thus normally can solve it in multiple ways.
 

Encode string and patterns then compare

Since we are comparing "patterns" here, one straightforward way is encode the pattern into a string, then use the same encoding algorithm to encode the str array into a string, then compare the string.

What encoding should we choose? Well it's not really an encoding per se. What I did is just convert any word or character to a character staring with ('a' + an index). If we see this character before, we just directly return from the hash map lookup. For example, "duck dog dog" would be encoded as "abb" while "bcc" would also be encoded as "abb".

Use bijection mapping

Note in the problem description it mentions it is a bijection mapping (i.e., a one to one mapping).
As shown in the graph below, you see the differences between injection, surjection and bijection. That said, bijection does not allow duplicates. We can build a one to one mapping between the pattern and string, since it's bijection, if two characters in the pattern map to the same string, then it's not a valid bijection, therefore return false.

Ref: https://en.wikipedia.org/wiki/Injective_function

Solutions

Encode string and patterns then compare

Time Complexity: O(N), N is the length of pattern or string array, we loop it 3 times, but still O(N)
Space Complexity: O(N), N is the length of pattern or string array, we need the extra map and string to store the results

Use bijection mapping (Recommended)

There is also a clever implementation like below. The key point is use the index to compare, if there is duplicate index, meaning there are two keys already mapped to the same value. Also, remember java put() returns a valid, not a void :) 

Time Complexity: N is the length of pattern or string array
Space Complexity: O(N), N is the length of pattern or string array, we need a map regardless

 

References

• Leetcode discussion with the clever implementation

Leetcode solution 1036: Escape a Large Maze

Problem Statement 

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square.  Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves.

Example 1:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation: 
The target square is inaccessible starting from the source square, because we can't walk outside the grid.

Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true
Explanation: 
Because there are no blocked cells, it's possible to reach the target square.

Note:

1. 0 <= blocked.length <= 200
2. blocked[i].length == 2
3. 0 <= blocked[i][j] < 10^6
4. source.length == target.length == 2
5. 0 <= source[i][j], target[i][j] < 10^6
6. source != target

Hints

• If we become stuck, there's either a loop around the source or around the target.

• If there is a loop around say, the source, what is the maximum number of squares it can have?

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

At first, I am puzzled why this problem would be a hard one. It seems simply applying a BFS would get the answer. So here we go.
 

Brute force, simple BFS

Of course it will hit memory limit because I am allocating a 2-dimensional visited array. Assume boolean is 8 bit -> 1B, 1 Million * 1 Million = 1TB, OMG, immediately using a set instead.

P.S. fun fact, you can use this method to test how much memory leetcode allocate to this problem, you can use binary search and memory is around 300MB

However, this would start hitting Time Limit Exception. Now I begin to notice a few constrains, e.g., the block size is only 200 while the grid is 1M*1M. Simply going from source to target worst case would cause a timeout.

Next thought would be does it help if we sort the block array? While we are doing the BFS, if the block is already larger/smaller than the max/min of the block, we can early stop. However, this won't help if we simply place a block near the target. Also, this would be a nightmare to implement.

Check block loops on source and target

Following the two hints, it would be natural to come up with this idea. Given such huge contrast between the block size (0,200) and the grid size (1M, 1M), all we need to do is to check if there is any loops built by block on source and target b/c if there is a loop, we cannot explore outside of the loop. However, notice if target and source are in the same loop, then we are fine.

There are two ways to early stop this loop checking. One way is to count the BFS steps, the other way is to follow the hints, given 200 blocks, what's the max area it can cover. Given the length 200, Fig 2 in the below graph can result in the largest area. Therefore, we can early terminate the BFS search once we covered more than 19900 blocks. (We can relax this a bit to 20000, doesn't matter)

• Fig 1 area = 100 * 100 = 10000
• Fig 2 area = 1 + 2 + 3 + ... + 199 = (1+199)*199/2 = 19900
• Fig 3 area = 1 * 200 = 200
• Fig 4 area = 790 (2*Pi*R = 100, thus R = 15.92, Pi * R^2 = 790 )

Solutions

Brute force, simple BFS

Time Complexity: O(N), N = 1M * 1M, essentially need to cover the entire huge grid
Space Complexity: O(N), N = 1M*1M, essentially all the nodes need to be put to visited set

Check block loops on source and target

Time Complexity: O(N), N in terms of block size
Space Complexity: O(N), N in terms of block size

 

References

• Leetcode discussion using BFS steps 
• Leetcode discussion using BFS area

Alibaba Tech Festival - Silicon Valley & Game of Thrones Season 8 Finale

Alibaba Tech Festival - Silicon Valley

Alibaba, Jack Ma's empire has always been very active in Silicon Valley, trying to recruit the top talents. Traditionally it was mainly focused on somewhat cutting edge technologies. e.g, big data in the old days (while everyone is talking about it), cloud, and nowadays machine learning / AI of course. However, this time, the Taobao Team (淘系技术) was in town and shared some of the interesting projects they are working on.  This is mainly due to the early vision shifts from Jack Ma that technology should drive business instead of the old vision, business is key, technology plays only a secondary supporting role.

What is Taobao(淘宝), TMall(天猫) & Xianyu (闲鱼)?  

Taobao is the largest e-commerce platform in China, with over 600M monthly active users. Think about the size 1.4B Chinese, 1B has internet access, almost half of entire China is using Taobao. It is mostly C2C where TMall is B2C.They also have Xianyu(闲鱼), which is a second hand marketplace. 

Just to give another prospective, Alibaba single-handedly created a new holiday in China called Singles' Day (光棍节，双十一), where single day it creates $30B worth of spending.

Alibaba Tech Festival at Silicon Valley

A Swag, everyday struggle, but work makes me happy 😂

New Retails (新零售)

Alibaba is one of the pioneers of e-commerce innovation and they have proposed this new concept called "New Retails". So what exactly is the new retails idea? We lived through shopping from offline to online, then online back to offline due to certain limitations. E.g., you might want to try on lots of clothes or makeups before you buy them, and online shopping cannot really satisfy that. Moreover, some people might want to hear other's opinions whether the clothes looks good or not before they buy it, they have to be in store and talk to others. Therefore, the new retails idea is digitizing every thing in store and you can shop offline, but you can view all the items info online, place the order online and expect the items to be shipped home in a few hours.

Below is a very good article on the store Alibaba built in Hangzhou.
https://www.alizila.com/future-of-retail-happening-in-china/

A few interesting things I learned from the talk

• Taobao is also all in in AI, so that everybody's shopping / recommendation experience is highly customized.
• Wechat is No.1 chatting app in China, and Taobao's chat is actually No. 2. Taobao also has a large video live features for sellers to better engage the buyers, it's literally like a TikTok on its own 
• Alibaba has built extensive tools for sellers to manage all their inventory, brand, marketing etc. 
• They have tried many ideas in the Fashion AI field. I used to think having 3D AR technology could perfectly solve the clothes fitting requirement, apparently based on Alibaba that's not the case. That's why they use image recognition to split the body into three parts and try different clothes/dress match up.

• Alibaba is a giant company, if you look at their org chart, it's crazy 

Game of Thrones Season 8 Finale

完全的题外话，这个剧我追了8年，md最后给了我们这个一个沙雕的结局，当大家是弱智呀？！这才是官方实锤的版本, 我也是这么认为的，当年2017年这个版本所谓被黑客泄露之后，我读了觉得完全靠谱，大家可以看看，欢迎讨论
https://www.youtube.com/watch?v=U435sekPlxg

References 

• 阿里铁军这本书不错，概括了阿里的文化
• 阿里新零售的文章