Люди производят много контента. Сообщения, текстовые файлы, электронные таблицы, презентации, отчеты, финансовые показатели и т. Д., Список можно продолжить. Обычно организации хотят иметь хранилище всего этого контента где-то централизованным (на случай, если ноутбук, например, сломается, будет потерян или украден). Это приводит к некоторой группировке и структуре разрешений. Вы не хотите, чтобы сотрудники просматривали записи о людских ресурсах друг друга, если только они не работают в отделе кадров, не работают в том же отделе расчета заработной платы, не выпускают квартальные данные и т. Д. По мере того, как эти данные растут, больше не становится просто ориентироваться, а поисковая система должна иметь смысл. всего этого
Но что, если ваша поисковая система выдаст 1000 результатов для запроса, а пользователь, выполняющий поиск, должен иметь доступ только к 4 вещам? Как вы справляетесь с этим? Проверять пользовательские права на каждый файл в реальном времени? Медленный. Предварительно рассчитать все разрешения документа для пользователя при входе в систему? Медленно, а что, если новые документы создаются или разрешения изменяются между логинами? Масштабируется ли система на 1 млн документов, 10 млн документов, 100 млн документов?
В примерах моделирования данных Neo4j есть решение с использованием графика.
Пользователи имеют прямые права доступа к документам (или папкам) или через группы. Папки могут иметь много дочерних документов, которые могут иметь много дочерних документов и «черепах на всем пути».
Наличие их на графике позволяет легко:
- Найти все файлы в структуре каталогов
- Какие файлы принадлежат кому?
- У кого есть доступ к файлу?
- … и так далее
Итак, вернемся к нашему вопросу. Что если поисковая система вернула 1000 записей, и нам нужно было узнать, к какому из них пользователь имеет доступ. Как мы можем сделать это на графике?
Не начиная с пользователя и обращаясь ко всем возможным документам, к которым у него есть доступ (так как это может занять очень много времени в графе документа 100M). Вместо этого мы начнем с документов и посмотрим, имеют ли они прямое право доступа к пользователю или группам, к которым принадлежит пользователь. Мы делаем это для всех документов, а для тех, с которыми у нас нет прямых отношений, мы перемещаемся в родительскую папку и пробуем снова. Мы будем умны и объединяем любые документы, имеющие одного и того же родителя, чтобы уменьшить количество проверок. Делая это таким образом, мы будем пересекать тысячи отношений (вместо миллионов) в зависимости от глубины структуры документа.
Я собираюсь пройтись по коду с помощью Neo4j Core API внутри неуправляемого расширения, чтобы к нему можно было получить доступ через REST, и я покажу вам, как я написал пару тестов производительности (один случайный и один статический), а также как я генерировал наши тестовые данные. Этот проект с открытым исходным кодом и доступен на GitHub .
Давайте углубимся. Нам нужно создать тест для нашего неуправляемого расширения, но мы не можем тестировать без некоторых примеров данных, поэтому давайте начнем с создания ImpermanentGraphDatabase в MyServiceTest.java :
private ImpermanentGraphDatabase db;
private MyService service;
private ObjectMapper objectMapper = new ObjectMapper();
private static final RelationshipType KNOWS = DynamicRelationshipType.withName("KNOWS");
private static final RelationshipType SECURITY = DynamicRelationshipType.withName("SECURITY");
private static final RelationshipType IS_MEMBER_OF = DynamicRelationshipType.withName("IS_MEMBER_OF");
private static final RelationshipType HAS_CHILD_CONTENT = DynamicRelationshipType.withName("HAS_CHILD_CONTENT");
Перед выполнением наших тестов мы хотим заполнить наш график, а затем разобрать его:
@Before
public void setUp() {
db = new ImpermanentGraphDatabase();
populateDb(db);
service = new MyService();
}
@After
public void tearDown() throws Exception {
db.shutdown();
}
Мы создадим несколько пользователей, группы, документы, а затем свяжем их друг с другом:
private void populateDb(GraphDatabaseService db) {
Transaction tx = db.beginTx();
try
{
Node personA = createPerson(db, "A");
Node personB = createPerson(db, "B");
Node personC = createPerson(db, "C");
Node personD = createPerson(db, "D");
Node doc1 = createDocument(db, "DOC1");
Node doc2 = createDocument(db, "DOC2");
Node doc3 = createDocument(db, "DOC3");
Node doc4 = createDocument(db, "DOC4");
Node doc5 = createDocument(db, "DOC5");
Node doc6 = createDocument(db, "DOC6");
Node doc7 = createDocument(db, "DOC7");
Node g1 = createGroup(db, "G1");
Node g2 = createGroup(db, "G2");
personA.createRelationshipTo(personB, KNOWS);
personB.createRelationshipTo(personC, KNOWS);
personC.createRelationshipTo(personD, KNOWS);
personA.createRelationshipTo(g1, IS_MEMBER_OF);
personB.createRelationshipTo(g2, IS_MEMBER_OF);
doc1.createRelationshipTo(doc4, HAS_CHILD_CONTENT);
doc2.createRelationshipTo(doc5, HAS_CHILD_CONTENT);
doc5.createRelationshipTo(doc7, HAS_CHILD_CONTENT);
Relationship secA1 = createPermission(personA, doc1, "R");
Relationship secA3 = createPermission(personA, doc3, "RW");
Relationship secB4 = createPermission(personB, doc4, "R");
Relationship secG2 = createPermission(g1, doc2, "R");
Relationship secG6 = createPermission(g2, doc6, "R");
tx.success();
}
finally
{
tx.finish();
}
}
Методы CreatePerson, CreateDocument и CreateGroup выглядят так:
private Node createPerson(GraphDatabaseService db, String uid) {
Index<Node> people = db.index().forNodes("Users");
Node node = db.createNode();
node.setProperty("unique_id", uid);
people.add(node, "unique_id", uid);
return node;
}
Метод CreatePermission немного отличается, так как мы создаем отношения.
private Relationship createPermission(Node person, Node doc, String permission) {
Relationship sec = person.createRelationshipTo(doc, SECURITY);
sec.setProperty("flags", permission);
return sec;
}
Наконец, мы напишем пару тестов, которые, как только мы получим метод «permissions», должны пройти:
@Test
public void shouldRespondToPermissions() throws BadInputException, IOException {
String ids = "A,DOC1 DOC2 DOC3 DOC4 DOC5 DOC6 DOC7";
Response response = service.permissions(ids, db);
List list = objectMapper.readValue((String) response.getEntity(), List.class);
assertEquals(new HashSet<String>(Arrays.asList("DOC1", "DOC2", "DOC3", "DOC4", "DOC5", "DOC7")), new HashSet<String>(list));
}
@Test
public void shouldRespondToPermissions2() throws BadInputException, IOException {
String ids = "B,DOC1 DOC2 DOC3 DOC4 DOC5 DOC6 DOC7";
Response response = service.permissions(ids, db);
List list = objectMapper.readValue((String) response.getEntity(), List.class);
assertEquals(new HashSet<String>(Arrays.asList("DOC4", "DOC6")), new HashSet<String>(list));
}
Отсюда мы переходим к фактическому алгоритму графа в MyService.java :
Сначала мы определяем наши типы отношений:
private ObjectMapper objectMapper = new ObjectMapper();
private static enum RelTypes implements RelationshipType
{
IS_MEMBER_OF,
SECURITY,
HAS_CHILD_CONTENT
}
Наш метод разрешений принимает строковый параметр, который содержит идентификатор пользователя, запятую и разделенный пробелами список идентификаторов документов. Мы берем входные данные и инициализируем некоторые переменные, которые будут содержать наши данные при прохождении графика.
@POST
@Path("/permissions")
public Response permissions(String body, @Context GraphDatabaseService db) throws IOException {
String[] splits = body.split(",");
PermissionRequest ids = new PermissionRequest(splits[0], splits[1]);
Set<String> documents = new HashSet<String>();
Set<Node> documentNodes = new HashSet<Node>();
List<Node> groupNodes = new ArrayList<Node>();
Set<Node> parentNodes = new HashSet<Node>();
HashMap<Node, ArrayList<Node>> foldersAndDocuments = new HashMap<Node, ArrayList<Node>>();
Нам нужно найти пользователя, и все документы, переданные в качестве поисковых запросов из нашей поисковой системы:
IndexHits<Node> uid = db.index().forNodes("Users").get("unique_id", ids.userAccountUid);
IndexHits<Node> docids = db.index().forNodes("Documents").query("unique_id:(" + ids.documentUids + ")");
try
{
for ( Node node : docids )
{
documentNodes.add(node);
}
}
finally
{
docids.close();
}
Нам также понадобятся все группы, к которым принадлежит пользователь:
if ( uid.size() > 0 && documentNodes.size() > 0)
{
Node user = uid.getSingle();
for ( Relationship relationship : user.getRelationships(
RelTypes.IS_MEMBER_OF, Direction.OUTGOING ) )
{
groupNodes.add(relationship.getEndNode());
}
Мы собираемся перебрать эти узлы документа. В цикле мы проверяем, имеет ли пользовательский узел прямую связь с документом, и, если да, добавляют его (и любые возможные дочерние документы в список «документов», который мы вернем в конце.
Iterator listIterator ;
do {
listIterator = documentNodes.iterator();
Node document = (Node) listIterator.next();
listIterator.remove();
//Check against user
Node found = getAllowed(document, user);
if (found != null) {
if (foldersAndDocuments.get(found) != null) {
for(Node docs : foldersAndDocuments.get(found)) {
documents.add(docs.getProperty("unique_id").toString());
}
} else {
documents.add(found.getProperty("unique_id").toString());
}
}
Если пользователь не имеет прямого подключения к документу, возможно, одна из групп, к которым он принадлежит, делает:
//Check against user Groups
for (Node group : groupNodes){
found = getAllowed(document, group);
if (found != null) {
if (foldersAndDocuments.get(found) != null) {
for(Node docs : foldersAndDocuments.get(found)) {
documents.add(docs.getProperty("unique_id").toString());
}
} else {
documents.add(found.getProperty("unique_id").toString());
}
}
}
Если у нас не получилось настроить родительский узел этого документа:
// Did not find a security relationship, go up the folder chain
Relationship parentRelationship = document.getSingleRelationship(RelTypes.HAS_CHILD_CONTENT,Direction.INCOMING);
if (parentRelationship != null){
Node parent = parentRelationship.getStartNode();
ArrayList<Node> myDocs = foldersAndDocuments.get(document);
if(myDocs == null) myDocs = new ArrayList<Node>();
ArrayList<Node> existingDocs = foldersAndDocuments.get(parent);
if(existingDocs == null) existingDocs = new ArrayList<Node>();
for (Node myDoc:myDocs) {
existingDocs.add(myDoc);
}
if (myDocs.isEmpty()) existingDocs.add(document);
foldersAndDocuments.put(parent, existingDocs);
parentNodes.add(parent);
}
Если мы добираемся до конца наших документов, мы переключаемся к родителям наших документов и перебираем их, пока не останется больше родителей (не достигли корневой папки нашего дерева документов).
if(listIterator.hasNext() == false){
documentNodes.clear();
for( Node parentNode : parentNodes){
documentNodes.add(parentNode);
}
parentNodes.clear();
listIterator = documentNodes.iterator();
}
} while (listIterator.hasNext());
Если мы не столкнулись с ошибкой, мы возвращаем список документов:
} else {documents.add("Error: User or Documents not found");}
uid.close();
return Response.ok().entity(objectMapper.writeValueAsString(documents)).build();
}
Метод getAllowed просто проверяет, найдены ли отношения безопасности с флагом свойства, содержащим «R»:
private Node getAllowed(Node from, Node to){
ConnectedResult connectedResult = isConnected(from, to, Direction.INCOMING, RelTypes.SECURITY);
if (connectedResult.isConnected){
if (connectedResult.connectedRelationship.getProperty("flags").toString().contains("R")) {
return connectedResult.connectedRelationship.getEndNode();
}
}
return null;
}
Метод isConnected позволяет нам узнать, связаны ли два узла друг с другом какими-то направленными отношениями:
private ConnectedResult isConnected(Node from, Node to, Direction dir, RelationshipType type) {
for (Relationship r : from.getRelationships(dir, type)) {
if (r.getOtherNode(from).equals(to)) return new ConnectedResult(true, r);
}
return new ConnectedResult(false, null);
}
Теперь, когда мы запускаем наши тесты:
Но как быстро это … и это масштабируется? Чтобы выяснить это, нам нужно создать увеличенный график и набор тестов производительности .
Оставайтесь с нами для второй части.