GMO-Z.com Vietnam Lab Center Technology Blog

Giới thiệu và hướng dẫn thiết lập NTP - Network Time Protocol

KYO -

Giới thiệu nội dung

  • NTP là gì: giới thiệu giao thức đồng bộ thời gian
  • Nguyên tắc hoạt động và những kỹ thuật sử dụng trong NTP: nguyên tắc hoạt động của hệ thống NTP
  • Thiết lập NTP: hướng dẫn config NTP trên server Linux trong 3 trường hợp cụ thể
  • Kết luận
  • Link tham khảo

NTP là gì

Giao thức NTP (Network Time Protocol - Giao thức đồng bộ thời gian mạng) là một
giao thức để đồng bộ đồng hồ của các hệ thống máy tính thông qua mạng dữ liệu chuyển
mạch gói với độ trễ biến đổi, được ra đời từ năm 1985 bởi David L. Mills nhưng vẫn được sử dụng cho đến ngày nay, và có rất ít bug được phát hiện của hệ thống NTP cho đến thời điểm hiện tại. Một số nét chính:

  • NTPv4 thông thường có thể đảm bảo độ chính xác trong khoảng 10 mili giây (1/100 s)
    trên mạng Internet công cộng, và có thể đạt đến độ chính xác 200 micro giây (1/5000 s)
    hay hơn nữa trong điều kiện lý tưởng của môi trường mạng cục bộ
  • NTPv5 là phiên bản mới nhất

Nguyên tắc hoạt động và những kỹ thuật sử dụng trong NTP

Kiến trúc Stratum (Clock Strata)

NTP sử dụng kiến trúc phân cấp, phân lớp cho các cấp nguồn đồng bộ, mỗi một cấp
trong phân cấp này được gọi là môt "statum' và được gán một số của cấp bắt đầu từ 0 là
cấp cao nhất. Cấp stratum chỉ ra nó đã qua bao nhiêu trung gian để đến được cấp tham
chiếu và cấp stratum cũng giúp tránh tham chiếu vòng trong phân cấp. Chú ý rằng cấp
stratum không có ý nghĩa chỉ chất lượng hay độ ổn định, dễ dàng tim thấy một nguồn
đồng bộ "stratum 3" có chất lượng tốt hơn một nguồn "stratum 2" khác. Các cấp độ stratum được liệt kê dưới đây

  • Stratum 0 : Bao gồm những thiết bị như đồng hồ nguyên tử (atomic clock), đồng hồ GPS hay các đồng hồ vô tuyến khác. Thiết bị Stratum-0 thường không được kết nối trực tiếp vào
    mạng mà được kết nối với máy tính (ví dụ thông qua cổng RS-232 sử dụng tín hiệu
    xung). Ảnh dưới đây là đồng hồ chủ dự phòng tại Schriever AFB (Colorado) là một nguồn
    Stratum-0 cho NTP
  • Stratum 1 : Đây là các máy tính kết nối với thiết bị Stratum 0. Đây là nguồn đồng hồ tham chiếu cho các server Stratum 2. Các máy tính này còn được gọi là time server. Các server Stratum 1 (với NTPv3 hay trước đó) có thể không hoạt động với độ chính xác của cấp Stratum 1
  • Stratum 2 : Là các máy tính gửi các yêu cầu NTP đến cho server Stratum 1. Thông thường máy tính Stratum 2 sẽ tham chiếu từ nhiều server Stratum 1 và sử dụng thuật toán NTP để thu thập thông tin chính xác nhất, và bỏ tham chiếu đến các server Stratum 1 hoạt động
    không chính xác. Các máy tính Stratum 2 sẽ liên lạc với các máy tính Stratum 2 khác để có được thời gian chính xác và ổn định hơn trong nhóm. Máy tính Stratum 2 theo phân cấp lại là nguồn tham chiếu cho các yêu cầu từ Stratum 3.
  • Stratum 3 : Các máy tính mày cũng thực hiện các chức năng như Stratum 2, và tương tự cũng là nguồn tham chiếu cho các cấp thấp hơn, có thể có tối đa 16 cấp. Tùy vào phiên bản,
    NTP có thể hỗ trợ đến 256 Stratum.

Trong phiên bản NTP 5 đang được phát triển, dự kiến chỉ có 8 stratum được cho phép. Hầu hết các NTP clients sẽ tham chiếu đến Stratum 2 server, nên sẽ không bị ảnh hưởng khi có ít cấp hơn.

Ứng dụng thuật toán Marzullo

Thuật toán Marzullo thuộc loại agreement algorithm(thuật toán thỏa thuận) là thuật toán dùng để lựa chọn sources (nguồn) để tính toán thời gian chính xác từ nhiều nguồn thời gian nhiễu(noisy time sources) -> gọi source này là confidence band(khoảng tin cậy). Nghe hơi khó hiểu nhỉ, mình sẽ đưa ra một vài ví dụ để các bạn dễ hiểu hơn nhé.

  • Ví dụ 1: ta có 3 nguồn 10 ± 2, 12 ± 1 và 11 ± 1 ( tương đương 3 khoảng [8,12], [11,13] và [10,12] ) => khoảng giá trị mà chứa nhiều giá trị chung nhất của cả 3 khoảng trên(confidence band) là [11,12] (11.5 ± 0.5) vì nó chứa giá trị chung của cả 3 khoảng trên. Xem ảnh dưới để dễ hình dung
  • Ví dụ 2: ta có 3 khoảng giá trị [8,12], [11,13] and [14,15] không có confidence band nào chứa giá trị chung của cả 3 khoảng trên, tuy nhiên khoảng [11,12] là khoảng chứa giá trị chung lớn nhất của cả 3 khoảng -> [11,12] là confidence band cần tìm

Các bước implement thuật toán Marzullo như sau
Định nghĩa:

  • offset là điểm đầu và điểm cuối của khoảng ước lượng ( ví dụ [8,12] thì 8 và 12 là offset )
  • type: là +1 or -1 ( -1: điểm đầu khoảng, +1 điểm cuối khoảng)
  • tuple: là <offset,type> ( ví dụ [8,12] sẽ có 2 tuples là <8,-1> và <12,+1> )

Các bước triển khai:

  1. Lập bảng các tuples:
  2. Sắp xếp các tuples theo giá trị tăng dần của offset. Lưu ý nếu offset bằng nhau thì ta lựa chọn -1 trước +1.
  3. Vòng lặp qua các tuples với giá trị khởi tạo best = 0, cnt = 0.
    1. cnt=cnt−type[i] ( type[i] là type của tuple đang xử lý )
    2. If cnt > best => best = cnt và beststart=offset[i] bestend=offset[i+1]
  4. Kết thúc vòng lặp ta sẽ có được confidence band cần tìm là [beststart, bestend]

Ví dụ source code triển khai với python (lượm lặt thôi)

# c.f. http://en.wikipedia.org/wiki/Marzullo%27s_algorithm
def marzullo_algorithm(ranges):
    table = []
    for l,r in ranges:
        table.append((l,-1))
        table.append((r,+1))

    def my_cmp(x, y):
        result = cmp(x[0], y[0])
        if result == 0:
            result = -cmp(x[1], y[1]) # to exclude 'pathological overlaps'
        return result
    table.sort(my_cmp)

    best = 0
    cnt = 0
    for i in range(len(table) - 1):
        cnt = cnt - table[i][1]
        if best < cnt:
            best = cnt
            beststart = table[i][0]
            bestend   = table[i+1][0]
    return (beststart, bestend)
        
def test(data_list):
    for data in data_list:
        result = marzullo_algorithm(data['input']) 
        if not result == data['expected']:
            print 'test failed input=', data['input'], 'expected=', data['expected'], 'actual=', result
            return
    print 'test suceeded'

if __name__ == "__main__":
    test_data_list = (
            {'input' : ((8,12),(11,13),(10,12)), 'expected' : (11,12)},
            {'input' : ((8,12),(11,13),(14,15)), 'expected' : (11,12)},
            {'input' : ((8,9),(8,12),(10,12)), 'expected' : (8,9)},
            {'input' : ((8,12),(9,10),(11,13),(10,12)), 'expected' : (11,12)},
            {'input' : ((8,12),(9,10),(11,13),(14,15)), 'expected' : (9,10)},
            {'input' : ((11,15),(8,15),(9,11),(10,14),(11,14),(9,10),(9,13),(12,15),(8,11),(14,15)), 'expected' : (12,13)})
    test(test_data_list)

Bạn có thể tham khảo thêm về thuật toán Marzullo tại đây.

Thực tế thì trong NTP sử dụng thuật toán Intersection algorithm (thuật toán được sửa đổi 1 chút từ thuật toán Marzullo). Lý do là do thuật toán Marzullo chỉ trả về khoảng giá trị chứa giá trị chung lớn nhất nhưng không trả về center point dùng để tính toán khoảng dịch (offset) của các khoảng giá trị nguồn so với khoảng giá trị chung tính toán được.

Các bước implement thuật toán Intersection như sau:
Giải thích:

  • f: số lượng falsetickers (những source ko tốt - source không có giá trị nằm trong khoảng giá trị interval cần tìm). Trường hợp tốt nhất là f=0 tức là confidence band tìm được sẽ nằm trong tất cả các sources đầu vào. Nếu f < M/2 -> ko có confidence band nào tồn tại vì không có khoảng nào chứa giá trị cho 1 nửa sources đầu vào -> không tin tưởng được. Lúc đó thuật toán sẽ trả về là FALSE.
  • M: số lượng sources
  • tuples <offset,type>: giống trên, chỉ có trong Intersection thì có thêm 1 type = 0 là center point của 1 source ( ví dụ khoảng [10,30] sẽ có 3 tuples là <10,-1>, <20,0> , <30,+1> )
  • endcount: bộ đếm có quy tắc endcount += type (type tuple hiện tại) => nếu gặp tuple đầu khoảng sẽ được cộng 1, center point sẽ giữ nguyên và cuối khoảng bị trừ 1. Ý nghĩa của endcount là sẽ cho ta biết confidence band đang chứa giá trị của bao nhiêu sources đầu vào.
  • midcount: bộ đếm có quy tắc mỗi khi tìm lower or upper mà gặp tuple center point thì nó được cộng thêm 1.

Các bước triển khai trong thuật toán

  1. Bắt đầu với f=0, làm vòng lặp với f tăng dần và f <= M/2
    1. endcount=0 , midcount=0
    2. Vòng lặp tìm lower point duyệt tất cả tuples
      1. endcount = endcount−type
      2. If endcount ≥ M−f thì set lower = offset và thực hiện tiếp bước sau, nếu ko thỏa mãn thì break ( break vì confidence band không thỏa mãn thuộc >= M/2 sources)
      3. If the type = 0 then midcount = midcount+1
    3. Set endcount=0 và bắt đầu vòng lặp qua tất cả các tuples để tìm upper
      1. endcount = endcount+type
      2. If endcount ≥ M−f thì set upper = offset và thực hiện tiếp bước sau, nếu ko thỏa mãn thì break ( break vì confidence band không thỏa mãn thuộc >= M/2 sources)
      3. If the type = 0 then midcount = midcount+1
    4. if lower ≤ upper và midcount ≤ f thì trả về confidence band là [lowerendpoint,upperendpoint]

Thằng này còn khó hiểu hơn tí nên lại mời các bạn xem code để hiểu hơn lý thuyết của nó nhé (Code có thể chạy online tại đây)

package main

import (
	"fmt"
	"sort"
)

type tuple struct {
	segname string // optional : ID of the interval
	offset  int    // the offset value of the start or end interval
	tp      int    // lower, midpoint, upper endpoint are types −1, 0, +1
}
type tuples []tuple

// functions to give sort capability to tuples with the “sort” package
func (ts tuples) Len() int {
	return len(ts)
}
func (ts tuples) Swap(i, j int) {
	ts[i], ts[j] = ts[j], ts[i]
}
func (ts tuples) Less(i, j int) bool {
	return ts[i].offset < ts[j].offset
}

func main() {
	var endcount, midcount, lower, upper, f, M int
	//var M int
	m := tuples{
		{"A", 10, -1},
		{"A", 20, 0},
		{"A", 30, 1},
		{"B", 38, -1},
		{"B", 58, 0},
		{"B", 78, 1},
		{"C", 46, -1},
		{"C", 70, 0},
		{"C", 96, 1},
		{"D", 60, -1},
		{"D", 91, 0},
		{"D", 122, 1},
	}
	sort.Sort(m)
	M = len(m) / 3

	// calling all truechimers
	for f = 0; f < M/2; f++ {
		endcount = 0
		midcount = 0
		// find low endpoint
		for _, t := range m {
			endcount -= t.tp
			lower = t.offset
			if endcount >= (M - f) {
				break
			}
			if t.tp == 0 {
				midcount++
			}
		}
		endcount = 0
		// find high endpoint
		for j := len(m) - 1; j >= 0; j-- {
			endcount += m[j].tp
			upper = m[j].offset
			if endcount >= (M - f) {
				break
			}
			if m[j].tp == 0 {
				midcount++
			}
		}
		// continue until all falsetickers found
		if midcount <= f {
			break
		}
	}

	// do we found an intersection ?
	if lower <= upper {
                f--;
		fmt.Println("Best source quantity = ", M-f)
		fmt.Println("False source quantity = ", f)
		fmt.Println("Beststart = ", lower)
		fmt.Println("Bestend = ", upper)
	} else {
		fmt.Println("Failed because false source quantity = ", f)
	}

}

Bạn có thể tham khảo thêm về thuật toán Intersection tại đây.

Mục đích NTP sử dụng thuật toán Intersection là để lựa chọn máy chủ thời gian chính xác nhất (accurate time servers) và giảm bớt độ trễ về thời gian do mạng.

Cách đồng bộ thời gian giữa client và server

Tiếp theo ta sẽ tìm hiểu làm cách nào mà client có thể đồng bộ thời gian với server, có 2 vấn đề cần giải quyết là

  • Độ trễ của mạng ( thời gian gửi và nhận gói tin từ client lên server).
  • Tính độ trễ của client với server.

NTP giải quyết vấn đề trên bằng cách tính time offset (thời gian lệch giữa client và server) và round-trip delay (thời gian gửi nhận gói tin qua network) bằng công thức dưới đây

  • Tính time offset:
  • Tính round-trip delay:

Trong đó
t0: client's timestamp gửi request lên server
t1: server's timestamp nhận request từ client
t2: server's timestamp gửi response cho client
t3: client's timestamp nhận được response của server

Ví dụ: ( đơn vị là giây )

client gửi t0 = 100 (client's timestamp)
server nhận t1 = 150 (server's timestamp)
server gửi response cho client t2 = 160 (server's timestamp)
client nhận response t3 = 120 (client's timestamp)

=> time-offset = ((t1 - t0) + (t2 - t3))/2 = ((150 - 100) + (160 - 120))/2 = 45 => client cần cộng thêm 45 giây nữa để đồng bộ với server

Thiết lập NTP

Thiết lập NTP trên linux là ta cấu hình trong file /etc/ntp.conf
Có 3 loại thiết lập NTP là:

  1. Cho server kết nối được ra ngoài: tất cả các server đều kết nối được ra ngoài internet
  2. Cho private network nhưng vẫn có node kết nối được ra ngoài: trong các server chỉ có 1 vài server mới kết nối được ra ngoài internet
  3. Cho private network không có node nào kết nối được ra ngoài: tất cả các server đều không kết nối được ra ngoài

Cho server kết nối được ra ngoài

  • Tất cả các server của ta đều là client. Ta cấu hình trong file /etc/ntp.conf phần server trỏ đến các server ntp như sau:
driftfile /var/lib/ntp/drift
restrict default nomodify notrap nopeer noquery

restrict 127.0.0.1
restrict ::1

# Use public servers from the pool.ntp.org project.
# Please consider joining the pool (http://www.pool.ntp.org/join.html).
server 0.centos.pool.ntp.org iburst
server 1.centos.pool.ntp.org iburst
server 2.centos.pool.ntp.org iburst
server 3.centos.pool.ntp.org iburst

includefile /etc/ntp/crypto/pw
keys /etc/ntp/keys
  • Sau khi thiết lập xong ta restart lại ntpd bằng command
service ntpd restart

Cho private network nhưng vẫn có node kết nối được ra ngoài

Ta chọn những node có thể kết nối ra ngoài làm NTP server cho những node ko kết nối được. Dưới đây là ví dụ config cho các node có dải mạng là 192.168.10.0/24 với 2 node là 10.1 và 10.2 kết nối được ra ngoài nên ta dùng làm NTP server.

  • Config file /etc/ntp.conf cho các NTP server như sau(chỉ thêm config restrict 192.168.0.0 mask 255.255.0.0 nomodify notrap cho phép các server trong dải mạng truy cập đến nhưng ko được modify):
driftfile /var/lib/ntp/drift
restrict default nomodify notrap nopeer noquery

restrict 127.0.0.1
restrict ::1
restrict 192.168.0.0 mask 255.255.0.0 nomodify notrap

# Use public servers from the pool.ntp.org project.
# Please consider joining the pool (http://www.pool.ntp.org/join.html).
server 0.centos.pool.ntp.org iburst
server 1.centos.pool.ntp.org iburst
server 2.centos.pool.ntp.org iburst
server 3.centos.pool.ntp.org iburst

includefile /etc/ntp/crypto/pw
keys /etc/ntp/keys
  • Config file /etc/ntp.conf cho các NTP client như sau (phần cấu hình server ta thay bằng IP của 2 node NTP server nội bộ vào):
driftfile /var/lib/ntp/drift
restrict default nomodify notrap nopeer noquery

restrict 127.0.0.1
restrict ::1
restrict 192.168.10.0 mask 255.255.255.0 nomodify notrap

# Use public servers from the pool.ntp.org project.
# Please consider joining the pool (http://www.pool.ntp.org/join.html).
server 192.168.10.1 iburst
server 192.168.10.2 iburst

includefile /etc/ntp/crypto/pw
keys /etc/ntp/keys
  • Sau khi thiết lập xong ta restart lại ntpd bằng command
service ntpd restart

Cho private network không có node nào kết nối được ra ngoài

Với trường hợp là không có node nào kết nối ra được internet thì ta chọn 1 số node làm NTP server nhưng dùng chính clock của node đó làm clock gốc để đồng bộ time.

  • Config file /etc/ntp.conf cho các NTP server như sau (config server 127.127.1.0 prefer chọn clock local làm clock đồng bộ, đặt là stratum 10):
driftfile /var/lib/ntp/drift
restrict default nomodify notrap nopeer noquery

restrict 127.0.0.1
restrict ::1
restrict 192.168.0.0 mask 255.255.0.0 nomodify notrap

# Use the local clock
server 127.127.1.0 prefer
fudge  127.127.1.0 stratum 10

broadcastdelay 0.008

includefile /etc/ntp/crypto/pw
keys /etc/ntp/keys
  • Config file /etc/ntp.conf cho các NTP client như sau (phần cấu hình server ta thay bằng IP của 2 node NTP server nội bộ vào):
driftfile /var/lib/ntp/drift
restrict default nomodify notrap nopeer noquery

restrict 127.0.0.1
restrict ::1
restrict 192.168.10.0 mask 255.255.255.0 nomodify notrap

# Use public servers from the pool.ntp.org project.
# Please consider joining the pool (http://www.pool.ntp.org/join.html).
server 192.168.10.1 iburst
server 192.168.10.2 iburst

includefile /etc/ntp/crypto/pw
keys /etc/ntp/keys
  • Sau khi thiết lập xong ta restart lại ntpd bằng command
service ntpd restart

Kết luận

  • Bài viếp giúp cho người đọc hiểu cơ chế hoạt động của NTP và hướng dẫn cầu hình NTP trên server Linux trong 3 trường hợp khác nhau. Hy vọng sẽ có nhiều hữu ích cho người đọc.

Link tham khảo: