CT Wu

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

Yesterday, I told I want to develop a game, and I draw a blueprint:

The game is web based and like a RPG. The player can control a character with several skills, and those skills come from his job. There are two kinds of jobs: attack by weapon or by magic. The player can pick 8 skills on the desk and fight to an enemy. If you win this enemy, you can get some experiences, money, and items. The goal of this game is to defeat the final boss.

The code flow is like:

To reduce the traffic between the frontend and the backend, the game loop is in browser, but the status and gaming engine are in backend. Therefore, the backend can determine what the enemy you encounter and what rewards you will receive.

The communication between the browser and the backend is session, and I will use an encrypted cookie to keep the game states. However, I am not sure this method is secure enough or not. If you have the better idea, please tell me.

Originally published on Medium

Hi guys,

I come from Taiwan, a free and kind country, and work in an international company. I had been an embedded engineer and coded in C/C++, but now I am a backend developer with Python. No one around me can discuss technology, e.g., machine learning, web development, or even programming. So, I try to find some people having the same habit in computer science from the Internet. On the other hand, I need practice my English to work with foreigners from our branch office.

I will attempt to update my stories about my side projects every week. Actually, I will design and develop a web game by using HTML/CSS/JavaScript and Node.JS. In addition, if I find something interesting, I will share with you. Therefore, follow me and become my friend. At least, please point out my English mistake, and this is very helpful to me.

Thank you for your reading.

Originally published on Medium