CT Wu

Leetcode concurrency #1226 The Dining Philosophers (in golang)

這是concurrency的最後一篇，前面已經試過幾種常見的同步模式，這次要解的題目是經典的哲學家問題，但處理的手法應該已經被很多教科書討論過了，不外乎引入服務生、搶到叉子就吃搶不到就等，和比較近期的用餐券換叉子。

這麼經典的問題教科書應該都有寫過我就大略描述下就好。總之，五個哲學家坐在同一張圓桌，每個人都有一碗吃不完的麵，但只有五支叉子放在人與人之間，要吃麵就一定要用兩支叉子，沒有兩支叉子就發呆。這裡有個變體，要接收一個整數，代表每個人至少要吃過幾次，例如：n=1，表示每個人都至少吃過一次就散會。

解法也很簡單，我選用最單純的搶叉子，每支叉子按順時鐘順序編號，每個人都要先拿編號小的才能拿編號大的，但放叉子要從編號大的先放，才能放小的。

每個叉子都是一個互斥鎖，小的先鎖再鎖大的，大的先解鎖才解小的。唯一要注意的一點是，吃完以後要看一下是不是每個人都吃過了，如果大家都吃過就準備結束散會；一定要在吃完的時候就看，因為這時候才是在critical section內，過了就要再搶一次，那沒必要。

有趣的一點是，我在Leetcode的playground跑這段code，會發現有些哲學家餓到不行，會狂搶叉子，導致結束的時候某人大概續了幾千次麵，真是個大胃王。

Originally published on Medium

Leetcode concurrency #1195 Fizz Buzz Multithreaded (in golang)

從開始刷concurrency到現在已經接觸過，Event、Lock和Semaphore，這題會用到另一個同步處理也會使用的技術：Barrier，Barrier是指當所有做事的人都必須將queue內的event全部依序執行，例如：ABC三個人同時拿queue[0]做，等大家都做完後，三人繼續拿queue[1]，依此類推。

先看一下題目，看完就會知道為什麼一看就知道要用Barrier。有一個class有四個method(又來了)，必須將四個method放在四個thread上執行，這四個method分別是：在3的倍數時印fizz、在5的倍數時印buzz、在15的倍數時印fizzbuzz，最後是上面都沒中就印數字。

因為golang沒有實作自己的Barrier，我本來想用WaitGroup來做，但怎麼試怎麼怪，最後決定WaitGroup還是維持他單純的用途就好：等所有人做完。那麼，就需要實作一個Barrier，這邊可以使用sync.Cond。如果寫過linux C應該會對pthread_cond_t有印象，這兩個是等價的。

當有了Barrier的實作，這題就一點也不難，就是分別判斷能不能整除3或5來決定個別要做甚麼，把輸入的整數丟進去大家一起一個一個做就好。

Originally published on Medium

Leetcode concurrency #1117 Building H2O (in golang)

今天的題目掙扎了一下，主要是對golang沒這麼熟，花了點時間試誤，最後還是選擇土法煉鋼的解。前幾天，我們試過同步處理中的Event和Lock，今天依然是解同步處理的問題，這次嘗試用號誌來解決。

題目解析：給一串字串僅包含H和O兩種字母，而且H的數量一定要是O的兩倍。接著起一堆thread，每個thread只可能會有印出H或印出O這兩個功能，目的是要將輸入的字串整理成HHOHHOHHO…的序列。

這題的難處在於一狗票的thread同時跑起來，要能夠快速知道甚麼時候開始印H又哪時候要印O。看到題目的第一直覺就是semaphore，只要起兩個semaphore，一個設2來決定H、另一個也設2來決定O就可以了。但是，碰到幾個問題：首當其衝的是，golang的sync裡沒有semaphore的實作，必須使用golang.org/x/sync/semaphore下的Weighted；另一個問題是，在這個package底下實作的Release不會空等，在沒有Acquire足夠數量的前題下，直接使用Release就panic。

semaphore: released more than held

正常的流程是H thread，先Acquire(H1)，若是可行，就印出H然後，Acquire(O1)來通知O開始跑；而O thread的流程是，先Release(O2)，若是可行，就印出O並且Release(H2)來告訴下一輪的H。但用原來的Release，O在第一次Release(O2)就會炸。因此我把整個package拷貝過來，並且修改Release的作法，做成類似自旋鎖的概念。

中間一大段拷貝可以略過不用看，幾乎都和原來的一樣，除了Release被我大改之外。當Release的問題解決之後，其實解法就和剛剛描述的流程一樣，從code可以很清楚的看到hydrogen和oxygen的實作都很簡單。

Originally published on Medium

Leetcode concurrency #1116 Print Zero Even Odd (in golang)

之前寫了#1114和#1115，都是用channel互相通知，叫正確的人起來做事；這在golang中算是很常見的作法，但這次的題目我想用比較傳統的方式解決，我將題目轉成一種producer-consumer的架構來解。

照慣例，題目解析：有一個class內有三個method，分別是印出0、偶數和奇數，跑三個thread各run一個method，輸入一個n要與0依序印出。舉例來說：n = 5，印出來的結果是：0102030405，依此類推。

這次解決的方法有點偷懶，正常的producer-consumer架構是要用一個queue，把東西丟入然後由consumer取出運算，但我只用兩個整數表示這個隊列，就沒去處理enqueue和dequeue的邏輯。

相比前面的解答算是再長了一些，這次用到一個互斥鎖來同步狀態，當要存取狀態時要取得鎖才有辦法繼續。也有在判斷條件內加入中止條件，也就是狀態是-1時就結束迴圈。用到鎖就比較繁複，有時間的話會試試看有沒有辦法把解鎖的地方處理的更漂亮。

若是consumer要做的事都一樣，這樣的寫法就足夠了，起多個goroutine可以有效加速消化。但是這次的題目會有一個edge case：因為是三人搶一鎖，而且每個人各司其職，所以有可能會starvation。舉例來說：當狀態curr = 2，理當由even接手，但若不幸的是，even搶不到鎖，變成是zero和odd兩個人互相把鎖丟來丟去，就空轉了。所以解答改良版如下：

變得更長了！兩個重點：一個是使用RWLock而不是互斥鎖，這樣在讀取狀態時人人有機會，不會發生搶不到的情況；其二，讀取鎖放掉後，若要繼續做事需要拿寫入鎖，但在拿到寫入鎖後，還是必須再判斷一次狀態，因為鎖放掉後就有可能有人改變狀態（雖然這題不會發生這種事，因為各司其職）。

Originally published on Medium

Leetcode concurrency #1115 Print FooBar Alternately (in golang)

繼上篇Print in Order之後，我們繼續挑戰concurrency，這次難度會從easy變成medium，但我覺得還是很簡單。

一樣先從題目解析開始，跟1114類似，一個class有兩個method，一個會印n次foo；另一個會印n次bar，兩個method個別分別會在不同的執行緒執行，希望最後印出來的結果是foobar重複n次。

跟上次的前題差不多，因為沒有golang的內建支援，所以main和run都是我的假設。

其實這次的解題思路跟上次87趴像，也是用兩個unbuffered channel互相等待互相指揮，唯一一個差別是channel的開始和結束需要做些判斷，不然會deadlock。所以foo在開始的時候不等，而bar在結束的時候不送。這樣就打完收工。

Originally published on Medium

Leetcode concurrency #1114 Print in Order (in golang)

最近在點新技能，想把golang的技能樹點高點。看了些open source，也練習寫了些side project，但總是有點偏門；感覺有甚麼基本沒有掌握好，所以決定一天至少一題，來刷刷leetcode。

先從concurrency下手，因為golang的強項就是concurrency，之後有閒會再寫別種類型的題目。

先從題目解析開始。題目給得很簡單：有個class有三個method，分別會印出一二三，這三個method會根據使用者的輸入參數來決定跑起來的順序，但無論順序是甚麼，最後印出來的結果都要是一二三。

答案如下。再解題前有一個前提必須要先申明，leetcode目前沒有支援golang，所以沒有一個基本的程式框架可以擴展，所以答案內有些地方是硬湊的，例如：為什麼用struct？因為題目寫的是class所以不選interface；為什麼參數用function arguments而不是stdin？因為沒有框架，不知道要怎麼塞。另外，golang的struct不像是python的class有init，所以初始化的code直接寫在run裡。

解題思路是，反正二要等一，三要等二，那就直接起兩個unbuffered channel，在一做完後通知二，二做完通知三，這樣就完事了。答案寫得有點死，可以再改進，例如：不應該寫死channel，而應該用channel陣列，這樣可以透過index知道要等哪個和要通知哪個，但題目的function都寫死了，我想也不用over enginnering，直接定死吧。

Originally published on Medium

To make a small enough container image is a complicated job, especially Python.
We can use multi-stage build process and virtualenv to reduce the overhead from the build and pip install.
However, some Python libraries use the runtime C library, we have to overcome this issue; otherwise the package won’t work.
I will take TA-Lib as an example to show how to get everything done correctly.

Here is an example, and there are 5 points should be aware:

1. Choose a small enough base image; nevertheless, avoid using alpine. The reason is explained by this article: https://pythonspeed.com/articles/alpine-docker-python/
2. Multi-stage is a good idea to reduce the overhead of building processes. In addition, applying virtualenv makes things much more easily. Therefore, install all Python packages into /opt/venv.
3. Now, we can try to build TA-Lib from the source. You have to specify the installation path to /opt/venv as well while configure.
4. Because we moved the default library path to /opt/venv, we need assign the global option or the build option to pip to let it know the library path.
5. Finally, remember to provide the LD_LIRARY_PATH to let python know where are the shared libraries.

Following the above procedure, the image size will be around 250MB. This is pretty small.

Originally published on Medium

Socket.io with TLS

After the last article, this place has not been updated for a long time. In order to avoid being a shopping list blog, I try to write some useful information or at least, provide some learning journeys. In the last article, I want to build an on-line game for interactive RPG, you can spell some magics or attack to the enemy. However, if the interaction is time-sensitive, the server has to push events to the client, i.e., our web page to ensure the operation works. Moreover, the communication between the server and the client must be in secure. Therefore, I want to use websocket over TLS to achieve those goals.
Nevertheless, websocket still has some shortages like group management. If the function of the game becomes more growing, e.g., multi-player fight together with the same enemy. The game server must have a more comprehensive solution to handle the group management. The final approach is socket.io.

Socket.io is a protocol based on websocket, and in addition, socket.io also applies the room concept to deal with emitting a message to multiple receivers.

First of all, I have no idea about the https, and I don’t know what is the certificate and what is the CA. So, this article will not introduce those details about the protocol, I will focus on how to build a workable server.

Now, you have a private key(server.key) and a certificate(server.crt). The suffix is no meaning, you can use what you want. If you get a file from somewhere, and you don’t know what it is, you can open it via the text editor, and then, you will see the purpose at the first line.

How to build a socket.io server

There is a great example written in python at the flask socket.io. The example/app.py demonstrates how to join/leave a room, broadcast a message, and be a echoed server. Nevertheless, this example does not tell you how to enable the TLS and become a https server. The reason behind it is very simple, you only need the original function in flask. If you want to enable the TLS, you have to replace the line:

socketio.run(app, debug=True)

to:

socketio.run(app, debug=True, ssl_context=(‘server.crt’, ‘server.key’))

Then, the server will run in https. However, you maybe want to improve the scalability for this server by using asynchronous mechanism. You can install the gevent and gevent-websocket. It is worth noting that you have to replace the mentioned line to:

socketio.run(app, debug=True, certfile=’server.crt’, keyfile=’server.key’)

Because the gevent cannot support the parameter, ssl_context. Things are almost done. Finally, you can use gunicorn and nginx to further expand the scalability and reliably like:

gunicorn -k geventwebsocket.gunicorn.workers.GeventWebSocketWorker -w 1 — certfile server.crt — keyfile server.key -b 127.0.0.1:3000 app:app

I will introduce how to benchmark the socket.io next time, especially the amount of concurrent clients. See you.

Originally published on Medium

Because my native language is Chinese, I try to find a Localization(L10n) package to translate the display from English to Chinese. There are many package found in Node.js; however, I need a standalone package can be executed only on the browsers due to reducing traffic. The final answer is webL10n. It is easy to use, and it not only can do the translation in HTML but in JavaScript. That is a total blast!

To use webL10n, the first thing must be done is set the language; for example:

1

<script type=”text/javascript”>

1

function onLocalized() {

1
2

var l10n = document.webL10n;   
l10n.setLanguage(‘zh-tw’);

1

}

1

document.webL10n.ready(onLocalized);

1

</script>

The zh-tw is the part of the path in the resource file such as data.zh-tw.properties. While the page is loaded, the language of this page will be set to the zh-tw. After that, you can use the translation in everywhere in the page.

1

var _ = document.webL10n.get;

1

console.log(_(‘magic’))

The underscore function _ is the convention while translating. So, get the underscore function, and do the translation in the place you want. The webL10n is the simplest package I have ever found.

Originally published on Medium

JavaScript Format String

The format string is composed of some operands and made to generate a real string by arguments. There are many programming language with the official format string method; for example, in C, it can use sscanf within %d, %s, %f, etc. to stand for the type from the auguments; similarly, in Python, it can use string.format within ${0}, ${1}, etc. to represent the order of the coming arguments.

Fortunately, in JavaScript, there is a method similar to those modern languages. However, the format string is a little different from the general string. The difference is using the graven accent instead of the quotation marks. The usage is like the following:

1

var a = 10;

1

var b = ‘hello world’;

1

var s = ` test ${a} ${b}`;

Now, you can use the string be composed of the arguments.

Originally published on Medium