Web Application Development_HTML

Web Application Development

Hypertext Transfer Protocol

1. Communication Process:

  • Browser -> DNS Server -> (IP) Browser
  • Browser -> (TCP/IP) Web Server [SYN connection] -> Browser [SYN-ACK connection] -> Web Server [ACK]
  • Browser -> (HTTP request) Web Server -> (HTTP response) Browser

2. Ports:

  • Telnet: 23
  • SMTP: 25
  • MySQL: 3306

For web servers:

  • Deployment:
    • HTTP: 80
    • HTTPS: 443
  • Development:
    • HTTP: 8000 or 8080
    • HTTPS: 8843

3. HTTP Request:

Methods:

  • Safe:
    • GET, HEAD, TRACE, OPTIONS
  • Idempotent:
    • PUT, DELETE (allowed to change the server, can have side effects, but multiple options should have the same effect as once)
  • Update:
    • POST (arbitrary changes)

HTTP Methods:

  • GET:

    • To retrieve data. Can be cached. URL length is less than 2048 characters. Only ASCII.
    • Example: /test/demo_form.asp?name1=value1&name2=value2

  • POST:

    • To post data. Cannot be cached. No length limitation. Supports all types (including binary).
    • Example: 
      1
      2
      3
      POST /test/demo_form.asp HTTP/1.1  
      Host: w3schools.com  
      name1=value1&name2=value2

  • HEAD:

    • Similar to GET, but only responds with the HTTP header, without the body.

  • PUT:

  • DELETE:

    • Delete resource.

  • OPTIONS:

    • Response supported HTTP methods.

  • CONNECT:

    • Changes connection to TCP/IP.

4. HTTP Response:

Response Headers:

  • Content-Type, Content-Length, etc.

Response Body:

  • The content is a sequence of bytes with an associated MIME type.
    Example: \r\n (carriage return and newline).

Amazon Aurora Product Thinking

Cloud Computing

Aurora: Log is database

最小化网络IO

企业级商业关系型数据库，满足高可用性，性能和拓展性，云服务托管

1. 性能和可扩展性:

  • 低抖动高吞吐量
  • 一键式计算扩展
  • 存储自动扩展
  • Amazon Aurora 低延迟只读副本

2. 可靠性:

  • 实例监控和修复
  • 包含 Aurora 副本的多可用区部署
  • 容错和自我修复型存储
  • 自动、连续、增进式备份和时间点恢复
  • 数据库快照

3. 安全性:

  • 网络隔离
  • 资源级权限
  • 加密

4. 可管理性:

  • 易于使用
  • 轻松迁移
  • 监控和指标
  • 自动执行软件修补
  • 数据库事件通知

5. 开源项目 低成本高可用

产品优点：

  1. 高可用性，比传统MySQL速度快，移植方便
  2. 自动故障修复
  3. 稳定备份和快照恢复
  4. warm restart，cache热备份：Aurora 会用内存页面缓存中存储的已知常用查询页面预加载缓冲池。这样，缓冲池便无需从正常的数据库使用“预热”，从而提高性能。

设计优点：

  1. 剥离基于SSD存储层，独立容错修复能力，高可靠的存储保证SLA免于性能波动和网络故障干扰
  2. Log is data，redo只写入存储层，减小网络IO，提高瓶颈（Mysql则需要协会脏数据页，redolog，binlog，双写文件，metadata）
  3. cache和redo，备份委托给存储层异步执行，及时回复以及warm cache

系统架构：

  1. 完全兼容Mysql用户可以不修改任何代码直接使用api
  2. 可完全脱管的数据库，具有多变的选择和可用性。
  3. 持久服务能力，跨数据中心 容错，自愈（局部数据修复能力，数据库宕机恢复），快速迁移
    • 副本数 V=6，读多数派 Vr=3，Vw=4
    • 分片限制为10GB，6个副本，万兆以太网修复时间低于10s。
  4. 多节点和恢复时数据一致性
  5. 类似Shared Disk Parallel(SDP)架构，只在主节点写，避免分布式并发控制协议。相较于sharding或分布式，将事物层和储存层剥离，将cache和redo放入储存层中
  6. 事务流程：

    • 写：单个master

      • 写多个副本，构造redo日志，但不修改buffer的数据页
      • 由储存层负责将redo日志批量持久化到磁盘，并给master发送ACK（4/6），此后储存层可异步进行后续步骤：
        • 整理日志，补充遗漏（集群中点对点的gossip协议），保证节点一致性
        • 合并步骤，将log转化为数据页
        • 将数据块备份到S3
        • 垃圾回收，清理过时的log和数据页
        • 校验数据块，自动回复坏数据

    • 读：

      • 保证缓冲区内LSN（最新修改操作log记录）大于VDL（持久化位点）的数据页被置换
      • 保证页面所有修改持久化到log，并在缓冲区没有数据页时可构造出当前的VDL页面
      • 如何保证读操作读到最新数据？
        1. 将重放操作组件将LSN ≤ VDL的日志记录应用到相应的数据页产生最新版本的数据；
        2. 读操作的时候将旧版本数据页与delta更新（日志记录）进行合并
      • 系统只有在故障恢复重启的时候会采用多数派读的方式来确定系统的VDL。正常情况下，读操作并没有采用多数派读的方法。Aurora给读操作指派一个读位点（read point），代表着读请求产生时刻的VDL。系统维护着对应存储节点的SCL，知道哪些节点可以满足当前的读操作。

    • 事务提交：

      • 异步成组提交
      • 线程将事物提交到列表，记录commit LSN，无需等待
      • 后台进程将log批量发送到存储层，主实例收到4/6个对应批次的ACK后推移VDL
      • 后台线程检查提交队列，成批提交LSN小于VDL的事务

    • 恢复：

      • 恢复由存储层负责，并行异步分布式redo，不同的segment上按需重放

53. Maximum Subarray

Be A Better Programmer

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

1.O(n)

amazing的解法

需要记录连续的和和需要丢弃前面重新开始的地方

1
2
3
4
5
6
7
8
9
10
11
12
public class longestSubstring {
    public int maxSubArray(int[] nums) {
        if(nums.length==0) return Integer.MIN_VALUE;
        int result = nums[0];int temp=nums[0];
        for(int i=1;i<nums.length;i++){
            temp=Math.max(temp+nums[i], nums[i]);
            result=Math.max(result, temp);
        }
        
        return result;
    }
}

2.Divide and conquer approach

What is divide and conquer?

http://blog.csdn.net/xyd0512/article/details/8220506

http://open.163.com/special/opencourse/algorithms.html

事实上分治算法最好味O(nlogn)， 不如线性算法

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
public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0)
            return Integer.MIN_VALUE;
        return helper(nums, 0, nums.length - 1);
    }
 
    public int helper(int[] nums, int b, int e) {
        int middle = (b + e) / 2;
        if (b == e)
            return nums[b];
        int leftmax = helper(nums, b, middle);
        int rightmax = helper(nums, middle+1, e);
        int temp = 0;
        int leftm = nums[middle];
        int rightm = nums[middle + 1];
        for (int i = middle; i >= b; i--) {
            temp += nums[i];
            if (temp > leftm)
                leftm = temp;
        }
        temp = 0;
        for (int i = middle + 1; i <=e; i++) {
            temp += nums[i];
            if (temp > rightm)
                rightm = temp;
        }
        return Math.max(Math.max(leftmax, rightmax), leftm + rightm);
    }
}

33. Search in Rotated Sorted Array

Be A Better Programmer

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

  1. 简单来说像是个二分查找，但是需要找到旋转轴，初步想法是递归，能过

  2. 看别的solution 并不需要找轴，可以在二分的基础上直接找，试试看可以

24. Swap Nodes in Pairs

Be A Better Programmer

Given a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

1.Swap in 4 group(Memory Limit Exceed)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class longestSubstring {
    public ListNode swapPairs(ListNode head) {
        ListNode result=head.next;
        ListNode third = head.next.next;
        while (head.next.next != null) {
            head.next.next = head;
            if (third.next != null) {
                head.next = third.next;
                ListNode temp=third.next.next;
                third.next.next = third;
                head = third;
                third=temp;
            } else {
                head.next = third;
            }
        }
        return result;
    }
}

2 Recursion(simple but take a stcak of O(n), stack overflow)

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode temp=head.next;
        head.next=swapPairs(head.next.next);
        temp.next=head;
        return temp;
    }
}

3.Swap in 3 group, fake a dummy node(constant memory)

20. Valid Parentheses

Be A Better Programmer

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

1.递归：stack overflow

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
public class Solution {
        public boolean isValid(String s) {
    Map<Character, Character> m = new HashMap<Character, Character>();
    // "()" and "()[]{}"
    m.put('(', ')');
    m.put('[', ']');
    m.put('{', '}');
    boolean result = false;
    while(s!=""&&s!=null){
    for (int i = 0; i < s.length(); i++) {
        if (m.containsKey(s.charAt(i))) {
            if ((i + 1) < s.length()) {
                 s.substring(i + 1);
                 String ss=findBi(s, m.get(s.charAt(i)), m);
                if (ss == null){
                    result = false;}
                else if (ss == ""){
                    result = true;}
 
                    s=ss;
                
                break;
            } else
                return false;
        }return false;
        
    }
    }
    return result;
}
 
public String findBi(String s, Character c, Map<Character, Character> m) {
    if (s==null||s.length() == 0)
        return null;
    for (int i = 0; i < s.length(); i++) {
        Character x=s.charAt(i);
        if (x == c) {
            if (i + 1 < s.length()) {
                return s.substring(i + 1);
            } else
                return "";
        } else if (m.containsKey(x) && (i + 1) < s.length()) {
            String string = findBi(s.substring(i + 1), m.get(x), m);
              System.out.println(string+"?"+c);
            if (string ==null) {
                return null;
            } else if(string == ""){
                return "";
            }
            else{
                return findBi(string, c, m);
            }
        } else if (m.containsValue(s.charAt(i))) {
            return null;
        }
    }
    return null;
}
}

2.堆栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
        public boolean isValid(String s) {
            if(s.length()%2==1) return false;
         Stack stack=new Stack<Character>();
        for(Character x:s.toCharArray()){
            if(x=='('){
                stack.push(')');
            }else if(x=='['){
                stack.push(']');
            }else if(x=='{'){
                stack.push('}');
            }else if(stack.isEmpty()||stack.pop()!=x){
                return false;
            }
        }
        return stack.isEmpty();
}
}