If God Built Netflix

ผมพยายามเขียนบล็อคนึงมาหลายปีแต่ก็ไม่เคยตกผลึกเขียนจบสักที

section ใหญ่ๆ ในบล็อคนั้นคือ ถ้าพระเจ้าสร้าง Netflix มันจะ design ระบบมายังไงกันนะ

เพราะในช่วงนั้น Microservice กำลังอยู่ในช่วงบูม gut feeling ผมบอกว่า microservice มันไม่ถูก แต่ไม่รู้ว่าที่ถูกต้องทำยังไงเลยไปนั่งคิดอยู่ว่าถ้าออกแบบระบบโดยมีเวลาไม่จำกัด มีเงินไม่จำกัด และทีมพัฒนาเทพมากไม่ต้องกังวลว่าจะเกิด feature creep มันจะออกมาหน้าตายังไง


ช่วงนี้ได้กลับไปดูคนอื่นแก้ module ที่เคยถือก่อนหน้านี้

module นี้ผมก็อยู่ในทีมก่อตั้งเลย แต่ตอนนั้นดูฝั่ง client side เลยไม่ค่อยรู้เรื่องว่ามัน design มายังไง จนตอนหลังมาปะติดปะต่อภาพแล้วเข้าใจว่าไอเดียของมันคือจะมี API กลางตัวนึงซึ่งมันแทบจะเป็น REST API ให้ database เลยแหละ แล้วก็ handle authn/authz ต่างๆ และ API นี้จะไม่รู้จัก module ที่เป็น UI เลยจะรู้จักแต่ module ที่ provide service เพื่อ implement feature ของมันเท่านั้น

ในฝั่ง UI ด้านนอกก็จะทำหน้าที่แทบจะเป็น API Gateway แค่นั้นไม่ได้มี logic อะไรเพิ่มนอกจาก map field ต่างๆ

ปัญหาก็คือบางครั้ง UI อยากจะทำ push notification เมื่อ object change ซึ่งเนื่องจาก API กลางจะไม่รู้จักกับ UI module เลยจะ push ไป trigger ไม่ได้ ก็ต้องส่ง message เข้าไปใน message queue ว่ามีการ change แล้ว แล้วใครอยากได้ก็อ่านไป ใน message เองก็จะไม่ได้ระบุว่า change อะไรบ้างส่งมาแต่ snapshot ของ object ที่เวลานั้นๆ

Design นี้ถ้าเคยศึกษา Kubernetes ก็น่าจะพอ map ได้เลยว่า API กลางเหมือน kube-apiserver แล้ว UI ก็คือพวก controller/operator ต่างๆ ซึ่งก็ถือว่าทันสมัยมากเพราะในตอนนั้น Kubernetes ยังเป็นของใหม่มากๆ และคิดว่าทีมก็ยังไม่ได้ศึกษา design ของ Kubernetes มาก่อน แต่มันก็เป็นไปตามหลัก microservice design

ที่จะแตกต่างกันคือ Kubernetes จะมีส่วนเก็บ status ของ object ที่ให้ controller สามารถเขียน state กลับไปได้ ทำให้ controller ทุกตัวเป็น stateless ได้หมด แต่โปรแกรมนี้ไม่ได้คิดไปถึงตรงนั้น

ฟีเจอร์แรกๆ ที่ต้องยิง callback ผมจำได้ว่าใช้วิธีเปิด Redis ของ UI module ตัวนั้นมาเก็บ state ส่วนตัว พอมาฟีเจอร์ที่สองบนอีก UI module หนึ่ง คนที่ออกแบบก็เลือกจะเอา API กลางยิงออกไป 3rd party แทนแล้ว ผมก็ยังไม่แน่ใจว่าทำไมเลือกใช้ design แบบนี้ในตอนนั้น

หลังจากนั้นแล้วผมก็ทิ้งหายจาก module นี้ไปนาน ทีมที่เขียนก็แยกย้ายกันไป บางคนก็ยังอยู่ในบริษัทแต่ทำหน้าที่อื่นๆ แล้ว จนกระทั่งผมได้กลับไปดู UI module ตัวนึงซึ่งทีมปัจจุบันไม่มีคนดู ปัญหาใหญ่ๆ ที่ผมเห็นคือมัน scale ไม่ได้และห้าม restart ด้วยเพราะมันเก็บ state ใน memory ตอนนั้นถึงเข้าใจว่า design ของระบบจริงๆ เค้าคิดอะไรอยู่

หนึ่งปีให้หลัง ทีมปัจจุบันเข้ามาแก้เพิ่มฟีเจอร์ใน UI module นั้น ผมรีวิวแล้วก็เพิ่งรู้ตัวว่า design ของระบบนี้มันเปลี่ยนไปเยอะมากเพราะทีมใหม่คุ้นชินกับการที่ทำฟีเจอร์ใหม่เป็น explicit เกือบหมด อยากได้อะไรก็ยิงไปบอกคนนั้นว่าให้ทำแบบนี้ ซึ่งมันเขียนง่ายขึ้นเยอะแต่ service ก็จะพันกันหมด


ถามว่าถ้าตอนนั้นไปลอก design แบบ Kubernetes มาคือแก้ให้ API กลางช่วย module อื่นเก็บ state ได้มันจะแก้ปัญหานี้มั้ย?

ผมก็ยังคิดว่าปัญหามันยังไม่จบนะ ถ้าดูจาก Kubernetes เองก็จะเห็นว่า API บางอย่างมันจำเป็นต้องมี flow explicit action จริงๆ เช่นขอดู log ที่ถ้าทำเป็น implicit แล้ว kubelet ต้อง stream log ไปที่ API server ตลอดเวลา หรือ API server ต้องมี Kubelet log URL เพื่อให้ client ไปยิงเป็น explicit กันเอง ก็เป็นปัญหา network security อีก และอย่างคำสั่ง exec นี่คงจะไม่มีทางเลี่ยง ยังไงก็ต้องเปิด channel ตรงๆ

นอกจากนี้ Kubernetes design ยังทำให้เกิด traffic ในการ polling เยอะ ก็จะเห็นว่า Kubernetes เริ่มติด scaling limit ระดับหลายพัน node ที่ API Server กินทรัพยากรจำนวนมาก

สำหรับ project ที่เล่าไปนี้ design ปัจจุบันที่ยิง action ตรงๆ ผมว่ามันเป็นอะไรที่ตรงไปตรงมา น่าเบื่อ แต่มันก็เหมือนจะเป็น system design ที่ผ่านการพิสูจน์มานานแล้ว ถ้าไม่กังวลปัญหาใหม่ๆ อย่าง microservice design ก็ดูเหมือนจะเป็น solution ที่น่าสนใจ


ผมเล่าเรื่องถ้าพระเจ้าสร้าง Netflix ลงใน Facebook อาจารย์ผมมาอ่านแล้ว comment ว่า

“ถ้าจะแก้ทีนึงก็ต้องสวดชุมนุมเทวดาก่อน”

ผมขำอยู่ปีนึงถึงจะเข้าใจความหมายที่อาจารย์จะสื่อ

Google Code Jam 2013 – Qualification Round 1C

ตกรอบทั้งแผ่นดิน :\ rank 2691

รอบนี้เหมือนจะง่ายเลยครับ ก็

# Consonants

ข้อนี้ให้ string มา แล้วจะมีพยัญชนะติดกันหลายๆ ตัว ถามว่ามี substring ที่มีพยัญชนะติดกันมากกว่า n ตัวกี่ substring

(substring คือส่วนใดส่วนหนึ่งของ string ตั้งแต่ 1 ตัวข้ึนไป และ substring เขียนเหมือนกันแต่เป็นคนละตัวได้ถ้าตัดมาจากคนละท่อนกัน คือจุดเริ่มต้นหรือจุดสิ้นสุดเป็นคนละจุด)

ผมใช้วิธีโง่ๆ อีกแล้วคือหาก่อนว่ามี substring ที่ตรงตามเงื่อนไขที่ตำแหน่งไหนบ้าง พอได้ครบแล้วก็หา substring ทั้งหมดแล้วหาว่ามีส่วนใดส่วนหนึ่งของ substring ที่พบในตอนแรกมั้ย ถ้ามีก็ดูว่าครบตาม n ตัวก็ให้ผ่านได้

ข้อนี้ large ไม่ทันครับ ไฟล์มัน 4MB มีข้อดัก 5 ข้อที่ string น่าจะหลายล้านตัว (เปิดไฟล์มา sublime ผมค้าง หน้าจอมีแต่ rrrrrrrrrrrrrr)

# Pogo

ผมคิดว่ามันง่ายนะ แต่ผมไม่รู้เรื่องนี้

ให้หาเส้นทางจาก (0,0) ไปจุดที่กำหนด (อาจจะตำแหน่งติดลบได้) เดินทะแยงไม่ได้ โดยเดินครั้งแรกจะไปในทิศทางนั้น 1 จุด ครั้งที่ 2 ไป 2 จุด ฯลฯ ห้ามเกิน 500 ก้าว และข้อใหญ่ต้องตอบวิธีที่สั้นที่สุดเท่านั้น

# The Great Wall

ข้อนี้นี่อ่านแล้วยาวแต่สนุกดีครับ

กำแพงเมืองจีนยาวในแนวแกน x จาก -อนันต์ – +อนันต์ ถูกเผ่าต่างๆ โจมตีเข้ามาในแต่ละวัน โดยมีการกำหนดค่าเผ่าดังนี้

– วันแรกที่เข้าโจมตี
– จำนวนครั้งที่เข้าตี
– ตำแหน่งที่เข้าตี (range)
– ความแรงของการโจมตี
– วันต่อๆ ไปที่เข้าตี (จะเข้าโจมตีทุกๆ n วัน ตามค่านี้ จนกว่าจะครบจำนวนครั้ง)
– ระยะทางที่เผ่าเคลื่อนที่ไปในการโจมตีครั้งต่อๆ ไป
– ความแรงในการโจมตีครั้งต่อๆ ไป (จะลดหรือเพิ่มตามค่านี้ตลอดทุกการโจมตี)

ตอนแรกไม่มีกำแพงอยู่ เมื่อถูกโจมตีแล้วกำแพงในส่วนที่ถูกโจมตีนั้นจะถูกยกขึ้นให้สูงเท่ากับความแรงของการโจมตี ต่อมาเมื่อมีการโจมตีซ้ำ ถ้าจุดใดจุดหนึ่งในช่วงที่เข้าตีมีความสูงน้อยกว่าความแรงการเข้าตีให้ถือว่าการโจมตีนี้สำเร็จ และยกกำแพงใหม่ให้สูงขึ้นเท่ากับความแรงการโจมตีครั้งนี้ ทั้งช่วงที่เข้าตี (ยกขึ้นหลังหมดวันแล้วเท่านั้น ถ้ามีการโจมตีอื่นๆ อยู่ยังไม่ยกขึ้น)

ข้อนี้กลับมาได้ใช้ class อีกแล้วครับ ผมไม่แน่ใจว่า x position มันติดลบได้มั้ย เลยเขียน class ที่รองรับตำแหน่งติดลบได้ด้วย แล้วก็ยังมีระบบ rebuild queue อีกด้วย

ตอนแรกผมเขียน generator (function `__iter__`) ไว้สร้างการเข้าตีทั้งหมด แต่ผมพบว่าเวลาจะโค้ดผมน่าจะไล่ไปดูว่าวันนี้ใครจะตีบ้าง ก็ควรจะ generate ของแต่ละวันมาน่าจะดีกว่า เลยเขียน `atk_day` ซึ่งก็ต้องบวกลบเลขกันนิดนึง

สิ่งที่พลาดนานที่สุดในข้อนี้คือ range ครับ ผมนึกว่ามันคือ [0, 2] แต่จริงๆ มันคือ [0, 2) (ตำแหน่งที่ 2 ไม่มีการเข้าตี) แล้วก็มี test case ตัวอย่างที่ผิดด้วย แต่คำตอบมันถูก ทำผมเสียเวลา debug แต่พอแก้ได้ปุ๊บก็ทำถูกได้ก่อนเค้าประกาศแก้ไขโจทย์

เช่นเดียวกัน ข้อ large ข้อนี้รันไม่ทัน นั่งเช็คๆ ดูเหมือนว่าแค่ generate attack for tribes on everyday ก็ไม่ทันกินแล้ว :3