Continuous Integration with CloudFormation, Ansible, Jenkins, Docker, ECS

Có bao giờ bạn muốn code của mình sau khi viết xong được kiểm tra ngay tức thời với hệ thống đang chạy trên các môi trường test, stagging, thậm chí là trên production ? Làm thế nào để tăng tốc quá trình phát triển ứng dụng thông qua việc phát hiện lỗi càng sớm càng tốt ? Nếu câu trả lời là có, xin mời bạn tiếp tục theo dõi bài viết.

Bài viết sẽ đưa ra một ví dụ tổng quát về việc sử dụng các công cụ, dịch vụ phối hợp với nhau để thực hiện Continous Integration (CI) trong quá trình phát triển phần mềm.

Mô hình tổng quan gồm có những gì ?

CloudFormation : một dịch vụ của AWS hỗ trợ việc quản lý, xây dựng các tài nguyên trên Amazon Web Service (AWS) một các tự động thông qua các APIs và Json templates. Tham khảo thêm ở đây.

Chức năng : cung cấp các tài nguyên cần thiết trên AWS cho dự án, trong ví dụ này chúng ta sẽ cần :

• 01 EC2 instance để cài đặt Jenkins (CI server)
• 01 ELB xử lý việc cân bằng tải
• 01 RDS instance cho lưu trữ dữ liệu
• 01 ECS cluster để chạy, điều phối các docker containers
• 01 ECR registry để lưu trữ các docker images

Ansible : một công cụ, ngôi sao đang lên, trong việc quản lý cấu hình tự động cho các machines. Tham khảo thêm tại đây.

Chức năng : cung cấp việc cài đặt và thiết lập môi trường cũng như các packages cần thiết cho CI server :

• Nginx với chức năng reverse proxy cho jenkins
• Jenkins với chức năng CI server
• Docker với chức năng build docker image
• Aws CLI tương tác với ECS, ECR qua dòng lệnh

Jenkins : CI server, một sản phẩm mã nguồn mở giúp tự động hóa các công việc building, deploying các phần mềm, dự án. Tham khảo thêm tại đây.

Chức năng : cung cấp hõ trợ cấu hình chạy unit test, build, deploy cho dự án.

Docker : một công cụ giúp đóng gói và phân phối ứng dụng dễ dàng, đa nền tảng. Tham khảo thêm tại đây.

Chức năng : đóng gói và phân phối các ứng dụng thông qua các docker images.

ECS : EC2 Container Service. Một dịch vụ của AWS thực hiện việc điều phối, quản lý, liên kết các docker container để làm việc hiệu quả. Tham khảo thêm tại đây.

Chức năng : cung cấp việc vận hành và điều phối các docker containers.

ECR : EC2 Container Registry. Một dịch vụ của AWS để lưu trữ các docker images, chức năng tương tự như DockerHub. Từ đấy các hệ thống có thể lấy docker image theo yêu cầu.

Vậy các bộ phận trên phối hợp với nhau như thế nào ?

1. Engineer push code tới git repository
2. Jenkins định kỳ kiểm tra và pull code mới về
3. Jenkins chạy Unit test
4. Jenkins chạy docker build để đóng gói ứng dụng vào docker image
5. Jenkins pushs docker image tới ECR
6. Jenkins trigger deploy tới ECS để lấy docker image mới từ ECR

Các bước trên được thực hiện tuần tự cho tới khi tất cả các bước được hoàn thành tạo nên một chu trình khép kín CI.

Như vậy chúng ta đã có một mô hình tổng quát về CI tích hợp các công cụ có sẵn AWS, Docker, Jenkins, Ansible. Việc tích hợp CI sẽ đẩy nhanh quá trình phát hiện lỗi thông qua việc tự động hóa. Giúp cho người viết mã có thể sớm sửa lỗi, góp phần tăng tốc quá trình đưa những cập nhật mới của ứng dụng tới người dùng.

Chi tiết từng bước sẽ được tác giả tiếp tục cập nhật ở các bài viết tiếp theo. Rất mong nhận được ý kiến của bạn đọc

Làm việc với người Nhật

Từ trước tới giờ tôi vẫn hay nghe nói nhiều về sự phát triển thần kỳ của đất nước Nhật Bản. Người ta nói nhiều về sự thành công của đất nước này, sự thành công đó tất nhiên là đến từ con người Nhật Bản, bởi vì đất nước của họ thiên nhiên không phải mưa thuận gió hòa như đất nước nào đó ở vùng Đông Nam Á vẫn thường tự hào :)

Cũng chỉ nghe nói về đất nước và con người Nhật Bản như vậy nhưng tôi đã không hiểu được nhiều ở thời điểm đó. Sau một thời gian làm việc cho các công ty Nhật, hơn 5 năm 6 tháng 7 ngày, tôi có thể một phần nào hiểu được tại sao nước Nhật lại có thể đạt được nhiều thành tựu trong thời gian ngắn tới như vậy.

Bài viết này ghi lại một số kinh nghiệm, có cả những cảm nhận, về tính cách (chủ yếu là thái độ trong công việc) của những người Nhật mà tôi có dịp làm việc chung.

. Tính trung thực
   Không nói dối, luôn báo cáo tình trạng dù có tồi tệ thế nào. Bởi vì che giấu vấn đề chỉ giải quyết được vấn đề trốn tránh trách nhiệm tại thời điểm đó, tệ hại hơn nữa là làm cho người khác hiểu biết lệch lạc về vấn đề, dẫn tới không kiểm soát được hậu quả.
 
. Trách nhiệm cao, chăm chỉ
   Khi đã nhận làm một việc gì đó, người Nhật luôn làm với một tinh thần cực cao. Như thể nếu việc này mà không hoàn thành thì họ muối mặt lắm, bị đau khổ lắm, dằn vặt lắm. Do đó họ làm việc rất chăm chỉ, công việc hôm nào chưa xong thì ngồi lại tới 9, 10 giờ khuya để làm.

. Tính khiêm tốn
    Luôn tỏ thái độ khiêm tốn với người khác, cúi chào nhau khi gặp mặt. Đồng thời cũng luôn thể hiện một đầu óc luôn học hỏi, cập nhật tri thức mới.

. Sự giúp đỡ
    Sắn sàng giúp đỡ người khác nếu mình có thể giúp được một cách nhiệt tình, không tính toán so đo.

. Làm việc nhóm, trao đổi
      Kỹ năng trao đổi thông tin trong nhóm rất tốt, mọi thông tin được truyền tải qua lại giữa tất cả thành viên trong nhóm dù là việc nhỏ nhất. Ngoài ra, mỗi thành viên sẽ cố gắng làm một việc trọn vẹn và chi tiết, sau đó chia sẻ với người khác. Như vậy một người làm giỏi một việc, giúp đỡ người khác và công việc sẽ hoàn thành tốt hơn.

.Tinh thần cải tiến
    Khi gặp vấn đề, lỗi. Tập trung vào việc khắc phục sự cố trước. Sau đó tìm hiểu tại sao lại xảy ra lỗi đó, làm thế nào để lần sau không xảy ra. Tất nhiên người gây ra lỗi cũng cần có trách nhiệm báo cáo vấn đề, nhưng không phải để trách móc, chế giễu mà để lần sau không xảy ra tình trạng này.

Đó là những gì tôi thấy và học hỏi trong thời gian làm việc cùng với một số đồng nghiệp người Nhật. Viết ra những đức tính tốt của họ không phải để tự ti, thấy mình thấp kém. Mà để học hỏi, học tập. Cải thiện bản thân ngoài kiến thức chuyên môn cần có tác phong làm việc chuyên nghiệp, tính cộng đồng để hội nhập thế giới.

Xây dựng môi trường phát triển với Docker compose

Tiếp nối bài viết trước Giới thiệu về Docker, bài viết này sẽ giới thiệu một công cụ để quản lý và chạy nhiều docker containers liên kết với nhau để xây dựng một môi trường phát triển ở local cho các developers, đó là công cụ docker compose.

1. Docker compose là gì

  . Định nghĩa

 "Compose is a tool for defining and running multi-container applications with Docker. With Compose, you define a multi-container application in a single file, then spin your application up in a single command which does everything that needs to be done to get it running."

 Bạn có thể tham khảo thêm thông tin chi tiết về docker compose ở đây

2. Xây dựng môi trường phát triển với docker compose

  2.1 Mục tiêu : xây dựng một môi trường phát triển local gồm các thành phần ở dưới -Reverse proxy : nginx -Framework : play-framework/scala -Database : Mysql 5.6

  2.2 Phân tích : sử dụng docker compose để quản lý và liên kết 3 containers, mỗi container chạy 1 service như ở trên gồm có nginx, play-framework/scala và mysql server

2.3 Cài đặt docker compose : tham khảo ở đây

2.4 Thiết lập cấu hình và chạy docker compose cho project

 Tạo một folder có cấu trúc như hình bên dưới, bạn có thể đặt tên theo project hoặc tùy ý, ở đây tạm đặt là docker-compose

Trong đó :

• docker-compose/ : thư mục gốc lưu trữ
• docker-compose/app_web : thư mục lưu trữ mã nguồn của ứng dụng play-framework/scala
• docker-compose/mysql : thư mục lưu trữ Dockerfile dùng để xây dựng và chạy mysql-server container
  • Dockerfile (mysql container)

    FROM mysql/mysql-server:5.6
    ENV MYSQL_DATABASE=app_dev
    ENV MYSQL_USER=app_web
    ENV MYSQL_PASSWORD=pleasechangeme
    ENV MYSQL_ROOT_PASSWORD=pleasechangemetoo

• docker-compose/nginx : thư mục lưu trữ Dockerfile, file cấu hình nginx dùng để xây dựng và chạy nginx container
  • Dockerfile (nginx container)

    FROM centos:centos6
    MAINTAINER longlx (long_lx@septeni-technology.jp)
    # Install epel repository
    RUN yum install -y http://dl.fedoraproject.org/pub/epel/6/i386/epel-release-6-8.noarch.rpm && yum update -y && yum clean all -y
    # Install nginx
    RUN yum install -y nginx
    # Remove the default nginx configuration file
    RUN rm -v /etc/nginx/nginx.conf
    # Copy a configuration file from the current directory
    ADD nginx.conf /etc/nginx/
    ADD app.local.conf /etc/nginx/conf.d/
    # Append "daemon off;" to the beginning of the configuration
    RUN echo "daemon off;" >> /etc/nginx/nginx.conf
    CMD service nginx start

• docker-compose/Dockerfile : Dockerfile dùng để xây dựng và chạy play-framework/scala container
  • Dockerfile (play-framework/scala container)

    FROM centos:centos6
    MAINTAINER longlx (long_lx@septeni-technology.jp)
    # install java 8
    RUN yum install -y java-1.8.0-openjdk java-1.8.0-openjdk-devel && \
    yum clean all
    # install activator
    RUN yum update -y && yum install -y unzip
    RUN curl -O http://downloads.typesafe.com/typesafe-activator/1.3.6/typesafe-activator-1.3.6.zip
    RUN unzip typesafe-activator-1.3.6.zip -d /opt && mv /opt/activator-* /opt/activator-1.3.6/ && \
    rm typesafe-activator-1.3.6.zip && chmod a+x /opt/activator-1.3.6/activator
    ENV PATH $PATH:/opt/activator-1.3.6
    RUN mkdir /app_web
    WORKDIR /app_web
    # copy source code to container's volume
    COPY app_web /app_web
    CMD ["activator", "run"]

• docker-compose/docker-compose.yml : file cấu hình mà docker compose sẽ sử dùng để đọc thông tin cấu hình khi chạy lệnh "docker-compose up"
  • docker-compose.yml

    nginx:
      build: ./nginx
      ports:
        - "8080:80"
      volumes_from:
        - web
      links:
        - web 

    web:
      build: .
      ports:
        - "9000:9000"
      volumes:
        - /root
      links:
        - mysql
      tty: true 

    mysql:
      build: ./mysql
      ports:
        - "3006:3006"

Đến đây việc chuẩn bị cấu hình cho docker compose đã hoàn tất. Tiếp theo chúng ta sẽ build các images từ Dockerfile và run các containers từ các images đó :

lx:~$cd docker-compose
# build images
lx:~/docker-compose$ docker-compose build
# run and link containers
lx:~/docker-compose$ docker-compose up

Hiển thị các containers đang chạy bằng lệnh :

lx:~/docker-compose$ docker-compose ps
Name Command State Ports
-------------------------------------------------------------------------------------------------
dockercompose_mysql_1 /entrypoint.sh mysqld Up 0.0.0.0:3006->3006/tcp, 3306/tcp
dockercompose_nginx_1 /bin/sh -c service nginx start Up 0.0.0.0:8080->80/tcp
dockercompose_web_1 activator run

Hiển thị logs của web containter bằng lệnh :

lx:~/docker-compose$ docker logs -f dockercompose_web_1
--- (Running the application, auto-reloading is enabled) ---
[info] p.a.l.c.ActorSystemProvider - Starting application default Akka system: application
[info] p.c.s.NettyServer - Listening for HTTP on /0:0:0:0:0:0:0:0:9000
(Server started, use Ctrl+D to stop and go back to the console...)
[info] Compiling 130 Scala sources and 2 Java sources to /app_web/target/scala-2.11/classes...
[info] 'compiler-interface' not yet compiled for Scala 2.11.6. Compiling...
[info] Compilation completed in 9.253 s

Bây giờ bạn có thể truy cập từ trình duyệt http://app.local:8080/ để kiểm tra kết quả.

2.5 Tổng kết : như vậy bạn đã có một môi trường phát triển hoàn chỉnh gồm các stacks : nginx/play-framework/mysql trên máy của mình chỉ với một vài thao tác sử dụng docker, docker compose. Việc chia sẻ với các developers khác cũng trở nên dễ dàng hơn, bạn chỉ cần đưa lên một source repository hoặc đẩy các images lên Docker Hub và các thành viên khác có thể sử dụng và đóng góp. Hiện tại trong tài liệu chính thức của docker compose không khuyến nghị sử dụng cho production, chỉ nên sử dụng ở môi trường development, staging, continous integration. Hy vọng trong tương lai gần chúng ta có thể sử dụng docker compose cho tất cả các môi trường giúp cho việc phát triển và phân phối các ứng dụng trở nên dễ dàng và trơn tru hơn. Một vấn đề nữa là khi mount một thư mục trên máy linux đã được mã hóa ổ đĩa, với một thư mục trên play-framework/scala container thì lúc biên dịch sbt sẽ báo lỗi :

"play.sbt.PlayExceptions$CompilationException: Compilation error[File name too long]"

Nguyên nhân có thể do giới hạn class file name của sbt và giới hạn của bản thân docker container. Khi có giải pháp cho vấn đề này người viết bài sẽ cập nhật.

 Thank you for reading, all comments are welcome !

AWS CloudFormation là gì?

Nếu đã từng làm việc trên AWS (Amazon Web Service) - môi trường cloud computing của Amazon - có thể bạn sẽ cần nhiều tới sự trợ giúp của CloudFormation - một công cụ để "tài liệu hóa" nguồn tài nguyên ( EC2 instances, RDS database , VPC ...) trên AWS.

Việc sử dụng CloudFormation giúp tái sử dụng các tài nguyên trên AWS dễ dàng và tự động. Giúp tiến gần tới khái niệm "Infrastructure as Code", một thuật ngữ mới trong nghành phát triển các sản phẩm phần mềm hiện đại.

Mục tiêu của bài viết này chia sẻ kiến thức cơ bản về CloudFormation, cách sử dụng nó qua một số ví dụ.

I. Một số khái niệm

1. Templates

Thành phần cốt lõi để CloudFormation làm việc là các templates. Nếu bạn là người thích liên tưởng, thì các templates giống như các bản thiết kế, phác thảo trong ngành xây dựng vậy. Nếu không thì đây là các tài liệu ở định dạng JSON, định nghĩa danh sách các tài nguyên, cấu hình của chúng mà bạn muốn sử dụng để xây dựng môi trường cho sản phẩm của mình trên AWS. Bạn sẽ định nghĩa trước các thành phần, bộ phận mà bạn muốn có ở đây. Sau đó Cloudformation sẽ đọc và thực thi theo yêu cầu của nội dung chứa trong các templates này.

Một template có cấu trúc như ở bên dưới :




{"AWSTemplateFormatVersion" : "version date","Description" : "JSON string",
"Metadata" : {
template metadata
},
"Parameters" : {
set of parameters
},
"Mappings" : {
set of mappings
},
"Conditions" : {
set of conditions
},
"Resources" : {
set of resources
},
"Outputs" : {
set of outputs
}
}

2. Stack

Stack là một thực thể của template, nó là một ngăn xếp giúp quản lý tập hợp các tài nguyên AWS đang được sử dụng trong cùng một nhóm. Bạn có thể hình dung như stack là một ngôi nhà cụ thể được xây dựng từ bản thiết kế ( các templates ). Nó là các tài nguyên đang được sử dụng thực, không còn là khái niệm trên các templates nữa.

II. Một số ví dụ

Công ty vừa phát triển một sản phẩm mới trên LAMP, bạn được yêu cầu chuẩn bị cơ sở hạ tầng và môi trường để sản phẩm chạy được trên AWS.

Đầu tiên phân tích các thành phần, stacks trên AWS sẽ gồm có :

- VPC : một data center ảo bao gồm subnets, routing tables, internetgateway

- EC2 : server ảo chạy Amazon linux, Public IP address

- RDS : database ảo chạy Mysql

Bây giờ bạn sẽ cần phải chuẩn bị các templates cho mỗi stack ở trên. Trong các templates này, bạn sẽ định nghĩa những thành phần cần thiết ở đây theo định dạng JSON. Ví dụ một đoạn JSON như dưới :

"Resources" : {"EC2Instance" : {"Type" : "AWS::EC2::Instance","Properties" : {"InstanceType" : { "Ref" : "InstanceType" },"SecurityGroupIds" : [ { "Ref" : "DevBaseWebVPCSecurityGroupID" }, { "Ref" :       "DevProductVPCSecurityGroupID" } ],"KeyName" : { "Ref" : "KeyName" },"SubnetId": { "Ref" : "DevPublicSubnet1AID" },"PrivateIpAddress" : { "Ref": "PrivateIPAddress" },"BlockDeviceMappings" : [ {"DeviceName" : "/dev/xvda", "Ebs" : { "VolumeSize" : "30" }} ],"ImageId" : { "Fn::FindInMap" : [ "AWSRegionArch2AMI", { "Ref" : "AWS::Region" },{ "Fn::FindInMap" : [ "AWSInstanceType2Arch", { "Ref" : "InstanceType" }, "Arch" ] } ] },"Tags": [{"Key": "Name","Value": { "Ref" : "InstanceName" }}] } } }

Trong ví dụ trên bạn sẽ tạo một EC2 instance với các đặc điểm được định nghĩa trước, bạn có thể điền giá trị trực tiếp trong template hoặc truyền vào giống tham số sau như ở phía dưới:

• InstanceType
• SecurityGroupIds
• KeyName
• SubnetId
• PrivateIpAddress
• BlockDeviceMappings
• ImageId
• Tags

Chuẩn bị Cloudformation template cho stack VPC, một ví dụ mẫu của VPC template bạn có thể xem ở đây.

Sau khi chuẩn bị xong vpc template, giả sử bạn lưu ở thư mục cloudformation/vpc_template.json. Có nhiều cách sử dụng template này, qua web console, aws command line, api. Ở đây bạn sẽ dùng aws command line, chạy lệnh dưới để tạo stack sử dụng vpc template bạn vừa tạo ở trên :

aws cloudformation create-stack --stack-name vpc-base-network --template-body file:///cloudformation/vpc_template.json

Tương tự cho các stacks EC2, RDS còn lại.

Chuẩn bị Cloudformation template cho stack EC2, một ví dụ mẫu của EC2 template bạn có thể xem ở đây.

Sau khi chuẩn bị xong ec2 template, giả sử bạn lưu ở thư mục cloudformation/ec2_template.json. Chạy lệnh dưới để tạo stack sử dụng ec2 template bạn vừa tạo ở trên, bạn có thể truyền tham số vào template :

aws cloudformation create-stack --stack-name dev-ec2-web --template-body file:///cloudformation/ec2_template.json --parameters ParameterKey=KeyName,ParameterValue=keys.dev ParameterKey=SubnetID,ParameterValue=subnet-a1b2c3d4

Chuẩn bị Cloudformation template cho stack RDS, một ví dụ mẫu của RDS template bạn có thể xem ở đây.

Sau khi chuẩn bị xong rds template, giả sử bạn lưu ở thư mục cloudformation/rds_template.json. Chạy lệnh dưới để tạo stack sử dụng rds template bạn vừa tạo ở trên, bạn có thể truyền tham số vào template :

aws cloudformation create-stack --stack-name dev-rds --template-body file:///cloudformation/dev/rds.json --parameters ParameterKey=DBSecurityGroup,ParameterValue=sg-f677e293 ParameterKey=DBSubnetGroup,ParameterValue=vpc-network-devdbsubnetgroup-19mk1hlxxx

Như vậy là bạn đã xây dựng xong cho mình một môi trường hoàn chỉnh trên AWS bao gồm ba stacks chính là VPC, EC2, RDS sẵn sàng cho việc deploy các sản phẩm tuyệt vời lên đó rồi. Các developers khó tính chắc chắn cũng khó để không hài lòng.

Tham khảo: http://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/

Divide and conquer - khái niệm "vạn năng"

Tôi thấy bài viết này hay hữu ích, dịch lại để nhớ phòng khi cần áp dụng :)) 

Ý tưởng chính là mọi vấn đề dù phức tạp đến đâu đều có thể giải quyết bằng phương pháp chia để trị, vấn đề phức tạp sẽ được chia thành càng vấn đề càng nhỏ càng tốt. Nhỏ tới mức đơn giản để giải quyết. Một ví dụ tôi có thể nghĩ ra là chiếc máy tính của bạn làm được rất nhiều việc phức tạp như lướt web coi phim, làm văn bản, nhận diện giọng nói mặt người ... nhưng các việc máy tính làm ở phía dưới chỉ là các phép toán cộng, trừ, lấy dư ... của CPU với các bit 0,1 mà thôi

----

Divide and conquer (chia để trị) là tên của một nhóm các thuật toán giải quyết các vấn đề bằng cách đệ quy (đệ quy là một khái niệm lập trình mà một chương trình sử dụng một phiên bản nhỏ hơn của nó). Ví dụ như Quicksort, một thuật toán gọn gàng dùng để sắp xếp các phần tử của một danh sách, có sử dụng đệ quy.

Nhưng đó không phải là định nghĩa duy nhất của nó. Trong lịch sử nó bắt nguồn từ 'divide and rule', một khái niệm để chỉ những người dân bản địa chiến đấu với nhau làm cho kẻ thù chung cai trị tất cả bọn họ. Hợp lại chúng ta thắng, chia rẽ chúng ta thất bại ...

Lý do mà tôi cho rằng divide and conquer là một trong những chiến lược đầy sức mạnh trong lập trình, đó là nó có thể được áp dụng ở mức cao : khi viết các chương trình phức tạp. Nếu bạn gặp một vấn đề quá khó để giải quyết trong một bước, bạn có thể sử dụng devide and conquer từng bước cho tới khi vấn đề của bạn trở nên dễ dàng. Sau đó bạn trở lại với vấn đề ở một cấp phía trên và tái sử dụng nó cho tới khi tất cả các vấn đề phụ được giải quyết và điều này đồng nghĩa với việc bạn đã giải quyết được vấn đề phức tạp ban đầu rồi đó.

Thậm chí khái niệm này còn được áp dụng để giải quyết tất cả các vấn đề ngoài lĩnh vực lập trình. Tôi chỉ cho bạn một ví dụ nhé : bạn cần sửa sang lại ngôi nhà? Quá khó để nắm được hết trong chốc lát, và tôi chắc rằng nếu không có kế hoạch cụ thể bạn sẽ bế tắc, thậm chí tuyệt vọng tới mức đốt luôn ngôi nhà của bạn lúc nào không hay. Không cần phải thế đâu, hãy chia nhỏ vấn đề ra và mọi thứ sẽ dễ dàng hơn :

• cơ sở hạ tầng
• hệ thống điện
• đường dẫn khí ga
• đường ống nước
• hệ thống s
• các căn phòng
• phòng bếp
• sửa trần
• chuẩn bị tường
• sàn gạch
• bàn ăn
• hộp tủ
• phòng tắm
• làm trần
• đặt kính
• vặn ốc vít
• làm mượt
• sơn
• sưả tường
• lát tường
• lắp đặt vòi tắm
• lắp cửa kính
• phòng khách
• phòng áp mái
• tầng hầm

Tôi vừa mới liệt kê chi tiết vài hạng mục nhỏ, bạn không cần phải dừng lại ở bất kỳ cấp độ cụ thể nào, mà có thể chia càng nhỏ hạng mục tới mức bạn muốn. Đây là một bí quyết rất hữu ích, nó cho phép một người có thể giải quyết mọi vấn đề nếu cho anh ta đủ thời gian. Nó cũng áp dụng cho việc sữa chữa xe hơi, hệ thống điện, ...vân vân. Tôi chưa thấy một công việc nào mà 'divide and conquer' không làm cho nó đơn giản hơn và nó luôn làm tôi ngạc nhiên khi mọi người không biết về nó hay không biết làm thế nào để sử dụng nó trong thực tế. Và nếu bạn chia nhỏ công việc trước khi bắt tay vào làm thì hẳn nhiên nó đã trở thành một kế hoạch, mà nó sẽ càng dễ dàng hơn nếu bạn nhận ra trước được việc nào có thể sai hoặc thứ tự các việc cần làm trước, việc cần làm sau. Chẳng hạn như ở ví dụ trên, rõ ràng là bạn nên cần phải làm sàn của ngôi nhà trước khi làm các phụ kiện phòng bếp, nó giúp bạn tiết kiệm công sức và tiền của.

Rõ ràng là có vài trường hợp mà chiến lược này không dùng được. Nếu bạn có ước mong trèo lên đỉnh Everest một mình thì bạn sẽ khó mà hoàn thành được cho dù bạn đã chia nhỏ nó thành 2 quãng đường nhỏ hơn bằng toàn bộ hành trình. Bởi vì việc leo tới đỉnh Everest bản thân nó đã vượt ra khỏi giới hạn của một cá nhân con người. Nhưng gần như tất cả vấn đề bạn gặp hàng ngày, quy tắc này đảm bảo rằng bạn thường là có thể chia nhỏ chúng ra các vấn đề nhỏ hơn.

Vậy thì lần tới khi gặp phải vấn đề gì mà bạn không thể làm, trong lĩnh vực lập trình hay các vấn đề trong cuộc sống : Divide and conquer! Chia vấn đề thành hai phần nhỏ hơn bằng nhau nếu có thể, sau đó cố gắng giải quyết chúng và nếu chúng vẫn còn quá phức tạp thì hay lặp lại quá trình trên cho tới khi có ít nhất một vài phần của vấn đề lớn trở nên khả thi. Thậm chí đôi khi phải bỏ đi một phần nhỏ của vấn đề để làm cho công việc còn lại dễ giải quyết hơn.

Source : http://jacquesmattheij.com/divide-and-conquer

Học Algorithms, Ngày 03

Hôm nay học Week 1 Analysis of Algorithms [introduction] & [observations]. Phần này nói về việc phân tích các thuật toán.

Ghi lại một vài ý mà tôi cho là quan trọng.

1.[introduction]

Lý do tại sao cần phải phân tích thuật toán :

• Predict performance.
• Compare algorithms.
• Provide guarantees.
• Primary practical reason : avoid performance bugs.

Phân tích thuật toán như thế nào? Một trong các cách là dùng scientific method, nghĩa là dùng phương pháp khoa học. Gồm các bước chính sau :

• Observe some feature of the natural world.
• Hypothesize a model that is consistent with the observations.
• Predict events using hypothesis.
• Verify the predictions by making futher observations.
• Validate by repeating until the hypothesis and observations agree.

2.[observations]

Sử dụng phương pháp quan sát để mô hình hóa việc tính toán thời gian chạy với kích cỡ dữ liệu đầu vào.

Hầu hết được tính theo công thức : T(N) = aN^b

Từ các kết quả chạy chương trình thực tế, tính toán a và b. Dự đoán b bằng cách gấp đôi số liệu dữ liệu đầu vào, phương pháp "doubling hypothesis". So sánh tỷ lệ kết quả các lần chạy, tính log cơ số 2, -> tính được b.

Hypothesis. Running time is about a N^b with b = lg ratio

Sau đó tính a bằng cách thay vào công thức T(N) và kết quả từ việc chạy chương trình thực tế.

Sau đó so sánh lại kết quả thực tế và kết quả dự đoán cho tới khi 2 kết quả này gần nhau nhất có thể.

Một vài lưu ý nhỏ về việc ảnh hưởng của các tham số:

System independent effects.
・Algorithm.
・Input data.

System dependent effects.
・Hardware: CPU, memory, cache, …
・Software: compiler, interpreter, garbage collector, …
・System: operating system, network, other apps, …

Hôm sau học Week 1 Analysis of Algorithms [mathematical models]

Học Algorithms, Ngày 02

Hôm nay học "Week 1" [quick-find] & [quick-union]. Đã thấy khó hơn nhưng vẫn hiểu được không nhiều thì ít hơ hơ.

Ghi lại vài chú ý chính.

1. [quick-find]

Data structure.
・Integer array id[] of length N.
・Interpretation: p and q are connected if and only if they have the same id.

Operations.
・Find : check if p and q have the same id.
・Union : to merge components containing p and q, change all entries whose id equals id[p] to id[q].

quick-find is too slow. 

union is too expensive. It takes N*N array accesses to process a sequence of N union commands on N objects.

2. [quick-union]

Data structure. 

・Integer array id[] of length N. 

・Interpretation: id[i] is parent of i. 

・Root of i is id[id[id[...id[i]...]]].

Operations.

・Find : check if p and q have the same root. 

・Union : to merge components containing p and q, set the id of p's root to the id of q's root.

quick-union is also too slow.

find too expensive (could be N array accesses).

Túm lại là 2 thuật toán quick-find và quick-union có thể giải quyết được vấn đề [dynamic connectivity], một cái thì "tìm nhanh" , cái còn lại thì "hợp nhanh". Tuy nhiên 2 thuật toán này không hiệu quả về mặt hiệu năng, quá chậm khi số phần tử N lớn. Hai cái này gọi là "quandratic algorithms" nghĩa là thời gian tính toán tăng theo cấp số bình phương của kích cỡ.

Hôm sau sẽ học Week 1 [quick-union improvements] & [union-find applications].