Giới thiệu

Builder Pattern là một pattern trong cuốn Design Pattern của “Gang of Four”. Mục đích của Builder Pattern như sau: Separate the construction of a complex object from its representation so that the same construction process can create different representations (tạm dịch: tách rời quá trình tạo object với nội dung và cấu trúc bên trong của nó, nhờ vậy tương ứng với một quá trình tạo object có thể có nhiều cách tạo nhiều thể hiện khác nhau.)

Bên cạnh đó, Builder pattern còn được dùng để giải quyết một vấn đề thường gặp trong quá trình test: cách nào tốt nhất để tạo những object có quá nhiều optional parameters, trong khi tạm thời một số parameter ta muốn để giá trị default, giá trị của parameter này không ảnh hưởng gì lắm đến algorithm hay flow của chương trình. Bài viết này sẽ trình bày phương pháp sử dụng Builder pattern này.

Ví dụ

Ta lấy ví dụ ta có một class quản lý sách, với các trường như sau: tiêu đề, tên tác giả, thể loại, năm xuất bản, ISBN. Để phục vụ việc tạo một object thuộc class này, ta nghĩ đến việc tạo một constructor như sau:

1
2
3
4
5
6
7
8

 public Book(String title, String author, Genre genre, GregorianCalendar publishDate, String ISBN)
  {
      this.title = title;
      this.author = author;
      this.genre = genre;
      this.publishDate = publishDate;
      this.ISBN = ISBN;
  }

Và trong chương trình, để tạo một object Book, ta gọi:

1

Book book2 = new Book("Core Java", "Cay Horstman", Genre.TECHNOLOGY, new GregorianCalendar(2012,12,7), "0137081898");

Ta thấy, với cách tạo object như trên, có một số nhược điểm như sau:

• Ta bắt buộc phải khai báo tất cả các parameters, không có giá trị default. Ta sẽ bị buộc phải set cả những parameters mà ta không quan tâm khi thực hiện test object.

• Đoạn code khá khó hiểu khi ta chỉ khai báo giá trị của parameter và truyền vào constructor. Người đọc sẽ phải đếm vị trí của parameters, soi vào trong khai báo constructor của Book.java để biết giá trị này là gán cho parameter nào. Với ví dụ trên, chỉ có 5 parameter, nhưng với những class phức tạp có nhiều parameters hơn nữa, việc khai báo như trên rõ ràng không tốt về mặt code visibility.

• Xuất hiện nhu cầu tạo object với các constructor với bộ tham số đầu vào khác nhau. Như ví dụ ở trên, ta muốn tạo object nhưng không muốn nhập thể loại, hoặc không muốn nhập năm xuất bản, … dẫn đến rất nhiều phiên bản constructor khác nhau.

Hoặc bạn có thể khai báo theo một cách thứ hai, theo kiểu JavaBean như sau: tạo một constructor default, không đối số, ví dụ như Book(), sau đó thì tạo một loạt các setter để nhập các tham số cho parameter. Lúc đó thì code cho từng đối tượng sẽ như sau:

1
2
3
4
5
6

Book book = new Book();
book.setTitle("Core Java");
book.setAuthor("Cay Horstman");
book.setGenre(Genre.Technology);
book.setPublishDate(new GregorianCalendar(2012,7,1));
book.setISBN("0137081898");

Nhưng cách này lại có nhược điểm là: vì việc tạo object bị kéo dài qua nhiều câu lệnh, có thể object sẽ bị rơi vào trạng thái unstable (ví dụ như ta quên mất set publishDate, như thế book sẽ không có giá trị cho publishDate !).

Để khắc phục những nhược điểm trên, có một phương pháp sử dụng Builder pattern như sau: Thay vì tạo object mong muốn trực tiếp, ta gọi một static factory với các tham số bắt buộc, nhận về một builder object. Sau đó gọi các setter method dể đặt các tham số tùy chọn. Cuối cùng gọi build method, tạo ra object. Để dễ hiểu hơn, ta quan sát ví dụ sau:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

public class Book {
  public enum Genre {FICTION, NONFICTION, TECHNOLOGY, SELFHELP, BUSINESS, SPORT};
  
  private String title;
  private String author;
  private Genre genre;
  private GregorianCalendar publishDate;
  private String ISBN;
  
  public static class Builder
  {
      //required params
      private String title;
      private String author;
      
      //optional params
      private Genre genre = Genre.FICTION;
      private GregorianCalendar publishDate = new GregorianCalendar(1900,1,1);
      private String ISBN = "000000000";
      
      public Builder(String title, String author)
      {
          this.title = title;
          this.author = author;
      }
      
      public Builder genre (Genre val)
      {
          this.genre = val;
          return this;
      }
      
      public Builder publishDate(GregorianCalendar val)
      {
          this.publishDate = val;
          return this;
      }
      
      public Builder ISBN(String val)
      {
          this.ISBN = val;
          return this;
      }
      
      public Book build()
      {
          return new Book(this);
      }
  }
  
  public Book(Builder builder)
  {
      title = builder.title;
      author = builder.author;
      genre = builder.genre;
      publishDate = builder.publishDate;
      ISBN = builder.ISBN;
  }
  
  @Override
  public String toString()
  {
      return "Title: " + title + ", author: " + author + ", genre: " + genre.toString() + ", publish year: "
                  + publishDate.get(Calendar.YEAR) + ", ISBN: " + ISBN;
  }
  
}

Lúc đó ta có thể tạo Book object bằng cách sau:

1
2
3

     Book book = new Book.Builder("Effective Java", "Joshua Bloch")
                      .publishDate(new GregorianCalendar(2008,05, 28))
                      .build();

Ta thấy, cách tạo object này có ưu điểm hơn so với cách dùng constructor thông thường:

• Không cần phải khai báo những parameter nào mà ta tạm thời chưa quan tâm. Những parameters đó sẽ nhận giá trị default. Trong ví dụ trên, ta đã bỏ qua khai báo cho genre và ISBN. Chúng sẽ nhận giá trị default: genre = FICTION, ISBN = “0000000000”.

• Ta thấy rõ là giá trị nào là gán cho parameter nào. Ví dụ: publishDate(new GregorianCalendar(2008,05, 28)) là gán giá trị cho parameter ngày xuất bản.

• Thứ tự của các method là không quan trọng. Ta có thể gọi các method để update thêm các giá trị cho các parameter theo thứ tự tùy ý. Object sẽ chưa được tạo cho đến khi gọi build(). Do vậy, builder rất dễ sử dụng và giúp ta tránh khỏi những sai lầm không mong muốn đối với thứ tự parameter.

Kết luận

Bài viết đã giới thiệu cách sử dụng Builder Pattern để việc tạo object trong quá trinh test được dễ dàng hơn, đồng thời khiến đoạn code được sáng sủa hơn về mặt trình bày.

Tham khảo

• Effective Java - Joshua Bloch

• Design Patterns - Elements of Reusable

Bài toán sinh unique ID

Unique ID được sử dụng để phân biệt các đối tượng khác nhau. Ví dụ primary key là một unique key đặc biệt dùng để phân biệt các row trong table.

Bài viết giới thiệu một số phương pháp sinh 64 bit unique ID.

Một số giải pháp sinh unique ID

• Nếu số lượng dữ liệu nhỏ, ta có thể sử dụng ID kiểu Integer và set cho nó thuộc tính auto increment.

Ưu điểm: đơn giản, dễ làm.

Nhược điểm: số lượng ID bị giới hạn (2 ^ 32 = 4294967296) và đặc biệt cách làm này không scale. Để đảm bảo tính duy nhất, tại một thời điểm, chỉ có thể sinh ra đúng một ID mà thôi.

• Sử dụng UUID - UUID là một giá trị 128bit, tuỳ vào thuật toán xây dựng UUID, có thể dựa trên Mac Address của máy.

Ưu điểm: scalable, distributed. Tại một thời điểm có thể sinh ra nhiều ID khác nhau, thậm chí client cũng có thể sinh ID mà vẫn đảm bảo không bị trùng lặp với server

Nhược điểm: sử dụng 128 bit, một số hệ thống phải lưu trữ dưới dạng char, tốn tài nguyên và index

64 bit unique ID trùng hoà giữa 2 cách trên, đảm bảo số lượng ID sinh ra là đủ lớn, đồng thời có thể lưu trữ dưới dạng dạng Big Int

Một số phương pháp sinh 64 bit unique ID

1. Twitter snowflake Snowflake là thrift service sử dụng Apache ZooKeeper để liên kết các node và sinh ra 64bit unique ID. Mỗi node là một worker, các worker được đánh số khác nhau

ID được sinh ra theo công thức

• time - 42bit (được tính bằng epoch)
• worker id - 10 bit (số worker có thể lên đến 1024)
• sequence number - 12 bit (number được tăng liên tiếp, đảm bảo tại một thời điểm, mỗi worker có thể sinh được 4096 ID)

Ở phần tiếp theo, chúng ta sẽ implement thuật một service sử dụng thuật toán trên để sinh ID

2. Instagram 64bt ID

Instagram sinh ID dựa vào posgresql schema. Thuật toán sinh ID tương tự như snowflake, mỗi ID 64 bit bao gồm

• time - 41 bit (time epoch)
• shard_id - 13 bit (so shard id lên tới 8192)
• sequence number - 10 bit

Implement thuật toán sinh 64 bit uniqueID của snowflake bằng python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

import simplejson
import sys
import tornado.httpserver
import tornado.ioloop
import tornado.options
import tornado.web

from time import time
from tornado.options import define, options

define("port", default=8888, help="run on the given port", type=int)
define("worker_id", help="globally unique worker_id between 0 and 1023", type=int)


class IDHandler(tornado.web.RequestHandler):
    max_time = int(time() * 1000)
    sequence = 0
    worker_id = False
    epoch = 137079712900000 # 2013-06-09

    def get(self):
        curr_time = int(time() * 1000)

        if curr_time < IDHandler.max_time:
            # stop handling requests til we've caught back up
            raise tornado.web.HTTPError(500, 'Clock went backwards! %d < %d' % (curr_time, IDHandler.max_time))

        if curr_time > IDHandler.max_time:
            IDHandler.sequence = 0
            IDHandler.max_time = curr_time

        IDHandler.sequence += 1
        if IDHandler.sequence > 4095:
            # Sequence overflow, bail out
            raise tornado.web.HTTPError(500, 'Sequence Overflow: %d' % IDHandler.sequence)

        generated_id = ((curr_time - IDHandler.epoch) << 22) + (IDHandler.worker_id << 12) + IDHandler.sequence

        self.set_header("Content-Type", "text/plain")
        self.write(str(generated_id))
        self.flush() # avoid ETag, etc generation


def main():
    tornado.options.parse_command_line()

    if 'worker_id' not in options:
        print 'missing --worker_id argument, see %s --help' % sys.argv[0]
        sys.exit()

    if not 0 <= options.worker_id < 1024:
        print 'invalid worker id, must be between 0 and 1023'
        sys.exit()

    IDHandler.worker_id = options.worker_id

    application = tornado.web.Application([
        (r"/", IDHandler),
    ], static_path="./static")
    http_server = tornado.httpserver.HTTPServer(application)
    http_server.listen(options.port)
    tornado.ioloop.IOLoop.instance().start()


if __name__ == "__main__":
    main()

Đoạn code trên được trích từ repository flake Sử dụng tornado - Python web framework and asynchronous networking library, ở một thời điểm (độ chính xác tới millisecond), một node có thể handle được nhiều request, mỗi một request sẽ được trả về một số là ID được sinh ra. Số lượng ID được sinh ra bởi một node, tại một thời điểm bị giới hạn bởi 4096, nếu lớn hơn, request sẽ bị báo lỗi

Kết luận

Bài viết trình bày một số phương pháp sinh ID 64 bit, kèm code minh hoạ. Tuỳ vào hệ thống của bạn, bạn có thể sử dụng ID 64 bit cho những mục đích khác nhau. Ví dụ như đánh số tất cả các đối tượng trong database (giống như FB làm với graph API), hoặc sử dụng 64 bit ID như một bước đệm và áp dụng thêm một bước mã hoá để sinh ID cho một loại đối tượng (giống như youtube đánh số các video).

Web audio api là gì?

Web audio api là là javascript API dành cho xử lý (processing) và tái tạo(synthesizing) âm thanh. Mới được ra đời vào thời gian gần đây (first draft vào 2011/05/12), mặc dù chưa được sử dụng nhiều ( do phần nhiều là chưa được support rộng rãi, tình trạng support các bạn có thể xem ở đây ), nhưng cá nhân mình thấy web audio api có tiềm năng ứng dụng không nhỏ, nằm ở các lý do dưới đây:

• Web audio cung cấp api ở tầng cao, giúp cho việc xử lý âm thanh trở nên dễ dàng hơn rất nhiều, đặc biệt bạn không phải quan tâm nhiều đến những công đoạn như xử lý binary data, phân tích FFT, encode/decode, input/output.
• Engine để xử lý âm thanh của web audio api chạy trên một thread riêng biệt, chính vì thế một số xử lý nặng như convolve, filter sẽ không làm ảnh hưởng đến GUI thread, chính vì vậy bạn sẽ đỡ phải quan tâm nhiều đến việc phải xử lý thế nào cho nhẹ, hay cho không block UI.
• Việc xử lý âm thanh (đặc biệt là play vào thời điểm nào- timing control) là rất quan trọng với việc làm game. Xu hướng làm rich game trên browser ngày càng phát triển, khiến cho việc sử dụng và phát triên web audio api là không thể tránh khỏi.

Để tìm hiểu và sử dụng web audio api thì bài viết này mình sẽ chia làm 2 ý, đầu tiên là kiến thức cơ bản về xử lý âm thanh, và thứ hai là web audio cung cấp những gì, và sử dụng nó ra sao.

Cơ bản về xử lý âm thanh

Bài viết này sẽ không đi quá sâu về xử lý âm thanh, mình sẽ đi qua một số khái niệm cơ bản để giúp cho việc sử dụng web audio api dễ dàng hơn. Đầu tiên các bạn nên tham khảo trước ở một số tài liệu cơ bản về digital audio processing. Mình có google thì nó ra một cái tài liệu khá dễ hiểu ở đây. Sau khi đọc tài liệu trên thì mình mong muốn các bạn nắm rõ được các khái niệm

1. Khái niệm âm thanh là gì và được biểu diễn thế nào trên máy tính? Âm thanh là các dao động cơ học được truyền trong không khí, va đập vào màng nhĩ , làm rung màng nhĩ và kích thích não người. Trên máy tính ở dạng raw thì âm thanh thường được biểu diễn dưới dạng đồ thị dạng time-series data, tức là có 1 trục là thời gian , và một trục là độ lớn (amplitude)

Để biểu diễn được trên máy tính thì sẽ cần làm 2 việc, 1 là sampling (tức là một khoảng thời gian bao nhiêu lại lấy dữ liệu một lần) và 2 là quantitize , tức là với sóng có biên độ là X thì bạn phải biểu diễn X dưới dạng bit để máy tính có thể hiểu được. Như hình vẽ dưới đây thì data được sampling với thời gian là 0.1s và được sử dụng 8bit để quantitize.

2. Khái niệm về tần số (frequency) và biến đổi Fourier(Fourier transform). Khái niệm về tần số các bạn có thể tìm hiểu thông qua google. Về Fourier transform, hay viết tắt là FT, thì FT giúp biên dữ liệu time series data nói chung ( ở đây là sound wave ) từ dạng ban đầu là trục độ lớn(x)/trục thời gian(y) trở thành trục độ lớn(x)/trục tần số(y). Việc biến đổi này có ích ở việc là giúp phân tích thành phần của sound wave, giúp cho ta biết trong data đó có những sóng có tần số thế nào, độ lớn ra sao. Điều này sẽ giúp cho việc nhận diện/ biểu diễn sound wave được thực hiện một cách dễ dàng hơn rất nhiều.

Nắm được các khái niệm trên một cách rõ ràng, chúng ta đã có thể sử dụng web audio api để làm một số việc từ đơn giản đến tương đối phức tạp rồi :).

Cấu trúc cơ bản của web audio api

Web audio api có thiết kế dưới dạng graph, được cấu thành bởi các node ( kiến trúc này còn được gọi là modular routing ). Mỗi node có thể có nhiều inputs và/hoặc nhiều outputs.

Tại sao lại là dưới dạng graph? Vì audio processing thường qua nhiều công đoạn, mỗi công đoạn xử lý lại có thể có nhiều output ( giống như hình trên ), do đó mà việc biểu diễn dưới dạng graph và connection giữa các node giúp cho việc tách các xử lý ra/ tổng hợp kết quả xử lý lại được thực hiện một cách dễ dàng và clean hơn.

Load audio file một cách đơn giản

Chúng ta sẽ bắt đầu sử dụng web audio api bằng cách load và play một file audio đơn giản:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

context = new webkitAudioContext();
sourceNode = context.createBufferSource();
sourceNode.connect(context.destination);

function loadSound(source) {
  var req = new XMLHttpRequest();
    req.open('GET', source, true);
    req.responseType = 'arraybuffer';

    req.onload = function() {
      context.decodeAudioData(req.response, function(buffer){
        playSound(buffer);
      }, function(){});
    }
    req.send();
}

function playSound( buffer ) {
  sourceNode.buffer = buffer;
  sourceNode.noteOn(0);
}

Các bạn sẽ thấy để thao tác với web audio api thì đầu tiên các bạn sẽ phải tạo ra một object gọi là AudioContext ( trên chrome sẽ gọi là WebkitAudioContext ). Toàn bộ các thao tác như tạo node mới sẽ quay quanh object này

Sau khi đã có context rồi thì các bước tiếp theo sẽ là :

1. Tạo ra sourceNode (sourceNode còn là Node dùng để input data)
2. Tạo ra destinationNode (là Node dùng để output data)
3. Load data thông qua XHR
4. play thông qua hàm noteOn của sourceNode (noteOn(0) tức là play tại thời điểm 0 là thời điểm bắt đầu của audio data)

Các bạn có thể thấy ở trên một graph đơn giản nhất đã được tạo ra với 2 node là Source và Destination được connect với nhau.

Kết luận

Như vậy các bạn đã có hình dung cơ bản về web audio api.

Ở bài viết tiếp theo mình sẽ nói về các node xử lý cơ bản như AnalyzerNode, ConvolverNode, OscillatorNode và các ứng dụng của chúng.

Các bạn có thể xem bài trình bày của mình tại osaka htmlday (bài viết bằng tiếng Nhật :D):