Cách tốt nhất để điều chỉnh hệ thống bảo mật này để xử lý nhiều thừa kế là gì?

Question

Đeo mình vào, đây là một câu hỏi phức tạp.

Chúng tôi có một hệ thống giao dịch với các tập dữ liệu lớn. (triệu đến tỷ bản ghi trên mỗi bảng lớn). Tất cả các dữ liệu được xử lý trong một cấu trúc cây của các nút.

Chúng tôi đang sử dụng Symfony2 và hệ thống bảo mật Symfony2 (Đối tượng miền, Acls, Aces, v.v.). Cây Acl của chúng ta phản chiếu cây nút của chúng ta.

Ðúc một số ngôn ngữ:

• DP Defined phép, tức là một kỷ lục ace vào nút acl này
• EP phép có hiệu lực, không có hồ sơ ace, cho phép kế thừa từ cha mẹ với một DP

Logic nghiệp vụ khôn ngoan, chúng tôi gán 0 hoặc 1 ace cho một đối tượng cho mỗi người dùng và dựa vào thừa kế khi không có. Root > lvl1 (DP: VIEW) > lvl2 > lvl3 (EP: VIEW)

Cho đến nay, rất tốt. Điều này tất cả các công trình.

Một số nút không chỉ có cha, nhưng được kết hợp với các nút khác (nhiều đến nhiều nút). Khi một nút được liên kết với một nút khác, điều này thể hiện một đường dẫn riêng biệt lên cây để có thể thực hiện theo. IE chúng ta sẽ có 1 hoặc nhiều đường dẫn lên cây để root để thu thập ace's.

Leaf < Parent < GrandParent < Root 
Leaf < AssociatedNode < AssociatedNodeParent < AssociatedNodeGrandParent < Root 
... 

Hoặc logic để quản lý bỏ phiếu là tốt, những gì chúng tôi không chắc chắn là cách thể hiện nhiều đường lên cây. hiện tại của chúng tôi (đọc: xấu) ý tưởng là:

• Nhiều hành vi cha mẹ trong cây acl
  • Ưu
    • vẻ sạch hơn?
  • Nhược điểm
    • Hầu như toàn bộ viết lại của hệ thống an ninh để đặt điều này trong.
    • ratsnesting tiềm năng.
• Nhân dạng đối tượng trùng lặp/acls đối với thực thể, chỉ định cha mẹ khác nhau.
  • Ưu
    • Er ...
  • Nhược điểm
    • sẽ tạo ra một số lượng rất lớn các bản ghi acl tiềm năng.
    • Khó quản lý trong mã.

Answer 1

Trong trường hợp cha mẹ nhiều tài khoản, bạn có hiệu quả có một cây traversal nghịch đảo từ nút đầu tiên của bạn đến bất kỳ node có chứa một ace. Vì vậy, nếu chúng ta hình dung các hoạt động truyền tải lên trên và bên là cây của riêng chúng (các vòng cắt tỉa), bạn có thể tìm kiếm toàn bộ mạng nút của bạn trước khi bạn tìm thấy ace trong trường hợp xấu nhất.

Cách dễ nhất để giải quyết vấn đề này là đảm bảo một số hình thức heap property đảm bảo mỗi nút có ace có giá trị lớn hoặc nhỏ có thể điều khiển truyền tải. Điều này làm giảm thời gian truyền tải xuống từ trường hợp xấu nhất O(n) (nếu bạn tìm kiếm mọi nút trong chỉ mục cơ sở dữ liệu của mình) thành O(log n) khi bạn quay lại qua mạng.

Lý do tại sao việc nhận được thông tin O(1) ở đây khó khăn là mạng nút của bạn đảm bảo khả năng lặp lại. Nhưng, nếu bạn xây dựng một biểu đồ ACL duy trì các thuộc tính của, ví dụ, một heap min, bạn sẽ không sao.

Chúc may mắn nhất với mô hình quyền của bạn.

Answer 2

Một lần nữa, như đã nói, đây là một vấn đề thú vị nhưng không tầm thường - cảm ơn! Bây giờ tôi biết làm thế nào tôi phải chi tiêu cuối tuần này :-) Tôi có thể xem xét ý tưởng đống là tốt, nhưng tôi muốn làm cho nó một đống threaded. Mỗi nút trong heap chứa một con trỏ tới một "chỉ mục" ACL nếu bạn muốn.

Giả sử tôi chỉ có ba nút trong ví dụ (R (oot), P (không) và N (ode)). Do đó, bộ ACL cho N là ACL (R) + ACL (P) + ACL (N). Giả sử rằng khi một nút được tạo, nút đó chứa một con trỏ X trỏ đến một chỉ mục nút. Vì vậy, R (X) = ACLIndex (R). Không có nút nào thực sự chứa ACL của nó.

Bây giờ, đối với một nút N, tôi vẫn phải đuổi từ gốc trong trường hợp xấu nhất, nhưng tôi chỉ đơn giản nhảy xung quanh một chỉ mục phẳng để làm điều đó thay vì nảy lên trên cây. Sẽ tốt hơn nếu bạn có thể xác nhận rằng đối với một nút N đã cho, chỉ có một đường dẫn đến N, hoặc, nếu có nhiều đường dẫn, N giữ một bảng traversals khác, cho N, Path (N) từ nút A được nghe trong bảng đó. Trong thực tế, bạn phải để lại mẩu đường trong N khi một nút gắn vào nó.

Tôi tự hỏi liệu chúng ta có thể mượn một khái niệm từ định vị địa lý hay không. Nó không thể cho GPS cầm tay nhỏ của bạn để giữ tất cả các tuyến đường ngắn nhất có thể từ bất kỳ điểm nào đến bất kỳ điểm nào, và giữ cho thời gian giao thông trong tâm trí. Nó cheats và chia các bản đồ thành "gạch" Vì bạn không thể được tất cả trên bản đồ cùng một lúc, nhưng thay vào đó, bạn được giới hạn trong một gạch bạn đang ở, nó chỉ cần tính toán các đường đi ngắn nhất từ ​​bên trong cái ngói đó đã biết của nó tồn tại. Khi bạn thoát ra, nó sẽ tải khối đó và lặp lại. Thực tế, chúng tôi sử dụng nguyên tắc địa phương để giảm phạm vi.

Điều gì sẽ xảy ra nếu chúng tôi sử dụng cùng một ý tưởng? Đối với một nút đã cho, nếu bạn chia cây truy cập thành "phân đoạn", bạn có thể tính trước chi phí hoặc ít nhất là cập nhật chúng, và sau đó chi phí đường dẫn từ R đến N chỉ đơn giản là tổng chi phí phân bổ cộng với chi phí đường dẫn trong mảnh đất địa phương của bạn.